栈用例——中缀表达式转后缀表达式、二叉树求表达式

一、中缀表达式转后缀表达式

• 中缀表达式：就是我们平时书写的带括号的标准四则运算表达式，如9+(3-1)*3+10/2
• 后缀表达式：没有括号的，常用于编译器计算表达式，如9 3 1 - 3 * + 10 2 / +

编译器无法直接去计算中缀表达式，而是会先将中缀表达式利用【栈】先转换为后缀表达式。

转换算法

• 1、从左至右遍历中缀表达式（字符串），遇到数字则输出（暂时只做打印），遇到运算符则入栈先保存。
  2、若遇到")"右括号，则要将栈顶至最近的左括号的所有操作符依次出栈全部输出打印，注意括号都不打印。
  3、符号入栈也有规则。若是当前要入栈的符号优先级高于栈顶的符号，则直接入栈；否则（优先级相同或者低于），先将栈顶一个符号出栈，然后再将当前符号和新的栈顶符号比较，依次循环。
  4、当所有的数字都输出时，将栈中的符号也一次出栈输出。

二、编译器如何将后缀表达式用于实际的计算？利用二叉树构建表达式树

1、先用后缀表达式构建表达式树，设输入后缀表达式为ab+cde+**，得到表达式树的过程如下图：

前两个符号是操作数，因此创建两棵单结点树并将指向它们的指针压入栈中。

接着,"+"被读入，因此指向两棵树的指针被弹出，形成一棵新的树，并将指向它的指针压入栈中。

image

接下来读入"+"号，因此两棵树合并。

表达式树

【一种算法来把后缀表达式转变成表达式树。】我们一次一个符号地读入表达式。如果符号是操作数，那么就建立一个单结点树并将它推入栈中。如果符号是操作符，那么就从栈中弹出两棵树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; 
}