栈的应用：括号匹配与表达式求值

有效的括号（20）：三种不匹配情形

括号匹配是栈的成名之作，但很多人第一次写只考虑了一种错误。一个括号串不合法，恰恰只有三种情形，写代码前先把它们一一列举，思路就闭环了：

情形	举例	栈的表现
① 右括号多了	`"(][]"`、`")("`	找配对时栈已空，或栈顶对不上
② 类型不匹配	`"[{]}"`	栈顶不是期望的左括号
③ 左括号多了	`"(()"`、`"(){"`	字符串扫完了，栈里还剩东西

思路：遇到左括号就压栈；遇到右括号时，检查栈顶是否是对应的左括号——是则弹出继续，否则立即返回 false。字符串遍历结束后，栈必须恰好为空才合法（防情形③）。

实现上有个省事技巧：遇到左括号时不压左括号本身，而是压入它对应的右括号。这样遇到右括号时只需判断"当前字符是否等于栈顶"，省掉一堆映射分支：

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(') stack.push(')');      // 压对应的右括号
        else if (c == '[') stack.push(']');
        else if (c == '{') stack.push('}');
        // 情形①：右括号多了，栈空没法配对
        // 情形②：栈顶不是它想要的那个右括号
        else if (stack.isEmpty() || stack.pop() != c) return false;
    }
    // 情形③：左括号多了，栈里还有剩余
    return stack.isEmpty();
}

三个分支恰好对应三种失败情形，逐一用 "(()" "、"[{]}"、")(" 手动模拟一遍，比背代码可靠得多。

删除字符串中的所有相邻重复项（1047）

题目：字符串里两个相邻且相同的字母要一起删掉，删除后左右两边可能又拼出新的相邻对，删到不能再删。例如 "abbaca" → "ca"。

用栈模拟这个过程再自然不过：遍历字符，若与栈顶相同就弹出（一对一起消失），否则压栈。遍历结束后栈里剩下的就是删不动的结果。

public String removeDuplicates(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (!stack.isEmpty() && stack.peek() == c) {
            stack.pop();        // 与栈顶相邻且相同，一起消除
        } else {
            stack.push(c);      // 暂存，等后面的字符来匹配
        }
    }
    // 栈底到栈顶才是原顺序，弹出顺序是反的，拼接时反转
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) sb.append(stack.pop());
    return sb.reverse().toString();
}

两个易错点：一是出栈拼字符串顺序是反的，最后要 reverse()；二是注意 "abba" 这种对称嵌套（bb 消掉后 a a 拼成新邻居）也能被正确处理——因为栈保存了"还没被消除的左侧字符序列"，右侧信息天然由遍历顺序提供。用 StringBuilder 直接当栈写也可以，append 是压栈、检查末尾字符是查栈顶、deleteCharAt 是弹栈，最后免反转。

逆波兰表达式求值（150）

逆波兰表达式（后缀表达式）把运算符写在操作数后面：["2","1","+","3","*"] 表示 (2 + 1) * 3 = 9。它的好处是不需要括号、不需要优先级，运算顺序完全由位置决定——这正是编译器处理后缀表达式、以及栈发挥作用的地方。

求值规则一句话：遇到数字压栈；遇到运算符，弹出两个数计算，把结果压回栈。

最容易错的地方是操作数顺序：先弹出的是右操作数，后弹出的是左操作数：

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String t : tokens) {
        switch (t) {
            case "+": {
                int b = stack.pop(), a = stack.pop();  // 先弹右，后弹左
                stack.push(a + b);
                break;
            }
            case "-": {
                int b = stack.pop(), a = stack.pop();
                stack.push(a - b);   // a - b，别写成 b - a
                break;
            }
            case "*": {
                int b = stack.pop(), a = stack.pop();
                stack.push(a * b);
                break;
            }
            case "/": {
                int b = stack.pop(), a = stack.pop();
                stack.push(a / b);   // a / b，整数除法向零截断
                break;
            }
            default:
                stack.push(Integer.parseInt(t));  // 是数字，入栈
        }
    }
    return stack.pop();
}

自测方法很简单：拿 ["4","13","5","/","+"] 走一遍——弹 5 和 13 算 13 / 5 = 2，再弹 2 和 4 算 4 + 2 = 6。如果把操作数顺序写反，- 和 / 立刻出错，+ 和 * 却碰巧不错，这种 bug 很隐蔽，务必注意。

心智模型：最近匹配，就近消除

把三道题摆在一起，会发现它们共享同一个模型：

题目	"了断"发生在	配对成功后
20 有效的括号	右括号 vs 栈顶左括号	双方一起出局
1047 相邻重复项	当前字符 vs 栈顶字符	双方一起出局
150 逆波兰求值	运算符 vs 栈顶两个数	三个数换一个结果

栈在这里扮演的角色是：保存所有"还在等一个交代"的元素，且最新的排在最前面。当前元素进来，只和"最近的那位"发生关系——能了断就出结果，了断不了自己进栈排队。这和递归调用栈、括号作用域、浏览器前进后退是同构的。

判断什么时候该想到栈，问自己两个问题：

处理当前元素时，是否只需要关心最近出现的若干元素？（是 → 栈）
当前元素与最近的元素发生关系后，是否会让更早的元素重新暴露出来参与判断？（是 → 必须用栈，数组做不到回退）

反过来，如果每个元素只处理一次、互不影响（比如求和、计数），用一个变量或哈希表就够了，别硬套栈。

LeetCode 题单

题号	题名	一句话考点
20	有效的括号	三种不匹配情形全覆盖：空栈、不匹配、剩余
1047	删除字符串中的所有相邻重复项	栈顶相等即消除，注意结果顺序反转
150	逆波兰表达式求值	弹两个数先右后左，注意减法除法顺序
227	基本计算器 II	中缀表达式，用栈处理加减暂存乘除
224	基本计算器	括号嵌套 + 正负号，栈存括号前的符号
388	文件的最长路径	栈按深度存路径前缀，回退用弹栈
71	简化路径	栈处理目录的进与退，`..` 对应弹出

其中 227/224 可以看作 150 的进阶：中缀表达式先按优先级拆解成栈上的"部分和"，本质上还是"遇到能了断的运算符就结算"。

参考

代码随想录 · 栈与队列专题