4011174_re.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <queue>
#include <ctype.h>
#include <algorithm>

using namespace std;

char exp[10011];

struct node
{
	struct node * left, *right, *parent;
	char op;
};

node *root;

void build(node *t, int p)
{
	if (p < 0)
		return ;
	node *tmp = new node();

	tmp->op = exp[p];
	tmp->left = tmp->right = NULL;
	tmp->parent = t;
	if (t->left == NULL)
	{
		t->left = tmp;
		if (isupper(exp[p]))
		{
			build(tmp, p - 1);
		}
		else
		{
			build(t, p - 1);
		}
	}
	else
	{
		t->right = tmp;
		if (isupper(exp[p]))
		{
			build(tmp, p - 1);
		}
		else
		{
			build(t->parent, p - 1);
		}
	}
}

queue <node *> que;

void visit()
{
	node *t;
	int p (0);

	que.push(root);
	while (!que.empty())
	{
		t = que.front();
		exp[p++] = t->op;
		que.pop();
		if (t->left == NULL)
			continue;
		que.push(t->right);
		que.push(t->left);
	}
	exp[p] = '\0';
	reverse(exp, exp + p);
	puts(exp);
}

int main()
{
	int n, l;

	scanf("%d", &n);
	while (n--)
	{
		scanf("%s", exp);
		l = strlen(exp);
		root = new node();
		root->op = exp[--l];
		root->left = root->right = root->parent = NULL;
		build(root, --l);
		visit();
	}
	return 0;
}