中缀表达式的转换问题

中缀表达式转成前、后缀表达式应该是数据结构中的基本问题。从考试上来说，这类问题基本是出在选择或者填空题中，那么我们如何才能用一种比较快捷的方式建立出中缀表达式所对应的前后缀表达式呢？

我们以式子：a*(b+c)-d/e为例。

先讨论如何转换成前缀表达式。首先，我们先将所有的直接相邻的操作数用括号括起来，例如式子中的b+c、d/e等，括号之后的式子如下：((a*(b+c))-(d/e))。然后从外向里一层一层去括号，去括号的途中，把这一层括号所对应的运算符放到对应的括号前面，最后去完括号的表达式即为前缀表达式。

按以上方法求表达式的过程如下：

①-(a*(b+c))(d/e)

②-*a(b+c)/de

③-*a+bc/de

得到的-*a+bc/de即为原式所对应的的前缀表达式。

后缀表达式的求法同前缀表达式，只不过是将对应的运算符放到对应括号的右边，过程如下：

①(a*(b+c))(d/e)-

②a(b+c)*de/-

③abc+*de/-

得到的abc+*de/-即为原式所对应的后缀表达式。

其实表达式的转换过程只不过是树的不同遍历方式而已，我们可以将中序表达式构建成二叉树，然后分别用树的先、中、后序遍历能够分别得到前、中、后缀表达式。用上面的中缀表达式用同样的方法加括号之后，还是从外往里一层一层去括号。最外层的括号对应的是减号，所以树的根节点为减号，减号左边的式子为左子树，减号右边的式子为右子树。用递归的方式处理剩下的式子，可建立出如下的一棵树：

对这棵树分别进行先、中、后序遍历可得到：

前缀表达式：-*a+bc/de

中缀表达式：a*(b+c)-d/e

后缀表达式：abc+*de/-