#include "iostream"
#include "string"
#include "vector"
#include "deque"

using namespace std;

struct node
{
	int l;
	int r;
	int sign;
	char c;
}re[10001];


char str[10001];

int main()
{
	int Case;

	scanf("%d",&Case);

	for( ; Case-- ; )
	{
		

		scanf("%s",str);

		deque<node> s;
		deque<node> que;

		s.clear();
		int len = strlen(str);
		int i,j,k;
		node root;
		node p;

		for( i=0 ; i<len ; i++ )
		{
			//re[i].c = str[i];
			//re[i].l = -1;
			//re[i].r = -1;

			if( str[i]>='a'&&str[i]<='z' )
			{
				node tmp;
				tmp.c = str[i];
				tmp.l = -1;
				tmp.r = -1;
				tmp.sign = i;
				s.push_back(tmp);
				re[i] = tmp;
			}
			else
			{	
				node tmp;
				p.c = str[i];
				p.sign = i;

				tmp = s.back();
				s.pop_back();
				p.l = tmp.sign;

				tmp = s.back();
				s.pop_back();
				p.r = tmp.sign;

				s.push_back( p );
				root = p;

				re[i] = p;
			}
			
		}

		que.clear();

		que.push_back( root );

		string res = "";
		//res.clear();
		node t;

		//memset(flag,0,sizeof(flag));

		for( ; !que.empty() ; )
		{
			t = que.front();
			res = t.c + res;
			que.pop_front();

			if( t.r != -1 )
			{
				que.push_back( re[ t.r ] );
			}

			if( t.l != -1 )
			{
				que.push_back( re[ t.l ] );
			}

		}

		printf("%s\n",res.c_str());

	}
}

• O(n) + 大量stl = 125ms (1595) wywcgs 2008-03-27 15:04:53
• Re:我说这题是不是有问题？O(n)都会TLE (1604) hanjialong 2008-09-03 20:10:51