栈算表达式

ds生成

三种表达式概述

表达式类型	别名	特点	示例 (a + b * c)
中缀	Infix Notation	运算符在操作数中间。符合人类的思维习惯，但需要括号来处理优先级。	a + b * c
前缀	波兰式 Polish Notation	运算符在操作数前面。无需括号，也能无歧义地确定运算顺序。	+ a * b c
后缀	逆波兰式 Reverse Polish Notation	运算符在操作数后面。同样无需括号，是计算机最容易处理的表达式形式。	a b c * +

中缀表达式存在运算符优先级（如 * /优先于 + -）和括号问题，而前缀和后缀表达式通过固定的顺序本身就定义了运算顺序，因此没有优先级和括号的困扰。

栈的作用就在于：

1. 将人类易写的中缀表达式转换为计算机易处理的后缀表达式。
2. 对后缀（或前缀）表达式进行求值。

---

后缀表达式（逆波兰式）

后缀表达式求值（逆波兰表达式求值）

算法思想：从左到右扫描后缀表达式。

• 遇到操作数，则将其压入栈。
• 遇到运算符，则从栈中弹出两个操作数（注意顺序：先弹出的是右操作数，后弹出的是左操作数），进行运算，并将运算结果压回栈。
• 扫描结束后，栈中唯一的元素就是最终结果。

示例：计算后缀表达式 "5 1 2 + 4 * + 3 -"的值。

扫描元素	操作	栈 (底部 -> 顶部)	说明
5	压入栈	[5]
1	压入栈	[5, 1]
2	压入栈	[5, 1, 2]
+	遇到运算符+	[5, 3]	弹出 2(右操作数) 和 1(左操作数)，计算 1 + 2 = 3，结果入栈
4	压入栈	[5, 3, 4]
*****	遇到运算符*	[5, 12]	弹出 4和 3，计算 3 * 4 = 12，结果入栈
+	遇到运算符+	[17]	弹出 12和 5，计算 5 + 12 = 17，结果入栈
3	压入栈	[17, 3]
-	遇到运算符-	[14]	弹出 3(右操作数) 和 17(左操作数)，计算 17 - 3 = 14，结果入栈

最终结果：14。这个表达式等价于中缀表达式 5 + (1 + 2) * 4 - 3。

中缀表达式转后缀表达式

算法思想：需要两个栈，一个输出栈（或队列）存放结果，一个运算符栈存放临时运算符。从左到右扫描中缀表达式。

• 遇到操作数，直接加入输出。
• 遇到 (，直接压入运算符栈。
• 遇到 )，不断将运算符栈顶的运算符弹出并加入输出，直到遇到匹配的 (（将 (弹出，但不输出）。
• 遇到运算符：
  1. 若运算符栈为空或栈顶为 (，则直接压入运算符栈。
  2. 若当前运算符优先级高于栈顶运算符优先级，则压入运算符栈。
  3. 若当前运算符优先级低于或等于栈顶运算符优先级，则不断将栈顶运算符弹出并加入输出，直到满足条件1或2，再将当前运算符压入栈。
• 扫描结束后，将运算符栈中所有剩余运算符依次弹出并加入输出。

优先级： * /> + -> (

示例：将中缀表达式 a + b * c + (d * e + f) * g转换为后缀表达式。

扫描元素	操作	运算符栈 (底部 -> 顶部)	输出
a	输出a	[]	a
+	压入栈	[+]	a
b	输出b	[+]	a b
*****	*优先级高于+，压栈	[+, *]	a b
c	输出c	[+, *]	a b c
+	+优先级<=栈顶*，弹出*；+优先级<=栈顶+，弹出+；栈空，当前+压栈	[+]	a b c * +
(	压入栈	[+, (]	a b c * +
d	输出d	[+, (]	a b c * + d
*****	栈顶是(，直接压栈	[+, (, *]	a b c * + d
e	输出e	[+, (, *]	a b c * + d e
+	+优先级<=栈顶*，弹出*并输出；栈顶是(，当前+压栈	[+, (, +]	a b c * + d e *
f	输出f	[+, (, +]	a b c * + d e * f
)	弹出栈顶运算符+并输出，直到遇到(	[+]	a b c * + d e * f +
*****	*优先级高于栈顶+，压栈	[+, *]	a b c * + d e * f +
g	输出g	[+, *]	a b c * + d e * f + g
结束	弹出栈中所有运算符	[]	a b c * + d e * f + g * +

最终的后缀表达式：a b c * + d e * f + g * +

---

前缀表达式（波兰式）

前缀表达式的处理和后缀类似，但顺序是相反的。

前缀表达式求值

算法思想：从右向左扫描前缀表达式。

• 遇到操作数，则将其压入栈。
• 遇到运算符，则从栈中弹出两个操作数（注意顺序：先弹出的是左操作数，后弹出的是右操作数），进行运算，并将运算结果压回栈。
• 扫描结束后，栈中唯一的元素就是最终结果。

示例：计算前缀表达式 - + 5 * 1 2 3的值（等价于 5 + 1 * 2 - 3）。

扫描元素	操作	栈 (底部 -> 顶部)	说明
3	压入栈	[3]	从右往左扫描
2	压入栈	[3, 2]
1	压入栈	[3, 2, 1]
*****	遇到运算符*	[3, 2]	弹出 1(左操作数) 和 2(右操作数)，计算 1 * 2 = 2，结果入栈
5	压入栈	[3, 2, 5]
+	遇到运算符+	[3, 7]	弹出 5(左操作数) 和 2(右操作数)，计算 5 + 2 = 7，结果入栈
-	遇到运算符-	[4]	弹出 7(左操作数) 和 3(右操作数)，计算 7 - 3 = 4，结果入栈

最终结果：4。

中缀表达式转前缀表达式

转换算法比转后缀更复杂一些，通常有两种方法：

1. 先给中缀表达式完全括号化，然后将所有运算符移到其对应括号的前面，最后去掉括号。
   • 例如：(a + ((b * c) + ((d * e) + f)) * g)-> + a * + * b c + * d e f g
2. 使用双栈法（类似中转后，但需要从右向左扫描中缀表达式，并且遇到运算符时的判断逻辑是“优先级高或相等则弹出”，而不是“优先级高则压入”）。这个过程相对繁琐，不如第一种方法直观。

由于前缀表达式在实际中使用较少，我们了解其求值方法即可。

总结

操作	核心方法	关键点
后缀求值	从左到右扫描，遇操作数入栈，遇运算符出栈两个数计算	顺序：先弹出的是右操作数
中转后	从左到右扫描，用运算符栈处理优先级	优先级：当前运算符高于栈顶才压入，否则弹出
前缀求值	从右到左扫描，遇操作数入栈，遇运算符出栈两个数计算	顺序：先弹出的是左操作数
中转前	通常先括号化再移动运算符	较为复杂，使用较少

为什么后缀表达式最常用？

因为其求值和转换算法都非常直观和统一（都是从左到右扫描），非常适合基于栈的计算机系统实现。很多虚拟机（如JVM）和计算器的内部实现都采用后缀表达式。