三种表达式 —— 前缀、中缀、后缀表达式
前缀表达式(波兰表达式)
前缀表达式又称为 波兰表达式,前缀表达式的 运算符位于操作数之前。
例如:( 2 + 3 ) × 4 – 5
对应的前缀表达式为:- × + 2 3 4 5
注意:前面这个表达式是一个中缀表达式,对应的是后面的这个前缀表达式。它的符号出现的顺序与中缀的顺序不一致。
前缀表达式中的符号顺序,就是他求值的规定了
前缀表达式求值过程
-
从 右到左 扫描表达式
-
遇到 数字 时,将数字压入堆栈
-
遇到 运算符 时
1)弹出栈顶的两个数(栈顶和次顶),用运算符对它们做相应的计算,并将结果入栈。
? 计算顺序是:先 弹出来的 (运算符) 后 弹出来的
然后重复以上步骤,直到表达式的最左端,最后运算出的值则是表达式的值。
看完前缀表达式的计算逻辑,那么你要明白的是,从一个 中缀表达式 转换为 前缀表达式 时,优先级顺序是已经处理好的,因为在求值时,不进行优先级的判定
例如:(3+4)x5-6
对应的前缀表达式为:- x + 3 4 5 6
,前缀表达式求值步骤如下:
-
从右到左扫描,将 6、5、4、3 压入栈
-
遇到
+
运算符时:将弹出 3 和 4(3 为栈顶元素,4 为次顶元素),计算出
3 + 4 = 7
,将结果压入栈 -
遇到
x
运算符时将弹出 7 和 5,计算出
7 x 5 = 35
,将 35 压入栈 -
遇到
-
运算符时将弹出 35 和 6,计算出
35 - 6 = 29
,压入栈 -
扫描结束,栈中留下的唯一一个数字 29 则是表达式的值
中缀表达式
中缀表达式就是 常见的运算表达式,如 (3+4)x5-6
。
中缀表达式的求值是人类最熟悉的,但是对于计算机来说却不好操作:
- 需要计算运算符的优先级
- 处理括号优先级
因此,在计算结果时,往往会将 中缀表达式 转成其他表达式,一般转成后缀表达式。
后缀表达式(逆波兰表达式)
后缀表达式 又称为 逆波兰表达式,与前缀表达式类似,只是 运算符 位于 操作数之后。
比如:(3+4)x5-6
对应的后缀表达式 3 4 + 5 x 6 -
再比如:
中缀表达式 | 后缀表达式 |
---|---|
a + b |
a b + |
a + (b-c) |
a b c - |
a+(b-c)*d |
a b c - d * + |
a+d*(b-c) |
a d b c - * + |
a=1+3 |
a 1 3 + = |
后缀表达式求值过程
-
从 左到右 扫描表达式
-
遇到 数字 时,将数字压入堆栈
-
遇到 运算符 时
弹出栈顶的两个数(栈顶和次顶),用运算符对它们做相应的计算,并将结果入栈。
计算顺序是:后 弹出来的 (运算符) 先 弹出来的
同样的也不用考虑符号优先级的问题
然后重复以上步骤,直到表达式的最右端,最后运算得出的值即为表达式的结果。
比如:(3+4)x5-6
对应的后缀表达式 3 4 + 5 x 6 -
-
从左到右扫描,将 3、4 压入堆栈
-
扫描到
+
运算符时将弹出 4 和 3,计算
3 + 4 = 7
,将 7 压入栈 -
将 5 入栈
-
扫描到
x
运算符时将弹出 5 和 7 ,计算
7 x 5 = 35
,将 35 入栈 -
将 6 入栈
-
扫描到
-
运算符时将弹出 6 和 35,计算
35 - 6 = 29
,将 29 压入栈 -
扫描表达式结束,29 是表达式的值,由此得出最终结果