中缀表达式转化为后缀表达式

中缀表达式转化为后缀表达式有两种方法，一种是利用栈，一种是把表达式转化为树再进一步求解，今天我们来深入了解一下这两种方法

给出下面一个例子：

我们把中缀表达式“9+（3-1）*3+10/2”转化为后缀表达式

1.首先初始化一个空栈，用来对符号进出栈使用

     

 

2.第一个字符是数字9，输出9，将后面的符号‘+’进栈 

+

 

3.第三个字符是‘（’，进栈

（

+

 

4.第四个字符为3，输出，将其后面的-号入栈，现在的输出为9 3

 

-

（

+

5.接着将1输出，现在输出为9 3 1，因其后面为右括号‘）’，与前面的‘（’匹配，将‘（’开始的栈内元素输出，现在输出为9 3 1-（括号不显示）,栈如下：

+

 

6.接着为‘*’，入栈，后面的3输出，现在输出为9 3 1 – 3

*

+

7.数字3后面为‘+’，栈顶‘*’的优先级大于‘+’，故出栈，由于栈中没有比‘+’优先级低的字符，故全部出栈，此时输出为：

9 3 1 – 3 * +，然后将这个‘+’入栈（是将* + 出栈之后它才入栈，），此时栈为：

 

+

8.接着为字符10，输出，将‘/’入栈，此时输出为：9 3 1 – 3* + 10

栈为：

/

+

 

9.剩下最后一个数字2，将其输出，然后将栈中字符全部出栈，最后输出结果为：9 3 1 – 3 * + 10 2 / +

看了上面的例子之后我们来总结一下套路：

1）        首先遇到数字就直接输出

2）        当遇到运算符时：

如果是右括号，则将从左括号开始的元素出栈（括号不显示），

如果不是右括号且前面有个左括号，直接入栈，

其余情况下比较与栈顶元素的优先级，优先级比栈顶元素不比栈顶元素高，则栈顶元素出栈，再次比较直到栈空或优先级比栈顶元素高，当前运算符入栈。

以上是利用栈来求解后缀表达式，下面我们利用树来求解

还是上面的例子

9+（3-1）*3+10/2，我们先把表达式转化为二叉树

我们先按照优先级给表达式加上括号：

1.（（9+（3-1）*3）+（10/2））

2.能看出此时式子分为2部分（9+（3-1）*3） 和（10/2）

故以‘+’作为根节点，（9+（3-1）*3）作为左子树，（10/2）作为右子树

3.我们先看左边，（9+（3-1）*3）也可分为2部分：左边为9，右边为（3-1）*3，故以‘+’作为根节点，数字9作为左子树，（3-1）*3作为右子树，（3-1）*3又可分为（3-1）和3，（3-1）又可分为3和1两部分，转化为树如图：

                

4.右边可以/为根节点，10为左子树，2为右子树  如图

              

 

6.将其组合得到如下一棵树：

               

 

表达式9+（3-1）*3+10/2对应的二叉树就如上图所示，我们对这棵二叉树进行遍历，采取前序遍历得到的就是前缀表达式，采取中序遍历得到的就是中缀表达式，采取后序遍历得到的就是后缀表达式。

我们要求得其后缀表达式，故对其进行后序遍历，先遍历其左子树，后遍历其右子树，最后遍历根结点，最后结果为：

9 3 1 – 3 * + 10 2 / +

以上就是中缀表达式转化为后缀表达式的两种方法，希望能对各位读者有所帮助。

 

参考自《大话数据结构》一书