做这道题之前，我建议你先别急着敲代码，把题目多读两遍。某高校的程序设计实训作业里，这道“合法的括号串”属于典型的栈结构入门题，但它的坑远比你想象的多。题目名字已经剧透了答案——用堆栈，可很多同学看完题还是不知道栈到底怎么用，代码写到一半又回头去看课件。问题不在智商，在于没把“括号匹配”这个词翻译成具体的数据操作。这篇文章就把这个翻译过程掰开揉碎讲清楚，从题目理解到代码实现，再到测试用例和隐蔽的坑，一次性讲透。
1. 题目到底在考什么——先看清问题本质
1.1 原题要求拆解
题目描述通常长这样：输入一个只包含括号字符的字符串，判断括号是否全部正确匹配。合法串的含义是：每一个左括号都能在合适的位置找到一个类型相同的右括号关闭，并且括号不能交叉嵌套。举个例子，( [ ) ]虽然每类括号都出现了两次，但它是非法的，因为[被)关闭了，而不是被]关闭，括号之间发生了交叉。
原题一般会声明输入字符串只包含六种字符：()[]{}，有些简化版只有(和)两种。要求输出YES（合法）或NO（非法）。题目给定了“堆栈的使用”这个提示，等于告诉你：不用栈也能做，但用栈才是最规范的解法，也最符合这门课想训练的知识点。
这里要特别注意的是“空字符串”也算合法。实训题目如果有多组测试，读入时经常会读到空行，很多同学空串处理不当，直接导致误判。这个问题我在后面第 4 部分会专门讲。
1.2 为什么第一反应想到栈，而不是别的结构
很多同学的第一个思路是“计数”：数一数左括号有几个，右括号有几个，相等就合法。这种思路能解决()这种情况，但遇到)(这种字符串就废了——左右数量都是 1，实际上却是非法串。计数只能统计数量，完全无法表达“先出现左括号、后出现右括号”的顺序约束。
还有一种思路是“用队列”，但是队列先进先出的特性用在这里是错位的。括号匹配的本质是“就近匹配”：最早出现的左括号，要等最晚的右括号来处理，这正是栈的 LIFO（后进先出）特性。你在生活里可以这么类比：往一个弹簧文件夹里依次塞入几张纸，最先塞进去的那张被压在最底下，最后塞进去的反而最先被抽走。括号嵌套的逻辑和这个完全一样。
2. 栈的工作逻辑——LIFO与括号嵌套的天然对应
2.1 三种括号的匹配规则拆解
先把匹配规则说透。从左到右扫描字符串，碰到的每个字符只分两大类：
- 遇到左括号
([{，直接入栈； - 遇到右括号
)]}，先检查栈是否为空。如果栈空，说明没有左括号可以和它对应，立刻判定非法。如果栈不空，弹出栈顶元素，看它和当前右括号是不是同一类型。
为什么是“弹出栈顶”而不是“检查所有元素”？因为栈顶元素就是离当前右括号最近的未匹配左括号。合法串要求所有右括号必须关闭它左边最近的那个左括号，否则就可能出现交叉。以( [ ] )为例：处理]时栈顶是[，匹配成功；处理)时栈顶是(，也匹配成功。而( [ ) ]处理)时栈顶是[，类型对不上，立刻判定非法。
扫描完整个字符串之后，如果栈是空的，说明所有左括号都被右括号关闭了，这个串才合法；如果栈里还剩元素，说明存在没被关闭的左括号，非法。
2.2 用一个具体例子走一遍入栈出栈流程
拿{ [ ( ) ] }这个合法串走一遍完整流程，你就能直观看到栈的变化：
- 读入
{，入栈，栈：{ - 读入
[，入栈，栈：{ [ - 读入
(，入栈，栈：{ [ ( - 读入
)，栈顶是(，匹配，出栈，栈：{ [ - 读入
]，栈顶是[，匹配，出栈，栈：{ - 读入
}，栈顶是{，匹配，出栈，栈空 - 输入结束，栈空，输出
YES
再看一个非法串：( [ ) ]：
- 读入
(，入栈，栈：( - 读入
[，入栈，栈：( [ - 读入
)，栈顶是[，类型不匹配，输出NO - 后面的字符不用再看了，反正已经非法
通过这个手算过程，你会发现核心就两步：入栈和出栈。栈里存什么、什么时候存、什么时候弹、弹之前查什么，这就是全部逻辑。
2.3 三种栈实现的对比选择
实训作业里栈的实现方式主要有三种：数组模拟、C 标准库的链表实现、C++ 标准模板库的容器适配器。我不推荐在作业里直接用复杂写法，最稳妥的是数组模拟。
| 实现方式 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 数组模拟 | 代码直观，便于打印调试点，不依赖额外库 | 需要预先确定最大容量 | 算法题、实训作业首选 |
| 带头结点链表 | 空间动态分配，不受容量限制 | 代码量大，指针出错的概率高 | 数据结构课设，可以用来练链表 |
| C++ STL stack | 写起来最短，各类操作封装完毕 | 部分实训环境只允许纯 C | 平时练习、面试手写题 |
我第一次做这类题目选用的是数组模拟。理由很简单：栈的大小最多是字符串长度，直接开一个足够大的数组，用一个top变量指向栈顶位置，入栈就stack[top++] = c，出栈就是stack[--top]。这样写出来的代码短、好排查，而且你能亲手控制每一步，比调标准库更能理解栈的运作。
3. 完整代码实现——从思路到能直接交作业
3.1 主流程设计思路
写代码之前先把流程画清楚，这一段就是整个程序的骨架：
- 定义栈数组和栈顶指针；
- 循环读入字符串；
- 逐字符扫描；
- 遇到左括号入栈；
- 遇到右括号先判空、再弹栈检查类型；
- 扫描完毕后检查栈是否为空；
- 按照题目要求输出
YES或NO。
这里有个容易搞混的细节：top这个变量到底表示什么。我用它表示“栈内元素个数”，入栈时stack[top] = c; top++，出栈时top--; c = stack[top]。另一种常见写法是用top表示“栈顶元素下标”，初始化为-1。两种写法本身没有问题，但你必须在整个程序里保持一致，否则很容易出现“栈空判断错误”这种隐蔽 bug。
3.2 核心代码：数组模拟栈版本
下面是基于数组模拟栈的完整可提交代码，我用的是纯 C 语言，适配大多数实训环境：
#include <stdio.h> #include <string.h> #define MAXN 10005 char stack[MAXN]; int top; // 栈内元素个数 int isLeft(char c) { return c == '(' || c == '[' || c == '{'; } int isMatch(char left, char right) { if (left == '(' && right == ')') return 1; if (left == '[' && right == ']') return 1; if (left == '{' && right == '}') return 1; return 0; } int main() { char s[MAXN]; // 支持多组输入 while (fgets(s, MAXN, stdin) != NULL) { // 注意 fgets 会读入换行符，需要去掉 int len = strlen(s); while (len > 0 && (s[len - 1] == '\n' || s[len - 1] == '\r')) { s[len - 1] = '\0'; len--; } top = 0; // 每次重新初始化栈 int valid = 1; // 标记是否合法 for (int i = 0; s[i] != '\0'; i++) { char c = s[i]; if (c == ' ') continue; // 有些题目会混入空格，跳过就好 if (isLeft(c)) { stack[top++] = c; // 左括号入栈 } else { // 右括号：栈空则非法 if (top == 0) { valid = 0; break; } char left = stack[--top]; // 弹出栈顶左括号 if (!isMatch(left, c)) { // 类型不匹配则非法 valid = 0; break; } } } // 扫描完还要确认栈已空 if (valid && top == 0) printf("YES\n"); else printf("NO\n"); } return 0; }这段代码在逻辑上做了三个关键处理：空格跳过、空行处理、栈空判断。如果你确认题目不会出现空格和空串，可以把相关分支删掉，但保留它们能让代码更健壮。实训判题的隐藏数据往往就在这些边边角角里。
3.3 换成 STL 栈怎么写
如果实训环境允许 C++，用std::stack可以更简洁地表达核心逻辑：
#include <iostream> #include <stack> #include <string> using namespace std; bool isValid(string s) { stack<char> st; for (char c : s) { if (c == '(' || c == '[' || c == '{') { st.push(c); } else { if (st.empty()) return false; char top = st.top(); st.pop(); if (c == ')' && top != '(') return false; if (c == ']' && top != '[') return false; if (c == '}' && top != '{') return false; } } return st.empty(); }这里用isValid返回布尔值，主函数里循环读入字符串调用即可。STL 版本的好处是代码量小，容错率高，不容易犯数组越界的问题；坏处是你可能搞不清top()和pop()的顺序——必须先用top()取栈顶值，再用pop()弹出，顺序颠倒了逻辑就错。数组模拟栈的时候我们写char left = stack[--top]一步搞定，反而不会犯这个错。
3.4 核心代码的五个容易写错的位置
这道题代码量不大，但错误率不低，主要集中在五个位置：
第一，右括号处理顺序。必须先判空再弹栈，不能反过来。很多同学看到右括号就直接执行stack[--top]，如果栈是空的，top变成 -1，访问stack[-1]就是未定义行为，可能读到一个随机值，程序表现为“时对时错”。
第二，扫完字符串后忘记检查栈空。如果字符串是((()，扫描过程不会报错，但不检查栈空就会错误输出YES。这一步经常丢分。
第三，top的初始化位置。如果是多组输入，每次处理新字符串之前必须把top重新置 0，否则上一轮的残留数据会污染这一次的判断。
第四，类型不匹配的判断条件。比对时要分三种情况分别写，不能只判一个left == right，因为(和)在 ASCII 码上差 1，[和]差 2，{和}差 2，没有统一的数值规律可循。用封装好的isMatch函数逐个比较是更稳妥的做法。
第五，用fgets读取输入时，换行符会被读进字符串尾部。如果不处理，长度为 0 的空字符串实际会带一个'\n'，让len变成 1，而s[0]就是换行符，它既不是左括号也不是右括号，在循环中被直接跳过，最后栈空空输出YES。这个行为碰巧和空串合法一致，你不一定发现得了这个隐藏问题，但严谨起见还是应该去掉换行符。
4. 实操记录与边界测试
4.1 训练样例与手算模拟
我建议拿到代码之后，先不要直接提交，自己准备一组测试数据，把覆盖到的场景都跑一遍。下面这组测试是我当时用来验证程序的，你可以直接抄走：
| 输入 | 预期输出 | 覆盖场景 |
|---|---|---|
() | YES | 最基础的嵌套 |
()[]{} | YES | 三种括号并列 |
([{}]) | YES | 多层嵌套 |
(] | NO | 单层类型不匹配 |
([)] | NO | 括号交叉嵌套 |
((())) | YES | 多层同类型嵌套 |
((()) | NO | 左括号比右括号多 |
()) | NO | 右括号多余 |
)( | NO | 逆序括号，数量相等但非法 |
| 空串 | YES | 边界条件 |
每个用例跑完之后，最好在脑子里补充一次手动模拟，哪怕只是快速过一下栈的变化，也比对着输出结果硬猜好。比如([)]这个用例，手动模拟时会发现：[入栈后，遇到)时栈顶是[，直接判定非法，后面的字符不用处理了。这种“提前返回”的行为在代码里用的是break跳出循环，你要确认跳出之后不会再误判。
4.2 常见错误与排查速查表
我把实训中高频出现的报错现象和原因整理成一张速查表，遇到问题可以直接对照排查：
| 错误表现 | 大概率原因 | 对应修复方法 |
|---|---|---|
()输出 NO | top初始化错误或完成处理逻辑反了 | 检查top初始值，确认入栈出栈顺序 |
))输出程序崩溃 | 弹栈前没有判空 | 在stack[--top]前加if (top == 0) |
((输出 YES | 扫描完成后没检查栈空 | 末尾加if (top != 0) valid = 0; |
| 多组输入时后几组全错 | 栈顶top没有在组间重置 | 每次读入新串前top = 0; |
| 带空格的字符串判断错误 | 没有处理空格字符 | 增加空格跳过逻辑 |
| 读入空行后程序死循环 | fgets返回NULL时未处理 | while (fgets(...) != NULL) |
| 答案总与预期相反 | YES/NO输出顺序写反 | 核对主循环最后的条件分支 |
这些坑我都踩过，尤其“多组输入忘记重置 top”这个问题，我第一次做的时候栽了整整一个下午。当时现象很诡异：第一组数据对，第二组数据错，第三组又对。调试半天才发现是上一组数据残留的栈元素没有清空。
4.3 调试技巧：把栈打印出来看
遇到代码逻辑说不通的时候，我强烈建议在循环里临时加几行打印语句，把每一步的“当前字符”和“栈内元素”打出来：
for (int i = 0; s[i] != '\0'; i++) { char c = s[i]; // 调试输出，排查完记得删除 printf("扫描到 %c, 当前栈: ", c); for (int k = 0; k < top; k++) printf("%c ", stack[k]); printf("\n"); if (isLeft(c)) { stack[top++] = c; } else { if (top == 0) { valid = 0; break; } char left = stack[--top]; if (!isMatch(left, c)) { valid = 0; break; } } }打印出来之后，栈的变化轨迹一目了然。比如输入([)]，输出会清楚显示：遇到)时栈里是( [ ]，弹出的是[，类型不匹配，程序走到 break 分支。这种可视化调试特别适合初学者，比盯着代码发呆管用得多。记住调试完把打印语句删掉，否则提交时输出会混入调试信息，直接判错。
5. 变体扩展——一个题目吃透栈的“一招鲜”
5.1 只有一种括号时能不能用计数
原题如果简化成只包含(和)，很多同学会问：是不是用一个计数器就可以？计数器的方法其实是“伪栈”——用一个整数cnt记录当前“还没关闭的左括号数”，遇到(就cnt++，遇到)就cnt--，cnt为负或者扫描完cnt != 0就非法。这种情况下计数器和栈的行为完全等价，只是不用额外数组。
但有一个边界必须注意：不能用“左右总数相等”来代替这个过程。总数相等只能排除“数量不对称”的情况，无法排除“顺序交错”的情况。)(的数量是相等的，但它是非法的。这就是为什么计数法也要动态维护“当前未配对数”，而不是最后数总数。能想通这一点，你对栈的理解就会更深一层。
5.2 括号字符串里混入其他字符怎么办
实训题目一般不会混入普通字符，但真实场景和面试题里经常出现“字符串里既有括号又有字母数字”的情况。比如要判断"a(b)c[d]{e}"这样带普通字符的串。
处理方法其实很简单：扫描时遇到非括号字符直接跳过，不参与栈操作。前面的代码里我用if (c == ' ') continue;就是这个思路的简化版。真正写通用版本时，你可以判断当前字符是不是六种括号之一，不是就跳过。也就是说，这道题考的核心逻辑不变，变的只是“哪些字符进入栈”，普通字符对栈来说就是透明的。
5.3 进阶经典题：求最长合法括号子串长度
这是一个很著名的栈进阶题：给定一个只含(和)的字符串，要求返回最长的“合法括号子串”的长度。比如")()())"的最长合法子串是"()()"，长度是 4。
这类问题的核心是：栈里不能只存字符，还要存下标。你需要用下标来结算“从哪个位置开始到当前位置是一段完整合法区间”。参考写法如下：
int longestValidParentheses(string s) { stack<int> st; st.push(-1); // 哨兵，表示最早匹配起点之前 int maxLen = 0; for (int i = 0; i < (int)s.size(); i++) { if (s[i] == '(') { st.push(i); } else { st.pop(); if (st.empty()) { st.push(i); // 当前右括号成为新的哨兵 } else { maxLen = max(maxLen, i - st.top()); } } } return maxLen; }这里把下标入栈，st.top()就是“最后一个未匹配左括号的位置”，弹出它之后，当前位置和新的栈顶之差就是当前连续合法段的长度。这个解法和你实训作业的数组栈本质同源，只是栈里存的从“括号字符”换成了“字符位置”。有空把这题做了，你对栈的应用理解会有一个很大的提升。
5.4 栈还能解决哪些同类问题
括号匹配只是栈应用的冰山一角。能用到类似思路的场景还有不少：表达式求值中的运算符优先级处理、函数调用栈的实现原理、浏览器的前进后退记录、编辑器的撤销操作、深度优先搜索的非递归实现等。它们背后的模型都一样——需要暂时保存一批状态，并且后续访问时遵循“后进先出”。当你把“栈”不再当成一个名词，而是当成一个“能用数组加一个变量实现的机制”时，你会发现这些题目都是同一道题换了一身衣服。
我个人在实际操作中的体会是，这道“合法的括号串”之所以值得认真做透，是因为它强迫你真正理解栈的“先入栈、后出栈”和括号“先出现、后关闭”是同一个顺序关系的两面。做题的时候多问自己一句“为什么这里要弹栈而不是看其他元素”，比多刷十道模板题有用得多。最后再分享一个小经验：把上面那组测试用例保存成一个文本文件，每次改完代码直接重定向运行一遍，几分钟就能完成回归测试。这个习惯不只能省下提交后等待判题的时间，更能帮你把每一处修改的影响范围看得清清楚楚。
