如何用栈判断括号是否有效匹配？

简化版

用一个栈：遍历字符串，遇到左括号就入栈，遇到右括号就看栈顶的左括号是否与它配对——配对则弹出继续，不配对（或栈为空）则无效。遍历结束后栈必须为空才算全部匹配。核心是栈的「后进先出」正好对应括号「最近打开的最先闭合」。

详细版

题目：给定只含 ()[]{} 的字符串，判断括号是否有效（每个左括号有对应右括号、且嵌套顺序正确）。

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> pair = Map.of(')', '(', ']', '[', '}', '{');
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);                     // 左括号入栈
        } else {
            // 右括号：栈空 或 栈顶不匹配 → 无效
            if (stack.isEmpty() || stack.pop() != pair.get(c)) return false;
        }
    }
    return stack.isEmpty();                     // 栈空才说明全部配对
}

三种失败情形：① 右括号来了但栈空（没有左括号可配）；② 栈顶左括号和右括号类型不符；③ 遍历完栈还有剩（有左括号没闭合）。

完整版教学

一、为什么这题非用栈不可

括号匹配的本质是**「最近打开的括号，必须最先闭合」**——这正是后进先出（LIFO）。例如 ([{}])：最内层的 {} 先闭合，然后 []，最后 ()，闭合顺序和打开顺序完全相反。栈的 LIFO 特性天然表达这种「就近配对、逆序闭合」的嵌套关系，所以是最贴合的工具。

二、算法逐步走一遍

s = "([)]"
'(' 入栈  → 栈: (
'[' 入栈  → 栈: ( [
')' 右括号，栈顶是 '['，期望是 '(' → 不匹配，返回 false ✓（确实无效）

s = "([])"
'(' 入栈  → ( 
'[' 入栈  → ( [
']' 栈顶 '[' 匹配，弹出 → (
')' 栈顶 '(' 匹配，弹出 → 空
结束，栈空 → true

三、三个必须处理的边界

右括号时栈为空：说明这个右括号没有对应的左括号，直接无效。漏判会在 pop 空栈时报错。
类型不匹配：( 不能被 ] 闭合，弹出栈顶后要比对类型。
结束时栈非空：还有左括号没被闭合（如 (((），也是无效。很多人只判前两条，忘了最后 return stack.isEmpty()。

四、常见变体

只有一种括号（如只有 ()）：可以不用栈，用一个计数器 count：遇 ( 加一、遇 ) 减一，中途 count < 0 或结束非 0 就无效。但多种括号必须用栈，计数器无法判断类型嵌套是否正确（([)] 计数正确但实际无效）。
最长有效括号长度：进阶题，栈里存下标来计算有效子串长度。
使括号有效的最少增删：贪心/栈计数。

五、复杂度

时间 O(n)：每个字符进出栈各一次。
空间 O(n)：最坏全是左括号，全部入栈。

六、常见误区与追问

当前字符	栈操作	失败条件
左括号	入栈对应右括号或左括号	无
右括号	和栈顶匹配后弹出	栈空或类型不匹配
扫描结束	栈应为空	栈非空说明有未闭合左括号

记忆钩子：括号匹配看的是“最近打开的括号最先关闭”，这正是栈的后进先出。

以字符串 ([{}]) 为例，依次压入 (、[、{，遇到 } 时必须匹配最近的 {，再匹配 ] 和 )。如果是 ([)]，遇到 ) 时栈顶是 [，类型不匹配，立即失败。长度为 6 的合法串每个字符最多入栈或出栈一次，所以时间 O(n)，栈空间最坏 O(n)。

误区：左右括号数量相等就合法。 ([)] 数量相等但顺序交叉，仍然非法。
误区：遇到右括号时栈空可以忽略。 栈空说明没有对应的左括号，必须立即判 false。
误区：扫描完不用检查栈是否为空。 栈里剩左括号说明没有闭合，例如 (([])。
追问：为什么不用队列？ 需要匹配最近打开的括号，队列会先取最早打开的括号，顺序不对。
追问：可以压左括号还是压期望的右括号？ 两种都可以；压期望右括号能让匹配时直接比较当前字符和栈顶。
追问：如果加入星号通配符怎么办？ 那是更复杂的有效括号变体，通常需要贪心维护可能的未闭合数量范围或用栈分别记录位置。

七、加强记忆

括号匹配用栈：左括号入栈，右括号和栈顶配对（配对弹出、不配或栈空则无效），遍历完栈必须为空。因为「最近打开的最先闭合」就是后进先出。三个坑：右括号遇空栈、类型不匹配、结束时栈还有剩。单一种括号可用计数器，多种括号必须用栈。O(n) 时间和空间。

简化版

详细版