栈的经典应用
检查表达式中左右括号是否匹配,是栈的典型应用:遇左括号入栈,遇右括号弹栈匹配。
bool Match(char str[], int n) {
SqStack S;
InitStack(S);
for (int i = 0; i < n; i++) {
if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
Push(S, str[i]); // 左括号入栈
} else {
if (StackEmpty(S)) return false; // 无左括号可匹配
char top;
Pop(S, top);
// 判断是否匹配
if (str[i] == ')' && top != '(') return false;
if (str[i] == ']' && top != '[') return false;
if (str[i] == '}' && top != '{') return false;
}
}
return StackEmpty(S); // 最后栈为空才全部匹配
}
表达式求值通常分为两步:中缀转后缀,再后缀求值。
中缀转后缀:利用栈保存运算符,遵循优先级规则:
- 操作数直接输出
- 左括号入栈
- 遇到运算符时,弹出栈中所有优先级不低于它的运算符,再入栈
- 右括号时,弹出直到左括号
后缀表达式求值:从左到右扫描,遇到操作数入栈,遇到运算符则弹出两个操作数计算结果后入栈。
例如中缀表达式 (a+b)*c 转后缀为 ab+c*。
- 函数调用:递归调用的函数栈帧管理
- 递归实现:递归的本质就是栈
- 浏览器的前进/后退:两个栈分别记录历史
- 编辑器的撤销/重做:两个栈保存操作记录
栈的生活类比:一摞盘子——最后放上去的盘子最先被拿走。这就是后进先出(LIFO)。
习题 1
举例说明栈的典型应用。
解题思路:
本题要求举例说明栈的典型应用。思路是先点明这些应用都利用了栈“后进先出、只在一端操作”的特性,再按场景逐个列举并说明栈在其中承担的作用。
详细步骤:
- 表达式求值:中缀转后缀表达式、后缀表达式求值都借助栈保存运算符与中间结果。
- 括号匹配:用栈记录尚未闭合的左括号,遇到右括号时与栈顶左括号配对。
- 函数调用与递归实现:用栈保存每一层的返回地址、参数与局部变量,函数返回时按后进先出的次序恢复调用现场。
- 浏览器的前进后退、编辑器的撤销重做:用栈保存历史状态,最近的操作最先被撤销。
最终答案:
栈的典型应用包括:表达式求值(中缀转后缀、后缀求值)、括号匹配、函数调用与递归实现、浏览器的前进后退、编辑器的撤销重做等。
习题 2
如何利用栈检查一个字符串中的括号是否匹配?请简述算法思想。
解题思路:
本题考查用栈检查括号匹配。思路是让栈保存“已经遇到但尚未闭合的左括号”,遇到右括号时用栈顶左括号来配对,最后检查栈是否为空来判断是否全部匹配。
详细步骤:
- 初始化一个空栈。
- 从左到右扫描字符串:遇左括号(
(、[、{)就入栈。 - 遇右括号(
)、]、})时,若栈为空则匹配失败,否则弹出栈顶元素与之匹配,若不配对则失败。 - 扫描结束后,若栈为空则全部匹配成功,否则说明存在未匹配的左括号。
- 每个字符只入栈或出栈至多一次,时间复杂度 ,栈的空间复杂度 。
最终答案:
用栈依次记录待闭合的左括号,遇到右括号时与栈顶左括号配对,扫描结束栈为空即全部匹配。时间复杂度 ,空间复杂度 。
