JavaScript 栈式括号匹配校验：从二十行算法到可报错模块

简介这是一份面向JavaScript初学者与算法练习者的括号有效性判断代码资源聚焦栈结构在字符串匹配中的典型应用可用于理解左括号与右括号按类型、按顺序闭合的校验思路。压缩包共2个文件含1个js与1个txt体积约818B其中main.js给出核心判断函数及测试示例README.txt用于承载项目或运行说明整体轻量便于直接阅读与本地验证。该资源已有3427人学习下载适合作为数据结构入门、面试题复盘或课堂示例。读者可从中获得完整实现代码、括号配对映射写法、栈的入栈与出栈校验流程以及有效与无效用例的对照结果同时可结合注释与测试输出梳理边界情况如栈为空、类型不匹配和遍历结束后栈未清空等判断便于快速掌握同类括号匹配问题的解题脉络。1. 先看一个很窄但很常见的场景代码评审时翻到过一段校验逻辑作者用正则把成对的括号一遍遍替换成空串最后看长度是不是 0。单个用例跑得飞快喂进去([)]却直接放行了——这就是典型的「每种括号数量都对得上但嵌套顺序非法」。后来我把这段 js 代码里的写法搬了过去一个栈、一张映射表、一次遍历二十行左右把有效性判定做干净。它要解决的问题很窄给定一个只含(、)、{、}、[、]六种字符的字符串 s判断左括号是否都用同类型的右括号闭合且闭合顺序正确。适合三类人写表单校验、表达式解析器、模板引擎的前端同学需要把一段小算法嵌进业务但不想引第三方库的人以及刚学栈这个数据结构、想要一个能完整跑通又能随手改的练手项目的人。2. 项目定位与技术选型一个纯 JS 的栈式校验器2.1 输入契约先说清楚后面的实现才好谈这份代码的输入契约非常明确s只包含六种括号字符长度可能为 0可能是()、()[]{}、{[]}也可能是(]、([)]、(这类反例。输出只有一个布尔值。正因为契约窄实现才能压到极短也正因为窄很多人在把它往真实业务里搬的时候会踩坑——真实表单里可能出现、可能夹杂空格和中文、可能超长这些都不在原始契约里需要自己补。我把这份代码定位成一个校验内核而不是一个完整工具。它不负责报错提示、不负责定位到第几个字符出错、也不处理除括号以外的字符。这些能力在后面第 6 章会做扩展。先认清边界读代码的时候就不容易把注意力浪费在「它为什么不告诉我哪里错了」上。顺带说一句环境整份代码不依赖任何 npm 包纯 ES6 语法Node 12 以上或者任意现代浏览器控制台都能直接跑。没有构建步骤、没有打包配置这既是它的优点拿来就能用也意味着它不会替你做任何工程化的事。2.2 选型对比为什么是栈而不是计数法或正则判断括号有效性有三种常见思路我把它们的差异列一下你就明白这份代码为什么选栈了方案时间空间能否处理嵌套顺序典型失败用例三个计数器分别统计三种括号O(n)O(1)不能([)]会被判为有效正则反复替换成对括号O(n²) 左右O(n)能但实现绕嵌套深时递归/替换次数爆炸栈 映射表O(n)O(n)能基本没有除非实现写错计数法的问题在于它只统计「数量」管不了「顺序」。([)]里圆括号 1 对、方括号 1 对数量完全正确但右圆括号闭合的时候栈顶还是方括号顺序是错的。正则替换法用(){}[]反复消对思路是对的等价于一个隐式的消除过程但每次replace都会重建字符串深层嵌套时性能掉得厉害而且正则写错一个转义就很难调——我见过把[]写成字符组的版本跑起来静默错误。栈天然就是「最近打开的最先关闭」这个语义的数据结构和括号嵌套的顺序约束完全同构。这也是我一般在教学和实战里都推荐栈的原因它不是技巧是问题结构本身决定了的选择。2.3 运行环境与文件形态原始资源是一份单文件 js 代码形态上就是一个函数定义加若干调用示例。落地时我一般会把它拆成三层solution.js只放核心函数末尾用module.exports导出方便被别的文件requiretest.js表驱动的用例集合跑一遍打印结果不引测试框架demo.html可选一个输入框加一个按钮把校验结果实时打在页面上用来演示和自测。拆成三层的好处是边界清晰核心函数不掺杂任何打印和 DOM 操作测试和演示都是它的消费者。这份代码原始形态里是带console.log的直接搬进业务会污染日志拆分是最省事的处理方式。3. 核心链路拆解一次遍历里发生了什么3.1 主函数逐段读入栈、配对、收尾核心函数只有二十来行但它把三个关键动作串在了同一个循环里。先看完整代码// 右括号 - 左括号 的映射用于 O(1) 判断类型是否匹配 const PAIRS { ): (, ]: [, }: { }; /** * 判断只包含 ()[]{} 的字符串是否有效 * param {string} s 待校验字符串 * returns {boolean} */ function isValid(s) { // 奇数长度不可能完整配对先短路省掉一次遍历 if (s.length % 2 ! 0) return false; const stack []; // 只存左括号字符 for (let i 0; i s.length; i) { const ch s[i]; if (ch ( || ch [ || ch {) { stack.push(ch); // 左括号压栈等待被闭合 continue; } // 到达这里说明是右括号输入契约保证只有六种字符 // 栈空 多出一个右括号栈顶类型不符 交叉嵌套两种都判失败 if (stack.pop() ! PAIRS[ch]) return false; } // 遍历结束后栈必须为空否则说明有左括号没被闭合 return stack.length 0; }第一段是映射表PAIRS。它的键是右括号、值是左括号方向很重要——因为判定的时机是「遇到右括号」此时需要知道「它应该闭合哪一种左括号」直接拿PAIRS[ch]取到期望的栈顶即可不用写三个if分支。中间那段循环是整份代码的主干。遇到左括号就push遇到右括号就pop出栈顶做比对。这里有个容易被忽略的细节stack.pop()在栈为空时返回undefined而undefined ! (恒为真所以「右括号多余」这种情况不需要单独写一个stack.length 0的判断一次比对就覆盖了。这是原代码写得比较紧凑的地方。最后一行return stack.length 0处理的是另一种失衡左括号多出来。比如(()循环里三个字符都没触发return false结束时栈里还剩一个(。这一句是必须的漏掉的话所有「左括号过量」的用例都会被误判为有效。3.2 参数与返回值这份函数没有隐藏状态isValid只有一个入参s是字符串没有默认值、没有配置项。返回值是严格的布尔值true/false不返回undefined、不返回状态对象。这一点在嵌入业务时很重要——很多校验函数喜欢返回null表示不适用调用方一个不小心写成if (!isValid(x))就会把null和false混在一起处理出问题时很难查。函数内部没有任何模块级可变状态PAIRS是只读常量stack是每次调用新建的局部数组。这意味着它是纯函数、可重入、可并发调用不需要加锁也不需要每次用之前 reset。如果你打算把它放进一个长驻的服务里跑这一点省了不少心。3.3 复杂度与边界预算时间复杂度 O(n)每个字符最多被push一次、pop一次常数很小。空间复杂度 O(n)最坏情况是整个字符串全是左括号栈的深度等于字符串长度。这个空间开销在真实场景里值得算一下。如果输入是一段 10MB 的 JSON 文本做括号预检栈里最多压 10M 个单字符V8 里每个数组元素占 8 字节左右的指针槽大概 80MB加上字符串本身内存峰值会很可观。所以我在处理超长文本时会加一条长度上限保护超过阈值就走流式分块校验这一点在第 6 章展开。边界上还有几个必须明确的语义空字符串长度为 0是偶数循环一次都不进最后stack.length 0为真返回true。这个结论符合数学定义空串是合法序列但在业务里往往不等于「用户填了内容」所以调用方在拿到true之后通常还得自己补一次非空判断。4. 跑起来三种执行方式与表驱动自测4.1 从命令行到浏览器三种跑法最直接的方式是命令行。把上面的函数存成solution.js末尾加一行打印然后执行# 确认 node 版本不低于 12ES6 语法都支持 node -v # 直接跑单文件 node solution.js如果想让它同时能被别的文件引用就在solution.js末尾加上导出再用一个test.js去调// solution.js 末尾 module.exports { isValid }; // test.js const { isValid } require(./solution); console.log(isValid({[]})); // true在浏览器里跑则是把函数整段贴进控制台然后手动调几次。这种方式适合快速验证思路不适合长期维护因为改动不会留存。第三方式是做成一个小页面输入框加按钮实时显示结果。这个形态在给别人演示或者自己肉眼比对十几种用例时最直观尤其是处理中文和空格混排的时候——控制台里和 看起来几乎一样页面上加个长度显示就一目了然了。4.2 用表驱动写用例别一条条写断言手工写if (isValid(()) ! true) throw ...写到第五个用例就会烦而且容易漏掉反例。我的习惯是把用例整理成二维数组一个循环跑完失败时把输入、期望、实际一起打出来const { isValid } require(./solution); // [输入, 期望结果, 用例说明] const cases [ [(), true, 最简单的一对], [()[]{}, true, 三种并列], [(], false, 类型不匹配], [([)], false, 嵌套顺序错误计数法会翻车], [{[]}, true, 正确的三层嵌套], [(, false, 只有左括号], [), false, 只有右括号], [, true, 空串按定义为有效], [((), false, 左括号多一个], ]; let failed 0; for (const [input, expect, desc] of cases) { const actual isValid(input); const ok actual expect; if (!ok) failed; console.log(${ok ? PASS : FAIL} | ${desc} | in${JSON.stringify(input)} expect${expect} actual${actual}); } console.log(failed 0 ? 全部通过 : ${failed} 条失败);这里用JSON.stringify(input)而不是直接拼字符串是为了让空串、空格这类不可见输入在日志里也看得见。这个习惯是从一次线上问题之后养成的当时一个空串被误判日志里打印出来是一片空白盯了半小时才发现问题出在输入上。用例设计上要刻意覆盖三类正常嵌套深度 1 到 3、数量失衡左多、右多、顺序非法([)]。第三类是最容易在重构时被破坏的我每次改实现都会先跑这一组。4.3 三个真实工程落点这份代码最直接的用途是表单校验。比如一段表达式输入框用户可能输入(ab)*(c-d)这类内容提交前先做一次括号预检能在解析阶段之前就拦住大部分低级错误给出的提示也比「表达式非法」更具体。第二个落点是表达式解析器的前置检查。写递归下降解析器的时候如果括号本身就不平衡递归会一路跑到栈溢出或者抛出一个语焉不详的异常。在入口处先用这个函数过一遍可以把「括号不配对」和「语法不合法」两类错误分开排查效率差别很大。第三个落点是模板引擎和 DSL 解析。模板里常见{{ }}、{% %}这类成对标记虽然字符不同但判定逻辑和括号完全一致——只要把映射表换掉就行。第 6 章的自定义括号对就是在做这件事。5. 避坑与排查五个真实翻车现场5.1 输入处理类的三个坑坑一用in判断键存在被原型链坑了。现象某次把映射表换成{ }: { }之后输入里混进了一个普通字符串函数没有报错也没有返回false而是抛了TypeError。原因判断分支写成了if (ch in PAIRS)。in运算符会沿原型链查找toString in PAIRS返回trueconstructor in PAIRS也返回true于是普通字符被当成右括号走进比对分支PAIRS[ch]拿到一个函数和栈顶字符串比对当然不等但代码里如果还有别的取值操作就会炸。解决要么用Object.create(null)建一张没有原型的表要么老实写Object.prototype.hasOwnProperty.call(PAIRS, ch)。我在需要高频判断的场景会直接用Mapmap.has(ch)没有原型链问题语义也更清晰。坑二循环里用for...in遍历字符串。现象某个环境里字符串被扩展了原型方法for...in把方法名也遍历出来了结果多跑了几个字符。原因for...in遍历的是可枚举属性包括原型链上的字符串索引只是其中一部分。对数组和字符串用它都属于误用。解决改用带索引的for循环或者for...of。这份代码用的是索引循环s[i]逐字符取行为最可控也方便后续扩展成「出错时返回位置」。坑三忘记处理左括号剩余的情况。现象(()被判为有效测试用例里没覆盖到上线后用户输入了半个表达式解析器直接崩溃。原因循环里只在遇到右括号时返回false遍历结束后没有检查栈是否为空。这是最常见的漏写因为大部分人手写用例时习惯写()、()[]{}这种平衡的反例只写(]。解决循环结束后必须return stack.length 0。写测试时强制自己补一条「只有左括号」的用例这个坑就再也不会出现了。5.2 工程接入类的两个坑坑四把console.log一起搬进了业务代码。现象生产环境日志里每隔几秒冒出一串括号和布尔值日志量翻倍排查真正的错误时被淹没。原因原始代码是演示形态函数内部或调用处带调试输出复制粘贴时一起带进去了。解决核心函数保持零副作用只返回结果输出交给调用方。我在做代码评审时会把「纯计算函数里有打印」作为一条硬性检查项因为它不影响功能跑测试也发现不了只能靠人工看。坑五超长输入直接把主线程卡住。现象一个富文本编辑器里粘贴了几万字的文档括号预检跑了将近两百毫秒输入明显卡顿。原因O(n) 的遍历本身没问题问题在于输入长度没有上限而这段校验是在每次按键时同步触发的。解决两条措施一起上。一是加长度上限超过阈值直接跳过预检或者转成异步二是给按键触发加防抖把校验从「每次输入」降到「停止输入 200ms 后」。纯算法层面的优化意义不大瓶颈在触发时机而不在算法本身。6. 二次开发从二十行扩成一个能报错的校验模块原始函数只回答「有效 / 无效」这在调试和用户提示场景下不够用。我在实际项目里做的第一件事就是让它带上位置和原因。下面这版保留了原实现的骨架把栈元素从字符换成了{ ch, pos }同时把括号对做成可配置参数/** * 分析括号串返回结构化结果而非布尔值 * param {string} s 输入串 * param {Array[string,string]} pairs 自定义括号对默认三种 * returns {{ok:boolean, pos?:number, reason?:string, expect?:string, got?:string}} */ function analyze(s, pairs [[(, )], [[, ]], [{, }]]) { const openSet new Set(pairs.map(p p[0])); const closeOf new Map(pairs); // 左 - 右用于生成期望值 const closeMap new Map(pairs.map(([o, c]) [c, o])); // 右 - 左用于比对 const stack []; for (let pos 0; pos s.length; pos) { const ch s[pos]; if (openSet.has(ch)) { stack.push({ ch, pos }); continue; } if (!closeMap.has(ch)) continue; // 非括号字符跳过交由调用方决定是否严格 const top stack.pop(); if (!top) { // 右括号多余此时没有可闭合的左括号 return { ok: false, pos, reason: unexpected-close, got: ch }; } if (top.ch ! closeMap.get(ch)) { // 交叉嵌套栈顶类型与当前右括号不匹配 return { ok: false, pos, reason: mismatch, expect: closeOf.get(top.ch), got: ch }; } } if (stack.length) { // 左括号未闭合报最后一处未闭合的位置 const top stack[stack.length - 1]; return { ok: false, pos: top.pos, reason: unclosed, expect: closeOf.get(top.ch), got: null }; } return { ok: true }; }改动集中在三处。第一栈里存对象而不是字符位置信息随元素一起入栈报错时能直接指到第几个字符前端可以据此在输入框里做高亮。第二括号对参数化模板引擎的{{ }}、{% %}、甚至 XML 的尖括号都能复用同一套逻辑不用复制三份代码。第三返回结构化对象reason区分了三种失败模式调用方能给出「第 5 个字符处多了一个右括号」这种具体提示而不是干巴巴一句「格式错误」。有一处语义需要你自己拍板遇到非括号字符怎么办。上面这版是跳过等价于宽松模式适合「先把括号挑出来验一遍」的场景如果要严格模式把if (!closeMap.has(ch)) continue;换成if (!closeMap.has(ch)) return { ok: false, pos, reason: invalid-char, got: ch };即可。两种都合理取决于你的输入契约。再往下走还有两个可选的改造方向我列一下各自的代价改造点收益代价结果缓存Map 存输入到结果重复输入场景快很多要控缓存大小否则内存涨分块流式校验支持超大文本不阻塞主线程状态要跨块保存复杂度上一个台阶多括号对合并校验一次遍历同时验圆括号和模板标记映射表冲突时要定优先级缓存这一项我要多说一句如果输入是按键触发的短表达式缓存命中率其实很低加了反而多一次查表开销不如老老实实做防抖。分块流式则值得投入思路是把stack提到函数外面维护每次喂一个 chunk返回当前是否已经出错最后一块再判空。这个改造我做过一次难点不在算法在于错误位置的偏移量换算容易差一。从那以后我每次把这类小算法塞进业务之前都会强制走一遍「纯函数 表驱动用例 位置上报」这三步哪怕代码只有二十行。功能上它确实简单但工程里出问题的从来不是算法本身而是调用它的那些边界。希望帮到你。本文还有配套的精品资源点击获取