三种表达式

前缀表达式，也叫波兰表达式(PN)。其特点是操作符置于操作数的前面。中缀表达式，操作符是以中缀的形式处于操作数的中间。中缀表达式中的括号是必需的。后缀表达式，也叫逆波兰表达式(RPN)。所有的操作符置于操作数的后面。

Example:
前缀表达式: - + 1 * + 2 3 4 5
中缀表达式: 1 + ((2 + 3) * 4) - 5
后缀表达式: 1 2 3 + 4 * 5 -

中缀表达式

中缀表达式（中缀记法）与其他两种表达式相比，虽然它符合人类的普遍用法，但是不容易被计算机解析。因此在计算机计算表达式时，通常需要先将中缀表达式转化成前缀表达式或者后缀表达式，再进行求值。

前缀表达式（前缀记法），也叫波兰表示法(Polish Notation)，不需要括号一样可以解析。

从右往左扫描表达式，遇到数字，将数字压入栈，遇到运算符，弹出栈顶两个数字进行运算，并将结果压入栈。重复计算直到表达式最左端，最后运算出来的值即为表达式的结果。

初始化两个栈，运算符栈和存储栈，从右往左扫描中缀表达式。
若遇到数字，将其压入存储栈。
若遇到操作符，则比较优先级：该运算符大于等于运算符栈顶元素，则该运算符入栈，否则栈顶元素出栈压入存储栈，重复比较该运算符与运算符栈的栈顶元素，直到该运算符入栈。
若遇到括号，若遇到为右括号，直接入运算符栈。若遇到左括号，则运算符栈的元素出栈压入存储栈，直到遇到右括号，且括号不入存储栈。
扫描表达式完毕后，若运算符栈内还有元素，则全部弹出压入临时栈。
将存储栈的结果出栈，得到结果即为前缀表达式。

后缀表达式（后缀记法），也叫逆波兰表示法(Reverse Polish Natation)，一样不需要括号解析。

与前缀表达式计算过程类似，区别是顺序从左往右。
从左往右扫描表达式，遇到数字，将数字压入栈，遇到运算符，弹出栈顶两个数字进行运算，并将结果压入栈。重复计算直到表达式最右端，最后运算出来的值即为表达式的结果。

与前缀表达式转化过程类似，区别是顺序从左往右，括号位置调换。

初始化两个栈，运算符栈和存储栈，从左往右扫描中缀表达式。
若遇到数字，将其压入存储栈。
若遇到操作符，则比较优先级：该运算符大于等于运算符栈顶元素，则该运算符入栈，否则栈顶元素出栈压入存储栈，重复比较该运算符与运算符栈的栈顶元素，直到该运算符入栈。
若遇到括号，若遇到为左括号，直接入运算符栈。若遇到右括号，则运算符栈的元素出栈压入存储栈，直到遇到左括号，且括号不入存储栈。
扫描表达式完毕后，若运算符栈内还有元素，则全部弹出压入临时栈。
将存储栈的结果出栈，得到结果即为前缀表达式。

将1 + ((2 + 3) * 4) - 5转化为表达式树为：

利用表达式树前序遍历出来的结果就是前缀表达式
利用表达式树中序遍历出来的结果就是中缀表达式
利用表达式树后续遍历出来的结果就是后缀表达式

根节点为优先级最低且靠右的操作符，操作数为叶节点，操作符为内部节点，子节点的左右顺序是其在操作符中的左右位置。不需要解析括号。