栈用例——中缀表达式转后缀表达式、二叉树求表达式
2018-07-24 本文已影响75人
XDgbh
一、中缀表达式转后缀表达式
- 中缀表达式：就是我们平时书写的带括号的标准四则运算表达式，如
9+(3-1)*3+10/2 - 后缀表达式：没有括号的，常用于编译器计算表达式，如
9 3 1 - 3 * + 10 2 / +
编译器无法直接去计算中缀表达式，而是会先将中缀表达式利用【栈】先转换为后缀表达式。
转换算法
- 1、从左至右遍历中缀表达式（字符串），遇到数字则输出（暂时只做打印），遇到运算符则入栈先保存。
2、若遇到")"右括号，则要将栈顶至最近的左括号的所有操作符依次出栈全部输出打印，注意括号都不打印。
3、符号入栈也有规则。若是当前要入栈的符号优先级高于栈顶的符号，则直接入栈；否则（优先级相同或者低于），先将栈顶一个符号出栈，然后再将当前符号和新的栈顶符号比较，依次循环。
4、当所有的数字都输出时，将栈中的符号也一次出栈输出。
二、编译器如何将后缀表达式用于实际的计算？利用二叉树构建表达式树
1、先用后缀表达式构建表达式树，设输入后缀表达式为ab+cde+**，得到表达式树的过程如下图：
前两个符号是操作数，因此创建两棵单结点树并将指向它们的指针压入栈中。
接着,"+"被读入，因此指向两棵树的指针被弹出，形成一棵新的树，并将指向它的指针压入栈中。
image
然后,c,d和e被读入，在单个结点树创建后，指向对应的树的指针被压入栈中。
接下来读入"+"号，因此两棵树合并。
继续进行，读入"*"号，因此，弹出两棵树的指针合并形成一棵新的树，"*"号是它的根。
最后，读入一个符号，两棵树合并，而指向最后的树的指针被留在栈中。
表达式树
【一种算法来把后缀表达式转变成表达式树。】我们一次一个符号地读入表达式。如果符号是操作数，那么就建立一个单结点树并将它推入栈中。如果符号是操作符，那么就从栈中弹出两棵树T1和T2(T1先弹出)并形成一棵新的树，该树的根就是操作符，它的左、右儿子分别是T2和T1。然后将指向这颗树的指针压入栈中。
完整步骤看这里：https://blog.csdn.net/buaa_shang/article/details/9124075
2、将表达式树进行中序遍历，可以分别计算各个子树的结果，最后计算出整个表达式的结果(a+b)*(c*(d+e))
【问题】 可以看到中序遍历出来的又是一个普通的四则运算中缀表达式。那为什么要引入后缀表达式做这个转换？
以开头的例子：中缀9+(3-1)*3+10/2==》后缀9 3 1 - 3 * + 10 2 / +==》表达式树==》中序遍历==>9 + 3 - 1 * 3 + 10 / 2
相当于只是做了一个去括号的操作，但是在遍历的同时将每两个叶子节点的数字计算出了结果，然后依次递归返回时将最后的计算结果输出。
typedef struct
{ //其实也可以用union类型来做，更省空间
int num; //存储整形数字
char ch; //存储运算符号
} ElemType;
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
//中序遍历运算并输出表达式
int Travel(BiTree T)
{
int result;
if (T->lchild==NULL&&T->rchild==NULL){
printf("%d",T->data.num);
result=T->data.num;
}
else
{
printf("(");
int num1=Travel(T->lchild);
printf("%c",T->data.ch); //中序遍历打印各个非叶子节点的符号值
int num2=Travel(T->rchild);
printf(")");
//对每两个叶子节点计算运算值。由此可见后序遍历也是可以计算的。
switch (T->data.ch)
{
case '+':result=num1+num2; break;
case '-':result=num1-num2; break;
case '*':result=num1*num2; break;
case '/':result=num1/num2; break;
}
}
return re;
}
