Appearance
括号匹配：一个栈走一遍
本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。括号匹配是「栈的应用」这一考点的代表题，也是理解栈「后进先出」如何解决「就近配对」问题的最佳例子。它是经典训练题，不是真题，也不押题。
题目
给定一个只含 (、)、[、]、{、} 六种括号的字符串，判断它是否「有效」：每个左括号都能找到类型匹配的右括号，且嵌套顺序正确。例如 ([{}])[] 有效，([)] 无效（交叉嵌套），((( 无效（有左无右）。设计算法返回是否有效。
这道题没有「尽可能高效」的要求。按拓展训练导语的分类，它属于「直观即满分」型——直白写法就是最优解，力气花在把判定写准上。
直观解法：一个栈,一趟扫描
括号匹配的核心矛盾是「就近配对」：一个右括号，必须和离它最近、还没配对的那个左括号匹配。「最近、还没处理」正是栈的「后进先出」——遇到左括号就压栈，遇到右括号就和栈顶的左括号比对。
c
#include <string.h>
int isValid(char s[]) {
int n = strlen(s);
char stack[n + 1]; // 用数组模拟栈，最多压 n 个
int top = -1; // 栈顶指针，-1 表示空栈
for (int i = 0; i < n; i++) {
char c = s[i];
if (c == '(' || c == '[' || c == '{') {
stack[++top] = c; // 左括号：入栈
} else {
// 右括号：栈空 或 栈顶与之不配对，都判无效
if (top == -1) return 0;
char t = stack[top];
if ((c == ')' && t != '(') ||
(c == ']' && t != '[') ||
(c == '}' && t != '{')) return 0;
top--; // 配对成功，弹栈
}
}
return top == -1; // 全部配对完，栈必须为空
}拿 ([)] 走一遍：( 入栈、[ 入栈；遇到 )，栈顶是 [ 不是 (，立刻判无效——正确识别出交叉嵌套。再拿 ((( 走一遍：三个左括号全入栈，扫描结束时栈非空，返回无效。
复杂度：扫描字符串一遍，每个字符做常数次栈操作，时间
为什么它就是满分解
这道题没有「暴力 vs 最优」的分差。用总纲的「找浪费三问」审一遍，三问全部答「没有」：
- 有没有重复扫描？ 没有。每个字符只进出栈一次，读过就不再回头。
- 有没有重算已知的东西？ 没有。栈顶永远是「当前最近的未配对左括号」，需要它时直接取，不用重新查找。
- 有没有放着性质不用？ 没有。题目要的「就近配对」性质，正好被栈的 LIFO 结构直接承载。
更根本的一条：判断括号是否匹配，至少要把每个字符看一遍——读一遍字符串就是
真正的难点在三处判定
分不在优化上，在把三处边界判准：
- 右括号遇到空栈,立即无效。
)来了但栈里没有等待配对的左括号（比如字符串)(），说明这个右括号没有对象，直接返回无效。漏了这个判断会对空栈做弹栈操作,下标越界。 - 类型必须匹配,不只是「有就行」。
(只能配),不能配]。这正是([)]被判无效的关键——不检查类型的话,它会被错误地当成有效。 - 扫描结束后栈必须为空。所有右括号都配对成功、循环正常走完,不代表有效——可能还有左括号留在栈里没人配（如
(((）。最后一定要检查top == -1。漏了它,(((会被误判为有效。
三处判定各守一种非法情形：右括号多了、类型错了、左括号多了。少任何一个,都有一类无效字符串会蒙混过关。
一个栈走一遍,看一遍
用 ([)]（无效,交叉嵌套）演示——(、[ 依次入栈,遇到 ) 时栈顶是 [、类型不匹配,当场判无效:
演示为 JavaScript 版本，逻辑与上文 C 代码一一对应（演示驱动用的是有效串
([{}])[],可自行改成([)]观察失配即停）。
别画蛇添足
这道题结构简单,过度设计的空间不大,但有两个常见的「想复杂了」：
- 想用计数器代替栈。只数左右括号数量是否相等——对单一种类括号也许能蒙混,但一遇到
([)]就露馅：左右括号各 2 个、数量相等,却是无效的。嵌套顺序的信息,计数器丢掉了,只有栈能保住。 - 想一次处理多种规则。括号匹配只管配对,别顺手去校验别的（表达式是否合法、运算符位置等）——那是另一道题。把这道题的边界收在「配对」上,反而写得又快又稳。
下一步
- 看栈处理括号匹配的交互演示：括号匹配可视化
- 同属「栈的应用」的拓展题：逆波兰表达式求值、中缀表达式转后缀
- 回到方法论源头：「暴力解到最优解」真题专题总纲