PKU 3367 Expressions

http://poj.org/problem?id=3367
逆ポーランド記法で入力された式を、スタックを使ってパースした結果が、
キューを使ってパースした結果と一致するような式を出力しろというような問題。

式を木になおしたあと、キューを使って逆シミュレート。
入力が非常に多いようなので、下手な実装だとTLEするようです。
new を使いまくって死んでました。

typedef struct _node{
  char op;
  _node*ri;
  _node*le;
}node;

node ent[30000];
int esz=0;
char in[30000];
char ans[30000];
int sz;

void solve(){
  scanf(" %s",in);
  stack<node*> st;
  esz=0;
  for(char*it=in;*it;++it){
      ent[esz].op=*it;    
    if(isupper(*it)){
      ent[esz].le=st.top();st.pop();
      ent[esz].ri=st.top();st.pop();      
    }
    st.push(ent+esz++);    
  }

  queue<node*> q;
  q.push(st.top());

  sz=0;
  while(!q.empty()){
    node* p=q.front();q.pop();
    ans[sz++]=p->op;
    if(isupper(p->op)){
      q.push(p->ri);
      q.push(p->le);
    }
  }

  ans[sz]=0;
  reverse(ans,ans+sz);
  puts(ans);
}

main(){
  int T;
  scanf("%d",&T);
  while(T--)solve();
}