题意:题目意思是给出后缀表达式。能够通过栈来计算表达式的值,即转化为中缀表达式。
然后如果如今不用栈。而是用队列来操作。即每遇到一操作符时。进行两次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 ",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]='