数据结构（四）：栈的应用之表达式求值

1、表达式求值

问题描述：

用户从控制台输入一个数学表达式（所有输入均合法），数学表达式只包含四则运算，程序需输出表达式对应的结果，如：

输入：(1+2)*3+4-5

输出：8

解题思路：

涉及到的数学符号有 +、-、*、/、(、)。

因为左边的 + 比右边的 + 优先级要高，所以我们在判断符号优先级的时候还要带上方向。

带上方向的符号优先级表为（0表示相等，1表示左边比右边大，-1表示小）：

两个相同优先级的符号总是左边的优先级比右边的高。

1. 初始化两个栈，一个用来保存操作数，另一个用来保存操作符。
2. 从控制台读取一个字符。
3. 如果是操作数则压入操作数栈中。
4. 如果是操作符，与操作符栈栈顶元素比较
5. 若优先级高于栈顶元素，压入操作符栈
6. 否则取出操作符栈栈顶元素和操作数栈栈顶的两个元素进行运算，并将运算结果压入操作数栈中。
7. 继续执行第 4步
8. 判断是否输入结束（遇到换行）
9. 若输入结束，将操作符栈中的元素逐个弹出进行运算
10. 否则继续第 2步
11. 返回计算结果

代码请看：栈及其应用