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(); }