题目要求重新写出给出的后缀表达式，使原后缀表达式的栈方法和新表达式的队列方法表示的表达式相同，也就是两种表达式对应的表达式树相等。
仔细想想表达式树和队列的结构，可以发现，输出为表达式树按层次遍历得到的序列的逆序。
以下是我的代码：
#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 阅读(580)
评论(1) 编辑 收藏 引用 所属分类:
题目分类：数据结构