305 栈的应用

栈的应用

中缀转后缀表达式

算法思想：利用栈存储运算符，遇到操作数直接输出，遇到运算符根据优先级决定入栈或出栈。

转换规则：

1. 从左到右扫描中缀表达式
2. 遇到操作数：直接输出到后缀表达式
3. 遇到运算符：
   • 若栈空或栈顶为 ’(‘：运算符入栈
   • 若运算符优先级大于栈顶运算符：入栈
   • 若运算符优先级小于等于栈顶运算符：栈顶元素出栈并输出，重复比较直到满足入栈条件
4. 遇到 ’(‘：直接入栈
5. 遇到 ’)‘：栈顶元素出栈并输出，直到遇到 ’(’，’(’ 出栈但不输出
6. 扫描结束：栈中剩余运算符全部出栈并输出

运算符优先级：$()$ > $\ast ,/$ > $+,-$（同级从左到右运算）

示例：$a+b\ast c$ → $abc\ast +$

• 扫描 a：输出 a
• 扫描 +：入栈
• 扫描 b：输出 b
• 扫描 *：优先级高于 +，入栈
• 扫描 c：输出 c
• 结束：* 出栈输出，+ 出栈输出

后缀转中缀表达式

算法思想：利用栈存储操作数，遇到运算符时弹出两个操作数进行组合。

转换规则：

1. 从左到右扫描后缀表达式
2. 遇到操作数：入栈
3. 遇到运算符：
   • 弹出栈顶两个元素作为右操作数和左操作数
   • 组合成 $(左操作数运算符右操作数)$ 的中缀表达式
   • 将组合结果入栈
4. 扫描结束：栈顶元素即为中缀表达式

示例：$abc\ast +$ → $(a+(b\ast c))$

• 扫描 a：a 入栈
• 扫描 b：b 入栈
• 扫描 c：c 入栈
• 扫描 *：弹出 c 和 b，组合 $(b\ast c)$ 入栈
• 扫描 +：弹出 $(b\ast c)$ 和 a，组合 $(a+(b\ast c))$ 入栈

括号匹配

问题描述：判断表达式中的括号是否正确匹配，包括小括号 ()、中括号[]、大括号{}。

算法思想：利用栈的后进先出特性，左括号入栈，右括号与栈顶匹配。

匹配规则：

1. 从左到右扫描字符串
2. 遇到左括号 $($、$[$、$\{$：入栈
3. 遇到右括号 $)$、$]$、$\}$：
   • 若栈空：匹配失败
   • 若栈顶括号与当前右括号匹配：出栈继续
   • 若不匹配：匹配失败
4. 扫描结束：栈空则匹配成功，否则失败

括号对应关系：

左括号	右括号
(	)
[	]
{	}

算法实现要点：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$（最坏情况全为左括号）
• 只需关注括号字符，忽略其他字符

典型应用：编译器语法检查、表达式合法性验证、代码编辑器括号高亮等。