Expressions
题目链接：http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=14332
题目大意：
一个表达式，可以用栈来处理，同时可以用队列来处理。现在告诉你用栈处理的表达式顺序，求其用队列表示的顺序？ 几种操作数为小写字母，操作符为大写字母。
如输入：
2 xyPzwIM abcABdefgCDEF则输出：
wzyxIPM gfCecbDdAaEBF
解题思路：
我们知道表达式在计算机中可以用二叉树表示。其中正常的表达式为树的中序遍历，而采用栈来模拟，则为树的后序遍历。如果用队列来表示表达式呢？
我们不妨把第一组样例的表达式处理成二叉树，然后对比队列的输出，便一目了然了。
我们可以看到，用栈表示为其后序，而用队列表示是其层次遍历的逆序输出。层次为MPIxyzw。
所以这道题就变成了先建树，然后再层次遍历，最后逆序输出。
我一开始的做法是，利用栈的后序，可以得到其中序遍历，然后利用中序和后序可以建树。但是由于这个树比较深，所以会爆栈。
其实利用栈的后序，完全可以直接建树了，因为操作符和操作数分别是大小写字母，可以区分。
即遇到小写字母就建立一个只有根节点的树，并将该地址入栈。
遇到大写字母，就建立一个根节点为该大写字母，然后从栈中取出两个地址，分别作为该节点的左右孩子，然后再将该根节点地址入栈
由于怕栈溢出，所有的栈操作都改为了数组模拟。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<string> #include<stack> #include<algorithm> using namespace std; char post[10010]; struct tree { char ch; tree* lchild; tree* rchild; }; tree* newnode() { tree* u = (tree*) new (tree); u->ch = ‘\0‘; u->lchild = u->rchild = NULL; return u; } void bfs(tree* root) { char out[10010]; tree* que[10010] = {NULL}; int font, rear, k = 0; font = 0, rear = 1; que[font] = root; out[k++] = root->ch; while(font < rear) { tree* tmp; tree* next; tmp = que[font++]; if (tmp->lchild != NULL) { next = tmp->lchild; que[rear++] = next; out[k++] = next->ch; } if (tmp->rchild != NULL) { next = tmp->rchild; que[rear++] = next; out[k++] = next->ch; } } for (int i = k - 1; i >= 0; i--) cout<<out[i]; } int main () { int t, i, n; cin>>t; getchar(); while(t--) { gets(post); n = strlen(post); tree* s[10010]; int k = 0; for (i = 0; i < n; i++) { if (post[i] <= ‘Z‘) //碰到操作符，从栈中取出两个地址，分别作为左右孩子，然后将其根地址再次入栈 { tree* u = newnode(); u->ch = post[i]; u->rchild = s[--k]; u->lchild = s[--k]; s[k++] = u; } else //碰到操作数，将地址其入栈 { tree* u = newnode(); u->ch = post[i]; s[k++] = u; } } tree* root = s[--k]; //把树的根节点取出 bfs(root); //进行层次遍历 puts(""); memset(post, 0, sizeof(post)); } return 0; }