前、中、后缀表达式和表达式树

前、中、后缀表达式的区别取决于操作符和操作数的位置：

1、前缀表达式：操作符在操作数前面，可通过前序遍历表达式树获得。

2、中缀表达式：操作符在操作数中间，可通过中序遍历表达式树获得（中缀表达式通过中序遍历得到后的括号是必须的）。

3、后缀表达式：操作符在操作数后面，可通过后序遍历表达式树获得。

表达式的二叉树(表达式树)：

表达式树： 即用二叉树来表示代数表达式，数的每一个内部节点都代表一个运算符，每一个叶子结点代表一个运算符数。

构造： 对于给定的中缀表达式（即代数表达式），我们通过下面步骤进行构建表达式二叉树

1、建立两个栈，一个操作符栈，用来存放操作符，一个是操作数栈，用来存放操作数。

2、从左往右遍历中缀表达式。

3、遇到操作数，为该操作数建立新节点，其值为操作数的值，然后放入操作数栈中。

4、遇到操作符通过按照以下规则处理：

5、当操作符从操作符栈中出栈时，为该操作符新建一个新节点，并从操作数栈中出栈两个操作数节点，将这两个操作数作为该操作符节点的两个孩子，然后将这个新节点压入到操作数栈中，其值为两个操作数通过操作符后的结果。当最后一个操作符出栈时，就构成了表达式树，且最后一个操作符节点为根节点。

计算中缀表达式的值

1、建立两个栈，一个操作符栈，用来存放操作符，一个是操作数栈，用来存放操作数。

2、从左往右遍历中缀表达式。

3、遇到操作数放入操作数栈中。

4、遇到操作符通过按照以下规则处理：

5、在操作符出栈时从栈中取出两个数计算出值后将结果值压入操作数栈

中缀表达式转后缀表达式：

1、建立两个栈，一个操作符栈，用来存放操作符，一个是操作数栈，用来存放操作数。

2、从左往右遍历中缀表达式

3、遇到操作数直接输出

4、遇到操作符通过按照以下规则处理：

5、在遍历完中缀表达式后，让操作符栈的最后元素出栈即可

中缀表达式转前缀表达式：

1、建立两个栈，一个操作符栈S1，另一个是存储中间结果的栈S2

2、从右往左遍历中缀表达式

3、遇到操作数压入S2中

4、遇到操作符通过按照以下规则处理：

5、重复2 到 5 操作，直到遍历到表达式最左端

6、将S1中剩余的运算依次弹出压入S2

7、依次弹出S2中的元素并输出，即是中缀表达式对应的前缀表达式。

表达树性质：

1、在表达树中，如果该结点向上走，即表示该子树的结点都被遍历完了（即该子树的值被算出来了），反之就是没有遍历完该子树。

2、当前内结点肯定相比其上一个结点的优先级更低。

根据1、2性质可以知道，通过栈模拟的时候，如果栈内的操作符的优先级比当前操作符的优先级高或者相等，即要把它们算出来，表示他们已经算过了（对应表达树中，该子树已经被遍历过了），然后再将计算后的值加入到操作数栈中。对于括号内的也是按照这个性质来进行的，当从左向右遍历遇到右括号，即表示括号内的部分已经要先计算出来，所以将括号内的内容都计算出来，然后再将计算后的值加入到操作数栈中即可。

中缀表达式求值代码：