01 栈的基础应用：括号匹配、最长有效括号与逆波兰表达式

栈的基础应用：括号匹配、最长有效括号与逆波兰表达式

摘要

本篇从栈最经典的三道题入手，建立对”栈解题思维”的基础认知。LeetCode 20（Valid Parentheses）是栈的入门题，用栈匹配括号对；LeetCode 32（Longest Valid Parentheses）是”下标栈”技巧的典范，要求在 $O(n)$ 时间内求出最长合法括号子串的长度；LeetCode 150（Evaluate Reverse Polish Notation）演示了栈在表达式求值中的核心作用。三道题难度递进，覆盖了栈在实际工程中最常见的两类用途：符号匹配与表达式计算。

---

第 1 章 理解栈：为何是后进先出

1.1 栈的本质

栈（Stack）是一种线性数据结构，核心操作只有三个：

• push(x)：将元素 x 压入栈顶
• pop()：移除并返回栈顶元素
• peek()：查看栈顶元素但不移除

约束很简单：只能从一端（栈顶）操作。这个约束看起来是限制，但恰恰让栈天然适合”最近操作优先处理”的场景。

典型场景：

• 函数调用栈（每次调用把帧压栈，返回时弹栈）
• 编辑器的撤销（Ctrl+Z）历史（最近的操作最先被撤销）
• 编译器括号匹配（最近打开的括号最先被关闭）
• 深度优先搜索（DFS）的递归实现（调用栈本身就是一个栈）

1.2 Java 中使用哪种栈

Java 中有多种栈的实现：

// 方式 1：Stack<T>（老式，线程安全但性能差，不推荐）
Stack<Character> stack = new Stack<>();
 
// 方式 2：Deque<T> 用 ArrayDeque 实现（推荐）
Deque<Character> stack = new ArrayDeque<>();
stack.push('a');    // 压入（等同于 addFirst）
stack.pop();        // 弹出（等同于 removeFirst）
stack.peek();       // 查看栈顶
stack.isEmpty();    // 判空

为什么推荐 ArrayDeque 而不是 Stack？

Stack<T> 继承自 Vector<T>，每个操作都加了 synchronized 锁，在单线程场景下有不必要的性能开销。ArrayDeque 基于动态数组实现，无同步开销，且内存布局更紧凑（数组 vs 链表的缓存局部性差异）。官方 Javadoc 明确推荐：“This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.”

Deque 作为栈的操作命名

用 Deque 当栈时，用 push/pop/peek（操作头部），语义清晰。也可以用 addFirst/removeFirst/peekFirst，效果完全相同。避免混用 addLast/offerLast，那会让代码的意图变得模糊。

---

第 2 章 LeetCode 20：有效的括号

2.1 题目

LeetCode 20 - Valid Parentheses（简单）

给定一个只包含 (、)、{、}、[、] 的字符串 s，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合
2. 左括号必须以正确的顺序闭合
3. 每个右括号都有一个对应的相同类型的左括号

输入: "()"       → true
输入: "()[]{}"   → true
输入: "(]"       → false
输入: "([)]"     → false
输入: "{[]}"     → true
输入: "["        → false（未闭合）

2.2 为什么栈是自然选择

括号匹配的核心性质：最近打开的括号最先被关闭。这正是 LIFO 的语义。

分析 "{[()]}" 的处理过程：

i=0: '{' → 左括号，压栈 → 栈: ['{']
i=1: '[' → 左括号，压栈 → 栈: ['{', '[']
i=2: '(' → 左括号，压栈 → 栈: ['{', '[', '(']
i=3: ')' → 右括号，与栈顶 '(' 匹配，弹栈 → 栈: ['{', '[']
i=4: ']' → 右括号，与栈顶 '[' 匹配，弹栈 → 栈: ['{']
i=5: '}' → 右括号，与栈顶 '{' 匹配，弹栈 → 栈: []
最终栈为空 → true

任何一步弹栈时”栈顶与当前右括号不匹配”，或者最终”栈不为空”，都是无效。

2.3 代码实现

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            // 左括号：压栈
            stack.push(c);
        } else {
            // 右括号：检查栈顶是否是对应的左括号
            if (stack.isEmpty()) return false; // 右括号多余
            char top = stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    
    // 栈为空说明所有左括号都被匹配了
    return stack.isEmpty();
}

两个边界情况：

1. ")" 或 "]" 等：遇到右括号时栈已为空，需要 if (stack.isEmpty()) return false
2. "(((" 等：遍历结束后栈不为空，需要 return stack.isEmpty()

另一种写法：用哈希表建立映射关系，代码更简洁但可读性稍差：

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> map = Map.of(')', '(', ']', '[', '}', '{');
    
    for (char c : s.toCharArray()) {
        if (!map.containsKey(c)) {
            stack.push(c); // 是左括号，压栈
        } else {
            // 是右括号，检查栈顶
            if (stack.isEmpty() || stack.pop() != map.get(c)) return false;
        }
    }
    return stack.isEmpty();
}

复杂度：时间 $O(n)$，空间 $O(n)$（最坏全是左括号时栈满）。

---

第 3 章 LeetCode 32：最长有效括号

3.1 题目

LeetCode 32 - Longest Valid Parentheses（困难）

给你一个只包含 ( 和 ) 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

输入: s = "(()" → 输出: 2（最长有效括号子串是 "()"）
输入: s = ")()())" → 输出: 4（最长有效括号子串是 "()()"）
输入: s = "" → 输出: 0

3.2 关键洞察：下标栈而非字符栈

LeetCode 20 压入字符，但 LeetCode 32 需要知道匹配括号的位置才能计算长度。因此改为压入下标。

核心技巧：栈底始终保存一个”哨兵下标”——上一个未被匹配的右括号的下标（初始时压入 -1）。每次完成一次成功匹配，以”当前下标 - 栈底下标”计算当前合法长度。

详细过程（s = ")()()"）：

初始栈: [-1]（哨兵）

i=0, ')':
  栈顶是 -1，不是左括号下标，直接弹出哨兵，压入新哨兵 0
  栈: [0]

i=1, '(':
  左括号，压入下标 1
  栈: [0, 1]

i=2, ')':
  弹出 1（与 '(' 匹配），栈顶变为 0（哨兵）
  合法长度 = 2 - 0 = 2，maxLen = 2
  栈: [0]

i=3, '(':
  左括号，压入下标 3
  栈: [0, 3]

i=4, ')':
  弹出 3（与 '(' 匹配），栈顶变为 0（哨兵）
  合法长度 = 4 - 0 = 4，maxLen = 4
  栈: [0]

结果: 4 ✓

关键规则：

• 遇到 (：压入下标
• 遇到 )：弹出栈顶
  • 若弹出后栈变空：说明这个 ) 是”孤立的右括号”，压入它的下标作为新哨兵（更新”未匹配区域”的起点）
  • 若弹出后栈非空：合法长度 = i - 当前栈顶下标（栈顶是最近的哨兵或未匹配左括号）

3.3 代码实现

public int longestValidParentheses(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1); // 初始哨兵
    
    int maxLen = 0;
    
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i); // 左括号压下标
        } else {
            stack.pop(); // 弹出栈顶（可能是匹配的 '(' 或哨兵）
            if (stack.isEmpty()) {
                stack.push(i); // 孤立右括号成为新哨兵
            } else {
                maxLen = Math.max(maxLen, i - stack.peek()); // 计算长度
            }
        }
    }
    
    return maxLen;
}

手动验证（s = "(()"）：

栈初始: [-1]

i=0, '(': 压入 0 → [-1, 0]
i=1, '(': 压入 1 → [-1, 0, 1]
i=2, ')':
  弹出 1 → [-1, 0]
  栈非空，length = 2 - 0 = 2，maxLen=2

结果: 2 ✓

3.4 其他解法对比

方法 2：动态规划（空间 $O(n)$，无需栈）

public int longestValidParentheses(String s) {
    int n = s.length();
    int[] dp = new int[n]; // dp[i] = 以 s[i] 结尾的最长有效括号长度
    int maxLen = 0;
    
    for (int i = 1; i < n; i++) {
        if (s.charAt(i) == ')') {
            if (s.charAt(i - 1) == '(') {
                // s[i-1]='(' 直接与 s[i]=')' 匹配
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (dp[i - 1] > 0) {
                // s[i-1]=')' 且 dp[i-1]>0，找 s[i-1] 这段有效串左边的字符
                int j = i - dp[i - 1] - 1; // 有效串左边界的前一个字符
                if (j >= 0 && s.charAt(j) == '(') {
                    dp[i] = dp[i - 1] + 2 + (j >= 1 ? dp[j - 1] : 0);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
    }
    return maxLen;
}

方法 3：双向计数（空间 $O(1)$）

左右各扫一遍，统计 ( 和 ) 的个数，当两者相等时更新最大长度。细节处理较多，但空间最优。

方法	时间	空间	直觉难度
下标栈	$O(n)$	$O(n)$	中
DP	$O(n)$	$O(n)$	高
双向计数	$O(n)$	$O(1)$	高

面试推荐下标栈：思路最清晰，容易讲清楚，实现不易出错。

---

第 4 章 LeetCode 150：逆波兰表达式求值

4.1 什么是逆波兰表达式

逆波兰表达式（Reverse Polish Notation，RPN）又叫后缀表达式——操作符放在两个操作数的后面，而不是中间。

中缀表达式:  3 + 4         → 逆波兰: 3 4 +
中缀表达式:  (2 + 3) * 4   → 逆波兰: 2 3 + 4 *
中缀表达式:  5 - (1 + 2) * 4 + 3 → 逆波兰: 5 1 2 + 4 * - 3 +

逆波兰表达式的最大优势是不需要括号来表示优先级——因为操作符直接作用于它前面的两个操作数，优先级由操作符的位置天然决定。这是 HP 计算器在 1970 年代的设计选择（至今 HP 部分科学计算器仍默认 RPN 输入）。

4.2 题目

LeetCode 150 - Evaluate Reverse Polish Notation（中等）

根据逆波兰表示法，求表达式的值。有效的算符包括 +、-、*、/。除法向零截断。

输入: tokens = ["2","1","+","3","*"] → 输出: 9
     计算: ((2+1)*3) = 9
输入: tokens = ["4","13","5","/","+"] → 输出: 6
     计算: (4+(13/5)) = 6
输入: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
     → 输出: 22

4.3 求值算法

逆波兰求值是栈的教科书级应用：

• 遇到数字：压栈
• 遇到运算符：弹出两个操作数，计算结果，再将结果压栈
• 最终栈中唯一的元素即为答案

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (String token : tokens) {
        if (isOperator(token)) {
            int b = stack.pop(); // 第二个操作数（后入栈）
            int a = stack.pop(); // 第一个操作数（先入栈）
            switch (token) {
                case "+": stack.push(a + b); break;
                case "-": stack.push(a - b); break;
                case "*": stack.push(a * b); break;
                case "/": stack.push(a / b); break; // Java 整除自动向零截断
            }
        } else {
            stack.push(Integer.parseInt(token));
        }
    }
    
    return stack.pop();
}
 
private boolean isOperator(String s) {
    return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
}

弹出顺序很重要

弹栈顺序：先弹出的是右操作数（b），后弹出的是左操作数（a）。减法和除法是非交换的（a - b ≠ b - a），必须注意顺序。

例：tokens = ["5", "3", "-"] → 预期结果是 5 - 3 = 2

• 先压 5，再压 3
• 遇到 -，先弹 b=3，再弹 a=5，计算 a - b = 5 - 3 = 2 ✓

手动验证（tokens = ["4","13","5","/","+"]）：

"4"  → stack: [4]
"13" → stack: [4, 13]
"5"  → stack: [4, 13, 5]
"/"  → b=5, a=13, 13/5=2, stack: [4, 2]
"+"  → b=2, a=4, 4+2=6, stack: [6]

结果: 6 ✓

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

4.4 为何逆波兰求值如此简单

中缀表达式的求值困难之处在于需要处理运算符优先级（先算乘除，再算加减）和括号（改变优先级）。这两件事在人类阅读时很直观，但对计算机而言需要两次扫描或使用调度场算法（Shunting Yard Algorithm）。

逆波兰表达式把优先级的信息编码进了操作符的位置，计算机只需从左到右扫描一遍，用一个栈就能完成求值——时间和空间都是线性的。

这也是为什么编译器在生成代码或中间表示（IR）时，通常将表达式转换成类似后缀形式（如 Three-Address Code）来处理的原因。

中缀转逆波兰：调度场算法

Dijkstra 的调度场算法（Shunting Yard Algorithm）可以将中缀表达式转换为逆波兰表达式，同样只需 $O(n)$ 时间和一个栈。LeetCode 224（基本计算器） 的一种解法就是先用调度场算法转换，再用 RPN 求值。

---

第 5 章 三道题的思维模式总结

5.1 括号题的通用解题框架

遇到括号类题目，先问自己三个问题：

问题 1：我需要追踪什么信息？

• LeetCode 20：只需知道”最近的未匹配左括号是什么类型” → 压字符
• LeetCode 32：需要知道”匹配发生在哪个位置” → 压下标

问题 2：弹栈的时机是什么？

• 遇到右括号时，弹出对应的左括号（或哨兵）

问题 3：弹栈后如何更新答案？

• LeetCode 20：弹出后判断是否匹配
• LeetCode 32：弹出后用”当前下标 - 新栈顶下标”计算长度

问题 4：什么情况下需要压入”哨兵”？

• 当需要计算长度时（LeetCode 32）：遇到孤立右括号时更新哨兵
• 哨兵的本质是”有效子串的左边界的前一个位置”

5.2 表达式求值的栈模式

遇到什么	操作
数字	压栈
运算符（双目）	弹出两个操作数，计算，压入结果
(	压栈（作为特殊标记）
)	弹栈直到遇到 (，计算括号内的结果

逆波兰表达式已经消除了括号，所以只需要数字和运算符的处理。带括号的中缀表达式求值（LeetCode 224）需要额外处理 ( 和 ) 的逻辑，见 07 字符串嵌套解码与基本计算器。

---

下一篇预告

02 栈的设计题：最小栈与用队列模拟栈 进入栈的”设计类”题目。LeetCode 155（最小栈）要求在 $O(1)$ 时间内查询栈中最小值，关键是用一个”辅助最小值栈”同步追踪；LeetCode 225（用队列实现栈）考察用两个 FIFO 队列模拟 LIFO 栈——理解这道题能加深对两种数据结构差异的认知。