題目要求重新寫出給出的后綴表達式，使原后綴表達式的棧方法和新表達式的隊列方法表示的表達式相同，也就是兩種表達式對應的表達式樹相等。
仔細想想表達式樹和隊列的結構，可以發現，輸出為表達式樹按層次遍歷得到的序列的逆序。
以下是我的代碼：
#include<stack>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxl(10007);
struct Node
{
int father,left,right;
};
char r[kMaxl];
Node tree[kMaxl];
int ans[kMaxl];
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",r);
int n(strlen(r));
stack<int> s;
memset(tree,-1,kMaxl*sizeof(Node));
for(int i=0;i<n;i++)
{
if(r[i]>='a' && r[i]<='z')
s.push(i);
else
{
int x,y;
y=s.top();
s.pop();
x=s.top();
s.pop();
tree[i].left=x;
tree[i].right=y;
tree[x].father=tree[y].father=i;
s.push(i);
}
}
/*
for(int i=0;i<n;i++)
printf("%d %d %d\n",tree[i].father,tree[i].left,tree[i].right);
//*/
int root;
for(int i=0;i<n;i++)
if(tree[i].father==-1)
{
root=i;
break;
}
queue<int> q;
int len=0;
memset(ans,0,kMaxl*sizeof(int));
q.push(root);
while(!q.empty())
{
int t(q.front());
q.pop();
ans[len++]=t;
if(tree[t].left!=-1)
q.push(tree[t].left);
if(tree[t].right!=-1)
q.push(tree[t].right);
}
for(int i=len-1;i>=0;i--)
printf("%c",r[ans[i]]);
printf("\n");
}
return 0;
}
posted on 2011-04-13 12:06
lee1r 閱讀(611)
評論(1) 編輯 收藏 引用 所屬分類:
題目分類：數據結構