前缀、中缀、后缀表达式

举例:

(3 + 4) × 5 - 6 就是中缀表达式
- × + 3 4 5 6 前缀表达式
3 4 + 5 × 6 - 后缀表达式

栗子:

中缀表达式 a+bc-(d+e) 转化为前缀 与 后缀
第一步:按照运算符的优先级对所有的运算单位加括号~
式子变成拉:((a+(b
c))-(d+e))
第二步:转换前缀与后缀表达式
前缀:把运算符号移动到对应的括号前面
则变成拉:-( +(a (bc)) +(de))
把括号去掉:-+a
bc+de 前缀式子出现
后缀:把运算符号移动到对应的括号后面
则变成拉:((a(bc) )+ (de)+ )-
把括号去掉:abc
+de+- 后缀式子出现

习题:

某表达式的前缀形式为”+-*^ABCD/E/F+GH”,它的中缀形式为()

从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 op 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。
根据从右至左扫描计算过程如下:

题目中的前缀形式为:+-^ABCD/E/F+GH
1) 首先扫描 H,是数字 入栈 ,栈中为: H
2) 扫描 G 为数字 入栈 ,栈中为:G,H
3)扫描+ 为运算符 ,依次弹出G ,H ,得到 G+H 的结果 入栈,栈中为: G+H(在这里方便讲解 标记为 G+H)
4)扫描 F 为数字 ,入栈 ,栈中为 F, G+H
5)扫描 / 为运算符, 依次弹出 F,G+H ,计算F/(G+H) 的结果入栈 ,栈中为 F/(G+H)
6)扫描 E 为数字,入栈,栈中为 E, F/(G+H)
7) 扫描 / 为运算符, 依次弹出E, F/(G+H) ,计算 E/(F/(G+H))
8)扫描 D 为数字,入栈 栈中为:D, E/(F/(G+H))
9) 扫描 C 为数字,入栈 栈中为:C,D, E/(F/(G+H))
10) 扫描 B 为数字,入栈 栈中为:B,C,D, E/(F/(G+H))
11) 扫描 A 为数字,入栈 栈中为:A,B,C,D, E/(F/(G+H))
12) 扫描^ 为数字,依次弹出 A,B 计算 A^B的结果入栈, 栈中为:A^B ,C,D, E/(F/(G+H))
13) 扫描
为数字,依次弹出 A^B,C 计算 A^BC的结果入栈, 栈中为:A^B C,D, E/(F/(G+H))
14) 扫描-为数字,依次弹出 A^BC,D 计算 A^BC-D的结果入栈, 栈中为:A^B C-D, E/(F/(G+H))
15) 扫描+为数字,依次弹出 A^B
C-D, E/(F/(G+H)) 计算 A^BC-D+ E/(F/(G+H)) 的到结果
最后得到的表达式为: A^B
C-D+ E/(F/(G+H))

文章目录
  1. 1. 举例:
  2. 2. 栗子:
  3. 3. 习题:
|