关键字:表达式、中缀、前缀、后缀、波兰、逆波兰
概述
在数据结构中,栈有一个常见的应用就是计算机中表达式的计算。
基础知识
中缀表达式(我们常用的写法,通常运算符在中间)、前缀表达式(波兰表达式,通常运算符在前面)、后缀表达式(逆波兰表达式,通常运算符在后面)
掌握的算法
需要掌握的是:中缀→后缀、中缀→前缀、前缀→中缀、后缀→前缀,其中前缀和后缀转换为中缀即为计算机求值的过程。
中缀转换算法总结
比较
基本算法一致,加粗字体为需要注意的不同点。
中缀→前缀 | 中缀→后缀 |
---|---|
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栈顶运算符即可,后缀只能够大于。
- 扫描中括号判断:前缀为右括号),后缀为左括号(。这里很容易理解,从扫描方向来直观感受,前缀首先遇到的就是右括号),后缀首先遇到的就是左括号(。
- 栈输出序列与最终的表达式的关系:前缀相同,后缀为逆序。
计算机求值算法总结
算法
通过一个栈进行运算,遇到运算符就弹出栈顶元素和次顶元素计算。
不同点
运算对象的顺序:前缀为栈顶元素+运算符+次顶元素,后缀为次顶元素+运算符+栈顶元素。
记忆方法:前缀为栈顶元素在前,后缀为栈顶元素在后。