表达式类型

对于前缀表达式和后缀表达式来说，表达式是不需要用括号确定优先级的。

表达式原理

网上的很多教程都没有同时提到这三种表达式转化与表达式树之间的关系，这里详细讲一下。

二叉树遍历

二叉树分别存在三种常见的遍历方式：前序遍历、中序遍历、后序遍历。（层序遍历与表达式无关）遍历点的顺序结果分别为前缀表达式，中缀表达式，后缀表达式。

1. 先序遍历：先访问根节点，再访问左子树，最后访问右子树。
2. 中序遍历：先访问左子树，再访问根节点，最后访问右子树。
3. 后序遍历：先访问左子树，再访问右子树，最后访问根节点。

当然我们常见的二叉树都是以字母或者数字为点的形式呈现的，例如：

我们很容易就会得到其先序遍历、中序遍历、后序遍历的表达式。

表达式树

当我们对上面棵树进行一系列的变化，就可以的到一颗表达式树。

这就是一颗表达式树，在这棵树中，只有叶节点是操作数，其他节点都是操作符。通过递归的方法分别计算一个节点左右字数的值，就可以得到这个算式的值。例如该树为表达式$d/e-a*(b+c)$的表达式树。

我们尝试去用不同的方式遍历一下这颗树。

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

中缀表达式：$d/e-a*b+c$（无括号）

中缀表达式：$d/e-a*(b+c)$（有括号）

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

可见，前缀表达式就是运算符放在操作数之前，后缀表达式就是运算符放在表达式之后，最直接的中缀表达式就是原表达式去括号后的序列，所以，直接写出中缀表达式可能会在逻辑上出现错误，需要加上括号。

在CSP/NOIP初赛考试的题目中，表达式的不同表示方法即为前中后缀表达式。

表达式转化

原理如上，目前在初赛题目中常见的有两种情况的转换，但是任何的转换都存在一个通法，即将给出的表达式还原为表达式树，使其叶子结点为操作数，其他节点为运算符。进行不同方式的遍历得到其他形式的表达式。

但是对于中缀表达式转化为前后缀表达式问题，存在一种简单方法：括号法，以上述中缀表达式（有括号）为例，分以下几步：

1. 给中缀表达式加上括号，明确计算优先级。

   $d/e-a*(b+c) \rightarrow ((d/e)-(a*(b+c)))$

2. 把括号中的运算符号移到括号前面或者后面（移到前面为前缀表达式，移到后面为后缀表达式）

   前缀表达式：$((d/e)-(a*(b+c))) \rightarrow -(/(de)*(a+(bc)))$

   后缀表达式：$((d/e)-(a*(b+c))) \rightarrow ((de)/(a(bc)+)*)-$

3. 删去所有括号，剩下的即为最终解。

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

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

经过表达式树的检验可知，该结果正确。

其实，括号法就是省略了画出表达式树的过程，第一步加入的括号从原理上来说是确定了符号与其两个子树的关系并对这棵树重新整理。