有效的括号：编译器闸机如何检查括号是否闭合？

栈不是为了存数据，而是为了记住『最近还没关闭』的左括号。

给一段只含 () [] {} 的字符串，判断它是否“合法配对”。难点不在数量，而在顺序——([)] 数量一样多，可它就是 false。本页用『编译器安检闸机』把栈 / LIFO 的几何意义画清楚。

栈 · LIFO一次扫描时间 O(n)空间 O(n)

人话版

每看到一个左括号，就像打开一扇门；每看到一个右括号，就必须关闭最近打开的那扇门。

机器版

左括号 push；右括号检查 stack top；匹配则 pop，不匹配直接 false；最后 stack 必须为空。

反例版

([)] 数量看起来对，但 ) 出现时，最近未关闭的是 [，所以顺序错了。

测试用例 · 切换后整段轨迹会重算

当前预期：false· 数量配平，但 ) 来时栈顶是 [，类型/顺序都错

帧 1/4

当前步骤

传送带准备就绪

发生了什么: 字符串 "([)]" 进入安检通道。指针指在第一个字符之前。
为什么这么判: 从左到右逐字符扫描；扫描器只看『当前』和『栈顶』，无需回头。
不变量: 扫描开始前栈为空。

输入「([)]」扫描下标 -栈 [—]

不变量 · Invariants

I1栈中自底向上 = 尚未关闭的左括号，按打开顺序排列。
I2右括号到来时，最近一次打开的同型左括号必然在栈顶。
I3栈空时收到右括号 ⇒ 无门可关 ⇒ 必然 false。
I4扫完后栈非空 ⇒ 仍有遗留开门 ⇒ 必然 false。

左括号 token（开门牌）右括号 token（关门牌）匹配成功失败 / 报警已扫描

输入「([)]」传送带准备就绪

Go 代码 · 同步高亮

intro

1func isValid(s string) bool {
2    stack := []rune{}
3    pairs := map[rune]rune{
4        ')': '(',
5        ']': '[',
6        '}': '{',
7    }
8 
9    for _, ch := range s {
10        if ch == '(' || ch == '[' || ch == '{' {
11            stack = append(stack, ch)
12            continue
13        }
14 
15        if len(stack) == 0 {
16            return false
17        }
18 
19        top := stack[len(stack)-1]
20        if top != pairs[ch] {
21            return false
22        }
23 
24        stack = stack[:len(stack)-1]
25    }
26 
27    return len(stack) == 0
28}

注意三条独立 return： len(stack) == 0 → false（空栈遇右）、 top != pairs[ch] → false（类型错乱）、最终 len(stack) == 0（扫完是否清空）。任何一条 false 都不能漏，否则就掉进 ([)] 这类陷阱。

为什么是栈

括号的关闭顺序是 LIFO ——最后打开，最先关闭。这与栈“最后压入的元素最先弹出”的行为完全一致。所以右括号只需要 O(1) 地看一眼栈顶，就能判断是否合法，整个算法 O(n)。

如果用计数器替代：cnt 加加减减只能查数量，看不到类型，所以 ([)] 会被误判成 true——这是这题最常见的陷阱。

数量正确 ≠ 顺序正确

错觉：只数数量counter only

([)] 里 ( = ) 各 1 个、[ = ] 各 1 个，计数器最终会回到 0——错误地判为 true。

正解：栈记顺序stack · LIFO

扫到 ) 时栈顶是 [，类型不符 ⇒ 立刻 false。栈天然记录了「最近一次还没关」的那扇门是谁。

QA 自检 · 5 个用例的判决

输入	扫描事件	最终判决
([)]	类型不匹配	false（[ ≠ 期望 (）
()[]{}	扫完，栈空	true
({[]})	扫完，栈空	true
(((	扫完，栈非空	false（栈非空）
){	空栈遇右括号	false（空栈遇 )）

每行都是动画播完最后一帧的事件类型 + 对应的 false 原因——直接对应 Go 代码里那条 return 的来源。