栈的经典应用：合法括号串匹配原理与C语言实现

5.合法的括号串(堆栈的使用！)

提到数据结构入门，栈（Stack）几乎是每个学编程的人绕不开的第一个“有灵魂”的容器。而“合法的括号串”这道题，可以说是我见过最经典、最能讲清楚栈的价值的一道训练题。它的外表像一个简单的字符串判断题，但内里牵扯到匹配逻辑、边界条件、栈的生命周期管理，甚至还有一定的状态机思想在其中。当年我在某高校做程序设计实训时，这道题被安排在作业一的第5题，名字里特意写着“堆栈的使用！”，可见出题人的用心——它不是让你背栈的接口，而是让你真正理解栈为什么是解决“最近匹配”“嵌套消除”这类问题的天然工具。这篇文章就以这道题为主线，把栈的用法、代码实现、易错点，以及我踩过的那些坑一次说透。无论你是刚接触栈的大一新生，还是在复习数据结构准备面试的老手，这篇内容都能给你一些值得细看的细节。

1. 项目概述与需求拆解

1.1 训练作业的真实目标

“合法的括号串”这个题目放在程序设计实训作业一里面，表面上考察的是字符串处理，但出题人的真实意图一般有三个层次。

第一层是读懂规则——什么样的括号串算合法？这里通常包含两类判定标准：一类是只允许一种括号（比如只有小括号），要求左右括号数量相等且前缀中右括号数量始终不超过左括号数量；另一类是允许多种括号，比如()[]{}混合，此时需要额外保证括号的配对顺序正确，即([)]是不合法的，而([])是合法的。前者只需要计数器，后者才真正需要栈。

第二层是选对数据结构——一旦题目升级为多种括号混编，你会发现计数器方案彻底失效，必须引入一个能记住“最近一个未匹配的左括号”的结构。栈的“后进先出”特性恰好对应了括号最近配对的本能需求：最后一个出现的左括号，必须匹配第一个出现的右括号。

第三层是规范编码——很多新手在本地测试通过后一提交就出错，多半是因为没有处理空串、栈未清空、输入格式异常等情况。实训作业往往要求用 C 语言从零手写栈结构，这又额外考察了结构体定义、内存管理、函数封装的功底。

1.2 合法括号串的判定规则详解

在动手写代码之前，必须把判定规则细化到“可编程”的程度。以最常见的多括号版本为例，合法串需要同时满足以下三个条件：

• 每个左括号(、[、{都必须有对应的右括号)、]、}与之匹配；
• 括号的嵌套顺序必须正确，也就是说右括号出现时，它必须与“最近的未匹配左括号”类型一致；
• 整个字符串处理完毕后，不能有“残留”的左括号，否则意味着括号未闭合。

举几个直观的例子：()合法，()[]{}合法，({[]})合法；而(]不合法，([)]不合法，(()不合法，())也不合法。

有一个容易忽略的细节是空字符串。在多数题目的定义中，空串是合法的括号串，因为没有任何括号需要匹配。但有些同学的代码在输入为空时会因为未初始化栈而直接崩溃，这就非常可惜了。所以在正式编码前，建议先把这些边界情况列成表格，逐条通过后再去写核心逻辑。

1.3 为什么用栈而不是其他结构

这个问题是面试官最爱追问的，也是实训答辩时的加分点。简单说，括号匹配本质上是一个“消除”过程：看到一个右括号，就要去找“最近出现的、尚未被匹配的左括号”。这种“最近的最优先”的诉求，天然就是栈的语义。

如果你想用数组模拟，其实也不是不行——维护一个top指针和一个字符数组，从尾部追加、从尾部弹出，这就是手动实现的栈。如果你想用队列，那就会出问题：队列是先进先出，它会让最早出现且未匹配的左括号去匹配当前的右括号，这与括号嵌套规则完全相悖。比如({})，按队列逻辑，遇到)时匹配的是队列头部的(，看起来似乎也能过，但遇到({)}这种串，队列会让(和)配对，{和}配对，从而错误地判定为合法，而实际上这个串是不合法的。

这个对比能帮你彻底理解一个观点：数据结构的选型不是靠背的，而是要看你需要哪种顺序的存取能力。括号匹配需要后进先出，所以用栈，没有悬念。

2. 核心算法思路与代码结构设计

2.1 栈的基本操作封装

写训练作业时，我强烈建议你至少在代码里明确区分“栈的业务操作”和“题目的业务逻辑”两个层次。即使学校只要求一个文件，也可以用函数把栈的初始化、入栈、出栈、取栈顶、判空封装成独立接口，这样主逻辑会非常清爽，也方便后续调试和复用。

以 C 语言为例，一个简化但够用的栈结构可以这样定义：

#define MAXSIZE 1000 typedef struct { char data[MAXSIZE]; int top; } CharStack; void initStack(CharStack *s) { s->top = -1; } int isEmpty(CharStack *s) { return s->top == -1; } int isFull(CharStack *s) { return s->top == MAXSIZE - 1; } void push(CharStack *s, char c) { if (isFull(s)) { // 实际题目中串长一般不会达到栈容量上限， // 但稳健的程序应该考虑溢出处理 return; } s->data[++(s->top)] = c; } char pop(CharStack *s) { if (isEmpty(s)) { return '\0'; } return s->data[(s->top)--]; } char peek(CharStack *s) { if (isEmpty(s)) { return '\0'; } return s->data[s->top]; }

这里的top初始化为 -1，是一个很实用的约定。它意味着栈空时top == -1，压入第一个元素后top == 0，恰好对应数组下标从 0 开始的习惯。很多人喜欢初始化为 0 然后先赋值再自增，也可以，但要注意所有判空、取栈顶的逻辑都要跟着调整，否则容易出现“差一错误”。

2.2 括号匹配主流程：两分支三细节

核心匹配逻辑可以浓缩为一个循环加一个判断，但里面有三个细节特别容易出错。

int isValid(char *s) { CharStack st; initStack(&st); for (int i = 0; s[i] != '\0'; i++) { char c = s[i]; // 左括号直接入栈 if (c == '(' || c == '[' || c == '{') { push(&st, c); } else { // 右括号出现时，栈必须非空且栈顶类型匹配 if (isEmpty(&st)) { return 0; } char topChar = peek(&st); if ((c == ')' && topChar == '(') || (c == ']' && topChar == '[') || (c == '}' && topChar == '{')) { pop(&st); } else { return 0; } } } // 最终栈必须为空，否则说明有多余的左括号 return isEmpty(&st); }

第一个细节：遇到右括号时先判断栈是否为空。这一步很多人漏掉，结果就是访问了非法内存或读取到了野值。逻辑上也很自然：如果栈已经空了，却出来一个右括号，说明它没有可匹配的左括号，直接判非法即可。

第二个细节：匹配判断要显式比较类型。有些同学会试图用 ASCII 码差值来判断(与)相差 1、[与]相差 2、{与}相差 2，这种技巧在某些字符集下能跑通，但可读性差，而且一旦遇到别的字符容易误判。老老实实写三个if分支，或者用switch，比什么都清晰。训练作业首要目标是正确和可读，不是炫技。

第三个细节：循环结束后要检查栈是否为空。如果整个字符串扫描完毕，栈里还残留左括号，说明有括号始终没有关闭，比如((()。这个检查写起来只要一行，但漏掉它的代价是前功尽弃。

2.3 处理非法字符的两种策略

题目如果明确说“输入只包含括号字符”，那么上面这份代码足够了。但如果你在做自己项目时想复用这段逻辑，通常会遇到字符串里混着空格、字母、标点的情况。这时有两种处理策略。

策略一是忽略非括号字符，只对括号做匹配判断。这种策略适合“从文本中检查括号是否平衡”的场景，比如代码编辑器里的括号高亮。实现时只需在循环里加一个判断：如果当前字符不是六种括号之一，就continue。

策略二是只要出现非括号字符就算非法。这种策略更严格，适合竞赛或考试场景，因为题目描述通常会写“字符串仅包含括号字符”，你多滤一步反而可能违背题意。

我的建议是：在做训练作业时，严格按题目描述来；但在写通用工具函数时，把“过滤策略”设计成一个参数，或者至少写上注释说明当前选择。这个小习惯能避免很多复用时的尴尬。

3. 实操过程与完整代码落地

3.1 从题目描述到测试用例设计

无论你的题目原文是“判断括号串是否合法”还是“给定一个只包含括号的字符串，判断括号是否匹配”，第一步都建议先设计测试用例，而不是直接写代码。这是我在实训中养成的一个习惯，也是后来写工程代码时觉得收益最大的习惯。

针对这道题，我建议至少准备以下几组用例：

把这些用例放在代码注释里或者单独写一个测试函数，每次改动代码后批量跑一遍，能省下大量人工试错的时间。训练作业的测试用例通常有限，但你按这个思路准备一套，基本覆盖了所有能想到的边界。

3.2 完整参考代码：C 语言版

下面给出一个可以直接编译运行的完整版本，包含简单的输入输出处理和主函数。你可以把它当作一个基线，再根据自己的题目要求调整输入格式。

#include <stdio.h> #include <string.h> #define MAXSIZE 1000 typedef struct { char data[MAXSIZE]; int top; } CharStack; void initStack(CharStack *s) { s->top = -1; } int isEmpty(CharStack *s) { return s->top == -1; } int isFull(CharStack *s) { return s->top == MAXSIZE - 1; } void push(CharStack *s, char c) { if (isFull(s)) { return; } s->data[++(s->top)] = c; } char pop(CharStack *s) { if (isEmpty(s)) { return '\0'; } return s->data[(s->top)--]; } char peek(CharStack *s) { if (isEmpty(s)) { return '\0'; } return s->data[s->top]; } int isLeftBracket(char c) { return c == '(' || c == '[' || c == '{'; } int isMatched(char left, char right) { return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}'); } int isValid(char *s) { CharStack st; initStack(&st); for (int i = 0; s[i] != '\0'; i++) { char c = s[i]; if (isLeftBracket(c)) { push(&st, c); } else { if (isEmpty(&st)) { return 0; } char topChar = peek(&st); if (isMatched(topChar, c)) { pop(&st); } else { return 0; } } } return isEmpty(&st); } int main() { char str[MAXSIZE]; // 以 EOF 作为输入结束标志，方便批量测试 while (scanf("%s", str) != EOF) { if (isValid(str)) { printf("合法\n"); } else { printf("非法\n"); } } return 0; }

这段代码里我特意把左括号判断、匹配判断分别抽成了独立函数，这样主逻辑读起来几乎和自然语言一样。如果老师要求提交的代码不能有太多函数（有些课程初期会限制使用自定义函数的数量），你可以把这三个判断直接内联到循环里，逻辑不变。

3.3 复杂度分析与空间优化

这个算法的时间复杂度是 O(n)，因为每个字符最多被入栈一次、出栈一次，整体是线性扫描。空间复杂度在最坏情况下是 O(n)，比如输入是一长串左括号((((...，栈里就会积累 n 个元素。

有些同学会问：能不能只用计数器，省掉栈的空间？对于单一类型括号，确实可以。用一个整数变量记录当前未匹配的左括号数量，遇到左括号加 1，遇到右括号减 1，如果中途减到负数或者最后不等于 0，就判定非法。这个方案空间复杂度是 O(1)，很漂亮。

但对于多类型括号，计数器无法记录“最近未匹配的左括号是什么类型”，所以必须用栈。这也是为什么题目强调“堆栈的使用”——它就是为了让你体会到，某些问题在数据结构选型上的必然性。

如果要进一步优化空间，可以尝试用一个字符数组只存左括号的“类型编码”，比如用 1、2、3 代替(、[、{。这样栈里存的不再是字符，而是更紧凑的整数。不过在 C 语言中，char 本来就只占一个字节，所以这种优化意义不大，反而降低了可读性。训练作业阶段，我更推荐“怎么清晰怎么来”。

4. 常见问题与排查技巧实录

4.1 栈顶指针的经典错误

我在给学弟学妹看代码时，见过最多的一类错误是top指针的初始化和自增顺序搞反。比如有人写：

void push(CharStack *s, char c) { s->data[s->top] = c; s->top++; }

同时初始化top = 0。这种写法不是不行，但如果你在pop时写的是s->top--; return s->data[s->top];，那么先压入的第一个元素存在data[0]，弹出的却是data[top-1]，逻辑上没问题。可是如果某个地方忘了统一约定，比如判空写成top == -1，就会导致栈永远非空，最终结果全错。

我的建议很朴素：一套约定用到底。要么全部采用top = -1表示空栈，入栈时++top再赋值；要么全部采用top = 0表示栈中元素个数，入栈时先赋值再top++。别混用。为了避免这种低级错误，最好的办法是在初始化函数里就把约定写清楚，所有操作都通过函数完成，不要在主逻辑里直接访问s->data[s->top]。

4.2 字符串读入方式引发的血案

训练作业里常见的输入方式有两种：一种是题目已经给定字符串变量（比如在函数参数里传入），另一种是要求从标准输入读取。后者有一个非常典型的坑：用scanf("%s", str)读取时，遇到空格会停止。如果测试数据是( [ ]这种带空格的括号串，scanf会把它们切成多个单词，导致程序逻辑混乱。

此时你需要明确题目对输入格式的定义。如果题目说“输入一行字符串，可能包含空格”，那就应该改用fgets或getline。在 C 语言里，fgets(str, MAXSIZE, stdin)可以读取整行，但它会把末尾的换行符\n也读进来，所以读完后通常要手动去掉：

char str[MAXSIZE]; fgets(str, sizeof(str), stdin); str[strcspn(str, "\n")] = '\0';

如果题目说“只包含括号字符且无空格”，那么scanf就足够，而且更简洁。判断依据就一条——严格按照题目描述的输入格式来，不要自行假设。

4.3 空串与栈残留：两个最隐蔽的失分点

空串问题我在前面提过，但这里还是要强调，因为真的太容易翻车。有些同学在主函数里直接写scanf("%s", str)，如果测试数据是空行，scanf会一直等待输入，造成“超时”的假象；如果题目通过参数传入字符串，传入的是""，但代码里没有显式处理空串，循环根本不会执行，最后返回isEmpty(&st)，而栈是初始化过的，所以结果是合法。其实这层逻辑已经在代码里自然覆盖了，但前提是你不要在没有输入时强行访问字符串，也不要忘记初始化栈。

栈残留问题则更容易在“看起来没问题”的代码里潜伏。比如你只判断了中间步骤，循环结束后忘了检查栈空，那么输入(()时，循环结束后栈里还有一个(，但函数却返回了合法。这个问题在测试中特别容易被漏掉，因为()、()[]这类用例都会通过，只有(()或(([]这类“左括号多于右括号”的用例才会暴露。我的测试用例表里专门放了两条这样的用例，就是为了时刻提醒自己。

4.4 调试技巧：把每一步的栈状态打出来

如果程序跑出来结果不对，最快的定位方式不是瞪着眼睛看代码，而是加日志。在循环里临时插入一行打印：

printf("i=%d, c=%c, top=%d, stack_top_char=%c\n", i, c, st.top, peek(&st));

你会非常直观地看到每个字符处理完后的栈状态。这个方法尤其适合理解([)]这种交叉嵌套的案例：当你处理到)时，栈顶是[，匹配失败，直接返回非法——日志里一目了然。

调试完了记得把日志删掉，否则提交作业时会输出多余内容，导致评测系统判错。这个操作我在实训时干过不止一次，每次都是泪的教训。

4.5 栈容量与数据范围

题目如果没有明确说明字符串最大长度，你需要自己估算。MAXSIZE设置得太小，比如 100，遇到长测试用例就会栈溢出；设置得太大，比如 1000000，虽然一般也能过，但会浪费内存。一个稳妥的做法是读取题目中的字符长度限制（通常是 1000、10000 或者更大），把MAXSIZE设为限制值加 5 或加 10，留出换行符和结束符的余量。

另外，有些同学会问我：“如果题目给的字符串特别长，用数组模拟栈会不会爆？”理论上可以改用动态分配，但在训练作业阶段，静态数组完全够用。真正需要警惕的是递归实现的“栈溢出”——如果你用递归函数来做括号匹配，遇到几千层的嵌套就会爆栈，所以这个题目用显式的栈结构而不是递归，本身也是一种规避风险的好选择。

5. 进阶扩展：不只是“判断合法”这么简单

5.1 升级方向一：找出第一个非法位置

有些综合训练题会要求你不仅要判断括号串是否合法，还要在非法时输出第一个出错的位置。这时算法需要微调：记录当前字符的下标，当发现栈空却遇到右括号时，输出该位置；或者当匹配类型不一致时，也输出该位置。

如果最终栈里还有残留左括号，第一个未被匹配的左括号位置通常就是出错点，但它到底算不算“第一个非法位置”，不同题目有不同约定。有的题目约定输出最靠前的右括号出错位置，有的约定输出最靠前的未匹配左括号位置。这又是一个需要仔细读题的点。

5.2 升级方向二：最小添加次数

另一个经典变形题是：给定一个括号串，问至少需要添加多少个括号才能使它合法。这个问题的解法依然依赖栈——扫描过程中遇到右括号时，若栈空，则count++（表示需要额外补一个左括号）；扫描结束后，栈中剩余的左括号数量也要计入count。最终count就是答案。

这个变体说明了一个很重要的道理：栈不仅能用来“判断”，还能用来“计数”。栈中元素的个数往往就是“当前尚未解决的问题数量”，这个直觉在后续学习更复杂的数据结构时会反复用到。

5.3 从这道题延伸到工程场景

比如编译器的语法分析阶段，需要检查代码中括号是否匹配；文本编辑器的高亮功能，需要快速定位不匹配的括号；计算器中缀表达式转后缀表达式，也要用栈处理运算符优先级。虽然这些场景的复杂度远超一道训练题，但核心思路都是一样的：用栈维持一个“最近优先”的待处理序列。

我在实训结束后的总结里写了一句至今仍觉得有用的话：栈不是一道题的答案，而是一类问题的武器。当你能在一道简单的括号题里理解“为什么必须用栈”，后面再遇到表达式求值、函数调用栈、撤销操作等场景，你会自然而然地想到它，而不是去翻书查“哪种数据结构适合哪种场景”。

个人实操体会

这道题我前后写过不下五遍，从最开始的if-else铺满主函数，到后来优雅地封装成独立函数，每一次重构都能看到自己的进步。有一个经验想分享给正在做训练作业的读者：不要满足于“能过样例”。试着把代码拿给旁边的同学看，让他随便挑毛病；再试着把输入改成空串、超长嵌套、带空格的形式，看看程序会不会崩溃。所有这些“多余”的折腾，才是训练真正的价值。

如果你在做这道题的过程中遇到了“明明逻辑对但就是过不了”的情况，优先检查三件事：栈初始化了吗？右括号时判空了吗？循环结束后查栈空了吗？我自己踩过的坑，八成都能归到这三点里。希望你一次就过，但如果没过，也别气馁——把错误用例记录下来，弄明白它为什么错，这比提交通过本身更有意义。