栈
1. 括号匹配问题
1.1 概述
在代码编写中，若括号不匹配编译器会报错。最后出现的左括号最先被匹配（最里层被外层包裹），符合后进先出（LIFO）性质，可用栈解决。
1.2 算法演示
遵循规则：
- 左括号入栈。若遍历结束栈非空，则缺少右括号。
- 右括号出现时，检查栈顶是否为匹配的左括号。若不匹配或栈空，则错误。
1.3 算法实现
遍历字符串，根据字符类型执行入栈或出栈操作，最终判断栈是否为空且无匹配错误。
1.4 小结
利用栈的 LIFO 特性可有效检测括号是否成对出现。
2. 表达式求值问题
2.1 引言
操作数为数字，运算符为 +、-、*、/。数学家提出不用括号的表示法，即前缀表达式（波兰表达式）和后缀表达式（逆波兰表达式）。
2.2 简述
- 中缀：运算符在两个操作数中间。
- 后缀：运算符在两个操作数后面。
- 前缀：运算符在两个操作数前面。
2.3 中缀转后缀（手算）
使用'左优先原则'保证运算顺序唯一。观察运算符优先级和结合性进行转换。
2.4 后缀表达式的计算
2.4.1 手算
遇到操作数入栈，遇到运算符弹出两个操作数计算后将结果压栈，重复直至得到最终结果。
2.4.2 机算
表达式：AB+CD*E/-F+
步骤 | 栈内容（从底到顶）
---|---
1.A|[A]
2.B|[A,B]
3.+|[A+B]
4.C|[A+B,C]
5.D|[A+B,C,D]
6.*|[A+B,C*D]
7.E|[A+B,C*D,E]
8./|[A+B,(C*D)/E]
9.-|[(A+B)-((C*D)/E)]
10.F|[(A+B)-((C*D)/E),F]
11.+|[((A+B)-((C*D)/E))+F]
2.5 中缀转前缀（手算）
转为前缀表达式采用'右优先原则'，逻辑与后缀相反。
2.6 前缀表达式的计算
从右向左扫描，操作数入栈，遇运算符弹栈计算。示例如下：
| 步骤 | 元素 | 栈（从底到顶） | 说明 |
|---|---|---|---|
| 1 | 1 | [1] | 入栈 |
| 2 | 1 | [1,1] | 入栈 |
| 3 | + | [2] | 1+1=2 |
| ... | ... | ... | ... |
2.7 小结
后缀和前缀表达式消除了括号依赖，便于计算机处理。
3. 表达式求值问题（续）
3.1 中转后（手算）
包含括号的中缀表达式转后缀时，需处理括号优先级。
3.2 中转后（机算）
正常无括号形式与加括号形式处理逻辑一致，括号作为界限符控制入栈时机。
