数据结构（四）：栈的应用之表达式求值
2018-11-23 本文已影响0人
渔父歌
1、表达式求值
问题描述：
用户从控制台输入一个数学表达式（所有输入均合法），数学表达式只包含四则运算，程序需输出表达式对应的结果，如：
输入：(1+2)*3+4-5
输出：8
解题思路：
涉及到的数学符号有 +、-、*、/、(、)。
因为左边的 + 比右边的 + 优先级要高，所以我们在判断符号优先级的时候还要带上方向。
带上方向的符号优先级表为（0表示相等，1表示左边比右边大，-1表示小）：
| 横右竖左 | + | - | * | / | （ | ） |
|---|---|---|---|---|---|---|
| + | 1 | 1 | -1 | -1 | -1 | 1 |
| - | 1 | 1 | -1 | -1 | -1 | 1 |
| * | 1 | 1 | 1 | 1 | -1 | 1 |
| / | 1 | 1 | 1 | 1 | -1 | 1 |
| （ | -1 | -1 | -1 | -1 | 0 | 0 |
| ） | 1 | 1 | 1 | 1 | 0 | 0 |
两个相同优先级的符号总是左边的优先级比右边的高。
- 初始化两个栈，一个用来保存操作数，另一个用来保存操作符。
- 从控制台读取一个字符。
- 如果是操作数则压入操作数栈中。
- 如果是操作符，与操作符栈栈顶元素比较
- 若优先级高于栈顶元素，压入操作符栈
- 否则取出操作符栈栈顶元素和操作数栈栈顶的两个元素进行运算，并将运算结果压入操作数栈中。
- 继续执行第 4步
- 判断是否输入结束（遇到换行）
- 若输入结束，将操作符栈中的元素逐个弹出进行运算
- 否则继续第 2步
- 返回计算结果
代码请看：栈及其应用
