Logo

栈的经典应用

括号匹配

检查表达式中左右括号是否匹配，是栈的典型应用：遇左括号入栈，遇右括号弹栈匹配。

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);  // 最后栈为空才全部匹配
}

表达式求值

表达式求值通常分为两步：中缀转后缀，再后缀求值。

中缀转后缀：利用栈保存运算符，遵循优先级规则：

  1. 操作数直接输出
  2. 左括号入栈
  3. 遇到运算符时，弹出栈中所有优先级不低于它的运算符，再入栈
  4. 右括号时，弹出直到左括号

后缀表达式求值：从左到右扫描，遇到操作数入栈，遇到运算符则弹出两个操作数计算结果后入栈。

例如中缀表达式 (a+b)*c 转后缀为 ab+c*。

其他应用

  • 函数调用：递归调用的函数栈帧管理
  • 递归实现：递归的本质就是栈
  • 浏览器的前进/后退：两个栈分别记录历史
  • 编辑器的撤销/重做：两个栈保存操作记录

习题

习题 1

举例说明栈的典型应用。

答案与解析

栈的典型应用包括：表达式求值（中缀转后缀、后缀求值）、括号匹配、函数调用与递归实现、浏览器的前进后退、编辑器的撤销重做等。

习题 2

如何利用栈检查一个字符串中的括号是否匹配？请简述算法思想。

答案与解析
  1. 初始化一个空栈；
  2. 从左到右扫描字符串：遇左括号（(、[、{）入栈；
  3. 遇右括号（)、]、}）时，若栈空则匹配失败，否则弹出栈顶元素与之匹配，若不配对则失败；
  4. 扫描结束后，若栈为空则全部匹配成功，否则存在未匹配的左括号。

时间复杂度 O(n)O(n)，空间复杂度 O(n)O(n)。

上一章节链式栈链式栈的存储结构、入栈出栈操作与复杂度。
下一章节总结栈的术语对照与核心要点总结。
数据结构