洛谷 B2165 括号匹配是我在刷“栈”这个数据结构题单时印象很深的一道题。别看它标着入门难度我第一次提交就 WA 了两次不是不会写代码而是把输入方式和边界条件想得太简单。这道题要做的只有一件事给你一串由()和[]组成的字符串判断括号是否按规则匹配。听起来简单但想一次写对、写稳得先把“为什么一定要用栈”这件事想明白。这篇题解我会从题目结构拆起把三种常见写法、五六个容易踩的坑、完整 AC 代码和后续刷题路线都放出来新手可以直接照着写。1. 题目到底在考什么1.1 题干拆解先把题意掰开揉碎。这类括号题面往往只给你一行字符串里面出现四种字符(、)、[、]让你判断整体是否合法。合法的定义分两层一层是数量配平一层是顺序正确。数量配平好理解一个左括号配一个右括号顺序正确才是这道题真正的考点也是最容易被忽略的部分。很多人第一反应是“我统计一下(和)数量相等、[和]数量相等不就完事了吗”这个想法错得离谱后文我会单独用一节来锤它。先看顺序这个维度()和[]当然合法([])也合法因为内层的小括号先闭合外层的方括号包住它们。但([)]就不合法四种字符的数量各配平了左右括号数量也对等可它出现了交叉嵌套先打开了方括号又打开小括号结果先关闭方括号再关闭小括号这不符合括号成对收束的规则。我刷这题的时候把合法条件拆成了三条写在了草稿纸最上面左括号必须和同类型的右括号配对(不能去配]。关闭顺序必须“后来者先关”嵌套越深、越晚出现的左括号越先被右括号关掉。整个字符串扫描完之后不能有左括号剩在栈里没被关掉。这三点就是整道题的全部考点。任何能做到这三条的代码都能过任何省掉其中一条的判断都会在某组测试数据上翻车。1.2 为什么必须是栈再看第二条“后来者先关”。这正是后进先出LIFO的顺序。最容易理解的类比是叠盘子你往桌上叠三层盘子要拿走的时候一定先拿最上面那个最后放上去的。括号嵌套也一样字符串( [ ] )里最晚遇到的[反而最早被]关掉最早遇到的(最后才被)关掉。只要问题天然带有“后出现的先处理”这种顺序要求栈就是最顺手的工具。反过来想如果你用队列来存左括号先进先出遇到]时会取出最前面的(类型对不上整段序列直接判错。所以这道题不是“老师说要栈所以用栈”而是问题的结构本身就决定了栈是唯一合理的方案。扫描字符串时的动作其实只有三个遇到左括号就压栈遇到右括号就去和当前栈顶比较匹配就弹出如果不匹配或者栈是空的直接宣布失败。全程不需要递归、不需要复杂状态机一个栈加一个 for 循环就是全部。时间复杂度 O(n)空间复杂度 O(n)对字符串长度不大的入门题来说完全够用。2. 三种写法与核心代码2.1 数组模拟栈最推荐竞赛环境里我一般优先用数组模拟栈不是 STL 不好而是手写栈更直观也更好调试。想打印栈里存了什么直接一个 for 循环刷一遍就能看到用stack反而得临时pop出来看。我自己的标准写法长这样#include bits/stdc.h using namespace std; char stk[100005]; // 数组模拟栈留足余量 int top; // 指向栈顶元素的下一个位置 int main() { string s; getline(cin, s); // 读整行避免输入中含空格时被 cin 截断 for (char c : s) { if (c ( || c [) { stk[top] c; // 入栈写入 top 位置然后 top 加一 } else if (c )) { // 栈空说明这个右括号没有可配对的左括号 if (top 0 || stk[top - 1] ! () { cout NO endl; return 0; } top--; // 匹配成功弹出栈顶 } else if (c ]) { if (top 0 || stk[top - 1] ! [) { cout NO endl; return 0; } top--; } // 其他字符按题意不会出现出现也可以直接忽略 } if (top 0) cout YES endl; else cout NO endl; return 0; }说说关键细节。top的语义我习惯定义成“下一个可写位置”所以栈底是stk[0]栈顶是stk[top - 1]。入栈写stk[top] c出栈直接top--弹出去的元素其实还留在数组里但已经不属于栈了下次入栈会被覆盖。判断右括号时top 0 || stk[top - 1] ! (这个短路顺序很重要左边成立说明栈空右边根本不会执行不会发生越界访问要是你反过来写stk[top - 1] ! ( || top 0top 为 0 时先访问stk[-1]那就是未定义行为本地可能碰巧不崩交到 OJ 上就是 RE。2.2 STL stack语义最清晰如果你更习惯标准库stack写法会更直白。逻辑完全一样代码量还短一点#include bits/stdc.h using namespace std; int main() { string s; getline(cin, s); stackchar st; for (char c : s) { if (c ( || c [) { st.push(c); } else if (c )) { if (st.empty() || st.top() ! () { cout NO endl; return 0; } st.pop(); } else if (c ]) { if (st.empty() || st.top() ! [) { cout NO endl; return 0; } st.pop(); } } cout (st.empty() ? YES : NO) endl; return 0; }这两种写法在洛谷上都能稳过。我个人的习惯是字符串长度不大的题STL 完全没问题要是以后做到字符串长度到 10^6 的括号序列计数题再换回数组模拟。数组模拟和 STL 不是对立关系核心判断逻辑一字不差区别只是管理栈的方式。新手阶段最好两种都会写至少得看得懂别人题解里的写法。2.3 计数法为什么不行这是我在评论区反复看到的一个误区单独拎出来说。用计数法的人通常这么想统计(的数量和)的数量一样多[的数量和]的数量一样多就认为合法。这个思路连第一个反例都过不了。反例一)(。右括号开头、左括号结尾两个括号数量都是 1。计数法给出“合法”可肉眼一看就知道顺序反了不能通过。反例二([)]。两类括号数量全配平却是交叉嵌套同样非法。这两个例子说明括号匹配是不是合法取决于字符出现的顺序以及它们之间按什么结构收束而不是数量上的账平不平。为什么计数法会失败因为计数器只记录“总共有多少个”而括号合法性的判断依赖的是“它们在哪里出现、以什么顺序闭合”。同一种字符数量一样可以排列出无数种顺序其中只有少量是合法括号序列。这就像你知道一抽屉里有四只型号一样的手套但不知道它们是否都配成了左右一对——数量的账算清了结构的信息却全丢了。括号匹配是序列结构问题不是统计问题。遇到“要不要用栈”的决策时多问自己一句我需要记录的仅仅是数量还是需要记录顺序答案一般自己就出来了。提示判断一道题该不该用栈就看它是否需要保留“历史顺序”以及后续操作是否需要倒着消费这些历史信息。需要就是栈不需要才轮到计数、哈希这些方案。3. 易错点与对拍测试3.1 入坑记录五个常见错误第一个坑是输入方式。题目字符串若包含空格cin s只会读到空格为止后半段括号全丢了判断结果自然不对。稳妥做法是用getline(cin, s)。如果题目保证纯括号串两种都行但我建议直接养成读整行的习惯以后做其他字符串题也能少踩同类坑。第二个坑是空栈访问。碰到右括号时忘了判断栈是否为空直接比较stk[top - 1]。top 为 0 时访问负下标本地测试可能碰巧读到垃圾数据交上去就是 RE。这个问题最难排查的一点是它不一定每次都会崩取决于内存里那个位置存了什么。解决方案很简单永远把empty判断写在类型比较之前。第三个坑是收尾忘了查栈。字符串扫描完成所有右括号都配上了但栈里可能还留着没被关掉的左括号比如(((。top 0这行检查是最后一道防线漏掉它整个题就直接白写。我在初学那阵漏过不止一次提交之后看到 WA 才反应过来。第四个坑是括号类型混配。有人会想用 ASCII 差值简化判断比如(和)差 1[和]差 2于是只判断差值大小。这种写法在嵌套和混杂场景下容易出边界问题而且可读性一塌糊涂。老老实实写字符比较一行一个条件清晰、直观、不容易错。第五个坑是数组开小。字符串长度上限不高的题开 1005 也够但我见过有人从模板里拷代码数组只开了 100数据稍微一大就越界。不差这几 KB 内存直接开到 100005省心也安全。3.2 自测用例表提交之前我建议至少把下面这组数据跑一遍。它能覆盖前面讨论的大多数错误也就两分钟的事输入期望输出覆盖点()[]YES两组独立括号([])YES多层嵌套([)]NO交叉嵌套)(NO右括号先出现(((NO扫描完栈不空))((NO空栈配对([([])])YES深层嵌套()()()YES多组并列需要注意空字符串的情况。有些题面会规定空串算不算合法有些版本直接不讨论。如果输入是空行而题意没说明程序按top 0会输出 YES。遇到约定不清的题优先看样例和题目最后一句说明实在没有就按常规做法处理不用过度纠结。本地测试还有个进阶玩法写一个随机括号串生成器再写一个递归暴力验证函数和你的栈解法对拍。随机跑一万组哪里有逻辑漏洞一目了然。这个方法对后面复杂数据结构题同样实用值得从小题练起。4. 完整AC代码与提交技巧4.1 完整代码把前面的数组模拟栈版本整理成最终形态我把它当成这类题的模板#include bits/stdc.h using namespace std; char stk[100005]; // 数组模拟栈留足余量 int top 0; // 核心判断逻辑 // 1. 左括号入栈 // 2. 右括号与栈顶比对类型匹配则弹出否则直接失败 // 3. 扫描完栈空才合法 int main() { string s; getline(cin, s); for (char c : s) { if (c ( || c [) { stk[top] c; } else if (c )) { if (top 0 || stk[top - 1] ! () { puts(NO); return 0; } --top; } else if (c ]) { if (top 0 || stk[top - 1] ! [) { puts(NO); return 0; } --top; } } puts(top 0 ? YES : NO); return 0; }这段代码在 G17 下编译零警告。puts比cout短一点新手如果觉得别扭全部换成cout也没问题可读性优先。核心逻辑就这一层后续扩展成支持{}都只需要在 if 里加一个分支结构非常干净。4.2 提交时的小细节第一看清楚题目要求的输出字符串大小写。洛谷上常见要求是YES/NO但有的变体会要求Yes/No或者T/F。大小写不对就是一连串 WA而且很难查到原因。最稳妥的做法是复制样例输出到代码里别手打。第二确认是否多组数据。不少 OJ 的括号题支持多行输入要用while (getline(cin, s))包住主体。B2165 通常只给一组输入但题面写的是“输入包含多行”就别犹豫直接套循环。第三注意本地环境和评测环境的差异。洛谷评测机是 Linux换行符是 LF本地 Windows 测试是 CRLF一般不影响getline。但如果混用cin和getline中间可能会吃到残留的换行符导致第二次读取得到空串。本题只有一次读取不存在这个问题做多组数据题时要格外小心。第四数组不需要整体清零。top 0已经保证了栈底为空之后只在数组里写、只改 top不会读未初始化的内容。写memset(stk, 0, sizeof(stk))完全是多余的白白浪费时间。5. 从B2165往外走5.1 工程里的括号匹配括号匹配远不是一道 OJ 题这么简单。代码编辑器里光标移到括号上高亮对应另一半用的就是这个算法IDE 自动补全右括号、代码格式化工具检查缩进、编译器的语法分析处理表达式优先级背后全是栈结构在做后进先出的匹配逻辑。甚至 JSON、XML 这类结构化文本标签的开闭和对象的嵌套本质也是同一套“先开后关”的规则。再往前一步中缀表达式转后缀表达式逆波兰表达式时括号的作用是决定运算符的出栈时机。那已经不只是判断括号对错而是用括号控制执行流程属于栈应用的进阶。洛谷的 P1449 后缀表达式就是补这一环的题把栈里存的东西从单个字符变成数字然后做运算。B2165 做完之后紧接着做它衔接非常自然。B2165 的代码稍微改一下支持三种括号{}就可以当一个小工具用来检查一段伪代码的括号是否成对。我当初学到这里时真这么干过复制一份改动版把 LeetCode 上的长表达式粘进去检测跑出的结果全都正确。这种“把小题目延伸成小工具”的练习收获比单纯多刷三题大得多。5.2 洛谷后续刷题路线如果你刚做完 B2165我建议按这个顺序往下刷P1739 表达式括号匹配只有小括号但字符串里混着字母和运算符需要忽略非括号字符。练的是对题目的适应能力思路不变处理方式多了几行。P1449 后缀表达式栈从“存括号”变成“存数字”开始理解栈在计算过程中扮演的角色。表达式求值类题目洛谷搜“表达式求值”即可稍微复杂的运算逻辑消耗的字符集更大栈的应用也更完整。再往后可以碰一些括号序列的思维题比如统计最长合法括号子串长度、生成合法括号序列等核心栈逻辑不变但会加上 DP 和递推思想属于难度进阶。刷题这件事做一道题最大的收获往往不在那道题本身而在于你能不能把它拆成可复用的模式。B2165 的“左括号压栈、右括号比对、最后查空栈”三部曲就是所有括号类问题的标准模式。我后来处理表达式求值、编辑器文本高亮需求时经常还会回到这段逻辑上可见经典题的价值。最后分享一个小习惯写完这类栈的题提交前一定先跑一遍那八组对拍数据前前后后不过两分钟。这两分钟省下的是提交后一次判题失败还有盯着红色错误记录时的一肚子火。B2165 这道题本身不大但把它吃透你栈这一块的基本功就算真的稳了。