关键字：表达式、中缀、前缀、后缀、波兰、逆波兰
概述
在数据结构中，栈有一个常见的应用就是计算机中表达式的计算。
基础知识
中缀表达式（我们常用的写法，通常运算符在中间）、前缀表达式（波兰表达式，通常运算符在前面）、后缀表达式（逆波兰表达式，通常运算符在后面）
掌握的算法
需要掌握的是：中缀→后缀、中缀→前缀、前缀→中缀、后缀→前缀，其中前缀和后缀转换为中缀即为计算机求值的过程。
中缀转换算法总结
比较
基本算法一致，加粗字体为需要注意的不同点。
| 中缀→前缀 | 中缀→后缀 |
|---|---|
| 1.从右到左扫描。 | 1.从左到右扫描。 |
| 2.设置两个空栈，一个为对象栈S1，一个为运算符栈S2（存放运算符）。 | 2.设置两个空栈，一个为对象栈S1，一个为运算符栈S2（存放运算符）。 |
| 3.扫描过程遇到数或者运算符： | 3.扫描过程遇到数或者运算符： |
| （1）遇到数直接压入S1。 | （1）遇到数直接压入S1。 |
| （2）扫描遇到运算符时：若S2为空或者S2栈顶为右括号)，扫描到的运算符直接压入S2；若扫描到的运算符优先级高于等于S2栈顶运算符，扫描到的运算符直接压入S2，否则（小于时）从S2弹出元素压入S1。直到将扫描到的运算符压入S2，（2）步骤结束。 | （2）扫描遇到运算符时：若S2为空或者S2栈顶为左括号(，扫描到的运算符直接压入S2；若扫描到的运算符优先级高于S2栈顶运算符，扫描到的运算符直接压入S2，否则（小于等于时）从S2弹出元素压入S1。直到将扫描到的运算符压入S2，（2）步骤结束。 |
| 4.扫描过程遇到括号： | 4.扫描过程遇到括号： |
| （1）遇到右括号)，直接压入S2。 | （1）遇到左括号(，直接压入S2。 |
| （2）遇到左括号(，依次弹出S2元素并压入S1，直到S2栈顶为右括号)，然后丢弃这一对括号。 | （2）遇到右括号)，依次弹出S2元素并压入S1，直到S2栈顶为左括号(，然后丢弃这一对括号。 |
| 5.重复3、4步骤直到扫描完毕。 | 5.重复3、4步骤直到扫描完毕。 |
| 6.依次弹出S2元素并压入S1。 | 6.依次弹出S2元素并压入S1。 |
| 7.弹出S1所有元素，输出序列即为转换的前缀表达式。 | 7.弹出S1所有元素，输出序列的逆序即为转换的后缀表达式。 |
不同点
- 扫描方向：前缀为右→左，后缀为左→右。
- 扫描中运算符比较：前缀扫描的运算符优先级大于等于S2栈顶运算符即可，后缀只能够大于。
- 扫描中括号判断：前缀为右括号)，后缀为左括号(。这里很容易理解，从扫描方向来直观感受，前缀首先遇到的就是右括号)，后缀首先遇到的就是左括号(。
- 栈输出序列与最终的表达式的关系：前缀相同，后缀为逆序。
计算机求值算法总结
算法
通过一个栈进行运算，遇到运算符就弹出栈顶元素和次顶元素计算。
不同点
运算对象的顺序：前缀为栈顶元素+运算符+次顶元素，后缀为次顶元素+运算符+栈顶元素。
记忆方法：前缀为栈顶元素在前，后缀为栈顶元素在后。
网友评论