题意：题目意思是给出后缀表达式。能够通过栈来计算表达式的值，即转化为中缀表达式。

然后如果如今不用栈。而是用队列来操作。即每遇到一操作符时。进行两次pop和一次push。（这里注意，先pop出来的作为第二操作数，操作符如果是不满足交换律和结合律的）由于队列的pop和push，与栈的不同么，所以。问队列的输入应该是如何的，才干和给定的输入用栈来计算，所得值同样。（即转化为同样的中缀表达式）

思路：先转为表达式树。然后能够看到用队列的方式即为层次遍历（队列实现）这棵树，然后将值逆序输出。

这里树的链式存储我没实用到内存动态分配、指针等easy出错的东西。

我是先声明了一个MAXN个的Node数组anode，然后每一个字符来这个数组申请node。用cnt来索引。位置0不存储数据，用索引0来表示不存在的结点。即相当于null。node结点中的left和right即为左右孩子结点在anode数组中的下标。建树的过程即函数build中用到的栈也是存对应结点在anode数组中的下标。

（好久没做题了。这个还一次AC了啊；之前在UVa单题最高排名也一百多。这个题排到77，破纪录了嘿嘿

年轻是一种债务，要加油~）

Code：

#include<stdio.h>

#include<string.h>

#define MAXN 10000

struct Node

{

 char data;

 int left,right;      //存的是anode数组的下标

};

void bfs(int root);

int build(char *str);

Node anode[MAXN];

int stack[MAXN+1];

char exp[MAXN+1];

int main()

{

 int n;

 scanf("%d",&n);

 while(n-->0)

 {

  scanf("%s",exp);

  int root=build(exp);//printf("%d\n",root);

  bfs(root);

 }

 return 0;

}

void bfs(int root)

{

 int que[MAXN];

 char ans[MAXN];

 int cnt=0;

 int front=0,rear=1;

 que[0]=root;

 while(front<rear)

 {

  int t=que[front++];

  ans[cnt++]=anode[t].data;

  if(anode[t].left!=0) que[rear++]=anode[t].left;

  if(anode[t].right!=0) que[rear++]=anode[t].right;

 }

 ans[cnt]='\0';

 //print      //printf("%s\n",ans);

 for(int i=0;i<cnt;++i)

  printf("%c",ans[cnt-i-1]);

 printf("\n");

}

int build(char *str)

{

 int cnt=1;//anode数组的下标0元素表示不存在该结点

 int top=0;//始终指向栈顶元素。stack[0]不用

 while((*str)!='\0')

 {

  anode[cnt].data=*str;

  if(*str>='a'&&*str<='z')

  {

   anode[cnt].left=anode[cnt].right=0;

   stack[++top]=cnt;

  }

  else

  {

   if(top>1)

   {

    anode[cnt].right=stack[top--];

    anode[cnt].left=stack[top--];

   }

   stack[++top]=cnt;

  }

  str++;

  cnt++;

 }//while

 return cnt-1;

}