表达式求值、表达式转二叉树

1、后序表达式求值：

后续表达式(逆波兰式)的特点：没有括号。

求值方法：

从前向后扫，

遇到操作数压栈；

遇到操作符，从栈中取出2个操作数运算，结果压栈。

最终栈中所剩的数为结果。

2、中序表达式求值
我们先来定义运算符的优先级：
(
+,-
*,/,%
从上到下依次升高
准备2个栈，一个专门存放运算符，另一个专门存放操作数。
1.遇到)，那么退栈计算到(为止.结果压栈。
2.遇到运算数.那么压栈。
3.如果当前运算符优先级低于栈顶运算符.那么计算栈顶运算符并将结果压栈.
4.否则压栈.

计算带括号和浮点数的表达式：

View Code

将中序表达式转换成后序表达式（逆波兰表达式）的算法：
(1)初始化一个空的运算符栈
(2)在没有到达中缀表达式的结尾及没有发生错误的时候，执行以下步骤：
 1.获取表达式中的一个标记（常数、变量、算术运算符，左括号，右括号）。
 2.如果标记是：
   i.  一个左括号，将其压入栈中
   ii. 一个右括号，连续弹出并显示栈中的元素，直到遇到一个左括号，不要显示这个左括号。（如果直到栈为空还没遇到一个左括号，则是一个错误）
   iii.一个运算符，如果栈为空，或者标记具有比栈顶元素更高的优先级，则将其压入栈中。否则出并显示栈顶的元素，接着继续比较标记和新的栈顶元素。（运算符比左括号的优先级高）
   iv 一个操作数，显示它
(3)当到达中缀表达式的结尾时，弹出并显示栈中的元素直到栈为空为止。

参考代码：

View Code

字符串表达式转化为二叉树：

View Code