4011347_tle.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 96 行

#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 ;
	
	while (t && t->left && t->right)
	{
		t = t->parent;
	}
	node *tmp = (node *)malloc(sizeof(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);
	}
	while (p--)
		putchar(exp[p]);
	puts("");
}

int main()
{
	int n, l;

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