博客首页开源平台

30-seconds-of-code：用 JavaScript 栈算法查找字符串中的匹配括号对

原创2026-10-03 18:46:10630 阅读
文章标签：教程文档

30-seconds-of-code：用 JavaScript 栈算法查找字符串中的匹配括号对

括号匹配（bracket matching）是编写解析器（parser）、解释器（interpreter）时几乎绕不开的基础问题：无论是解析数学表达式、校验 HTML 标签，还是实现类 Brainfuck 的 Esolang 解释器，都需要在一段字符串中快速定位相互匹配的开闭符号及其索引。本篇文章基于 30-seconds-of-code 仓库中 find-matching-bracket-pairs 一文展开，从最简单的圆括号匹配出发，逐步演进到多类型括号、Map 双向索引存储以及可复用（柯里化）的泛化方案。读完本文，你将掌握一种基于栈的 O(n) 线性解法，并能将其直接复用到 HTML 标签校验、Esolang 循环跳转等真实解析场景中。

问题定义：为什么要匹配括号对

假设有一个仅含圆括号的字符串，例如 ((a + b))，我们希望找出其中所有互相匹配的括号对。在这个例子里，答案是 (0, 8) 和 (1, 7)：前者是最外层括号，后者是最内层括号。这里 "匹配" 指的是成对的左括号与右括号在索引上一一对应，且满足嵌套关系正确、不交叉。

仔细分析不难发现规律：

  • 遇到左括号时，我们需要记住它的索引；
  • 遇到右括号时，它能匹配的是最近一次遇到的、尚未配对的左括号；
  • 如果遇到没有左括号可配对的右括号，字符串非法；
  • 如果处理完整串后仍有未配对的左括号，字符串同样非法。

这种 "后进先出" 的配对逻辑，天然对应**栈（Stack）**这一数据结构。由于这里只需要栈的 push() 与 pop() 两个操作，直接用 JavaScript 数组模拟即可，无需引入自定义栈类。如果你希望系统性地了解栈及其在 JavaScript 中的经典实现，可以参考仓库中的 Stack 数据结构一文——它同样位于本仓库，详细讲解了 push、pop、peek、isEmpty 四个基本操作的实现原理。

第一阶段：匹配圆括号的栈解法

使用 Array.prototype.reduce() 一次性遍历字符串，可以在单次线性扫描中同时完成入栈、出栈与配对记录。核心思路：左括号入栈（记录索引），右括号出栈（取回最近左括号的索引）并组成配对；同时用 stack.length === 0 与扫描结束后的 stack.length > 0 两个检查点拦截所有非法输入。

const findMatchingParentheses = str => {
  const { stack, pairs } = [...str].reduce(
    ({ pairs, stack }, char, i) => {
      if (char === '(') stack.push(i);
      else if (char === ')') {
        if (stack.length === 0) throw new Error('Invalid string');
        pairs.push([stack.pop(), i]);
      }
      return { pairs, stack };
    },
    { pairs: [], stack: [] }
  );

  if (stack.length > 0) throw new Error('Invalid string');

  return pairs;
};

findMatchingParentheses('a + b');      // []
findMatchingParentheses('(a + b)');    // [[0, 6]]
findMatchingParentheses('((a + b))');  // [[1, 7], [0, 8]]
findMatchingParentheses('((a + b)');   // Error: Invalid string
findMatchingParentheses('a + b)');     // Error: Invalid string

几个值得注意的细节：

  • [...str] 将字符串按 Unicode 码点展开为字符数组，保证索引 i 对应的是真实字符位置；
  • pairs 数组的配对顺序是内层先、外层后（内层括号先出栈），如 ((a + b)) 得到 [[1, 7], [0, 8]]；
  • 无括号的 'a + b' 返回空数组 []，属于合法输入而非错误；
  • 两个 throw 分别对应 "多余右括号" 与 "未闭合左括号" 两种非法情形。

第二阶段：扩展到多种括号类型

仅匹配圆括号显然不够，实际场景中我们通常要同时处理 ()、[]、{} 三类括号。思路与圆括号版本几乎一致，关键差异在于引入一个括号字典（bracket map）：'(' → ')'、'[' → ']'、'{' → '}'。这样既能判断某个字符是否为左/右括号，又能在弹出左括号时校验它与当前右括号是否属于同一对，杜绝 ([a + b} 这类括号类型交叉的非法输入。

const findMatchingBrackets = str => {
  const bracketMap = {
    '(': ')',
    '[': ']',
    '{': '}',
  };
  const bracketOpenings = Object.keys(bracketMap);
  const bracketClosings = Object.values(bracketMap);

  const { stack, pairs } = [...str].reduce(
    ({ pairs, stack }, char, i) => {
      if (bracketOpenings.includes(char)) stack.push(i);
      else if (bracketClosings.includes(char)) {
        if (stack.length === 0) throw new Error('Invalid string');
        const openingIndex = stack.pop();
        if (bracketMap[str[openingIndex]] !== char)
          throw new Error('Invalid string');
        pairs.push([openingIndex, i]);
      }
      return { pairs, stack };
    },
    { pairs: [], stack: [] }
  );

  if (stack.length > 0) throw new Error('Invalid string');

  return pairs;
};

findMatchingBrackets('a + b');        // []
findMatchingBrackets('(a + b)');      // [[0, 6]]
findMatchingBrackets('((a + b))');    // [[1, 7], [0, 8]]
findMatchingBrackets('([a] + b)');    // [[1, 3], [0, 8]]
findMatchingBrackets('([{a} + b])');  // [[2, 4], [1, 9], [0, 10]]
findMatchingBrackets('((a + b)');     // Error: Invalid string
findMatchingBrackets('a + b)');       // Error: Invalid string
findMatchingBrackets('([a + b}');     // Error: Invalid string

这段代码相对圆括号版本新增了两个关键点：

  1. 括号类型判定：通过 bracketOpenings.includes(char) / bracketClosings.includes(char) 判断当前字符是否为括号，而不再用 if/else 硬编码 ( 和 )；
  2. 配对类型校验：弹出左括号索引后，用 bracketMap[str[openingIndex]] 取出该左括号应当对应的右括号，与当前字符比较，不一致即抛错。这是 ([a + b} 被判定为非法的根本原因——[ 要求匹配 ]，却遇到了 }。

第三阶段：用 Map 存储双向索引

前两个版本把配对结果存成 [[leftIndex, rightIndex], ...] 的数组。但在大多数真实使用场景中，我们往往需要给定一个括号索引，立刻取出它的匹配索引——无论它是左括号还是右括号。此时 Map 明显更方便：它是原生键值对结构，get() / has() 均为 O(1) 查询。

因此，配对时需要在 Map 中同时写入两个方向的映射：pairs.set(openingIndex, i) 与 pairs.set(i, openingIndex)。这样一来，从任何一个括号出发都能 O(1) 拿到它的配对对象。

const findMatchingBrackets = str => {
  const bracketMap = {
    '(': ')',
    '[': ']',
    '{': '}',
  };
  const bracketOpenings = Object.keys(bracketMap);
  const bracketClosings = Object.values(bracketMap);

  const { stack, pairs } = [...str].reduce(
    ({ pairs, stack }, char, i) => {
      if (bracketOpenings.includes(char)) stack.push(i);
      else if (bracketClosings.includes(char)) {
        if (stack.length === 0) throw new Error('Invalid string');
        const openingIndex = stack.pop();
        if (bracketMap[str[openingIndex]] !== char)
          throw new Error('Invalid string');
        pairs.set(openingIndex, i);
        pairs.set(i, openingIndex);
      }
      return { pairs, stack };
    },
    { pairs: new Map(), stack: [] }
  );

  if (stack.length > 0) throw new Error('Invalid string');

  return pairs;
};

const str = '([{a} + b])';
const pairs = findMatchingBrackets(str);

[...str].forEach((char, i) => {
  if (pairs.has(i)) {
    const matchingIndex = pairs.get(i);
    const matchingChar = str[pairs.get(i)];
    console.log(
      `Bracket "${char}" at index ${i} matches with bracket "${matchingChar}" at index ${matchingIndex}`
    );
  }
});
// Bracket "(" at index  0 matches with bracket ")" at index 10
// Bracket "[" at index  1 matches with bracket "]" at index  9
// Bracket "{" at index  2 matches with bracket "}" at index  4
// Bracket "}" at index  4 matches with bracket "{" at index  2
// Bracket "]" at index  9 matches with bracket "[" at index  1
// Bracket ")" at index 10 matches with bracket "(" at index  0

从输出可以看到，Map 对左右两侧都建立了映射，因此遍历任意方向都能检索。这种 "正向 + 反向双向索引" 的设计在解释器实现中尤其常见——例如 Smallfuck 解释器需要根据 [ 的位置找到对应 ]，也需要根据 ] 找到对应 [（详见下文 "仓库实践" 一节）。

第四阶段：泛化为可复用的匹配工厂

到目前为止，括号规则都被硬编码在函数内部。如果想把同一套逻辑复用到 HTML/XML 标签（< 与 >）或其他自定义符号对上，最优雅的做法是把括号规则作为参数传入，并利用柯里化（currying）：findMatchingBrackets(bracketMap) 返回一个新函数，该函数接收字符串并返回配对 Map。这样既能复用同一套栈算法，又能按需配置不同规则。

const findMatchingBrackets = bracketMap => {
  const bracketOpenings = Object.keys(bracketMap);
  const bracketClosings = Object.values(bracketMap);

  return str => {
    const { stack, pairs } = [...str].reduce(
      ({ pairs, stack }, char, i) => {
        if (bracketOpenings.includes(char)) stack.push(i);
        else if (bracketClosings.includes(char)) {
          if (stack.length === 0) throw new Error('Invalid string');
          const openingIndex = stack.pop();
          if (bracketMap[str[openingIndex]] !== char)
            throw new Error('Invalid string');
          pairs.set(openingIndex, i);
          pairs.set(i, openingIndex);
        }
        return { pairs, stack };
      },
      { pairs: new Map(), stack: [] }
    );

    if (stack.length > 0) throw new Error('Invalid string');

    return pairs;
  };
};

const findBracketPairs =
  findMatchingBrackets({ '(': ')', '[': ']', '{': '}' });
const str = '([{a} + b])';
const pairs = findBracketPairs(str);
// Map(6) {
//  0 => 10, 1 => 9, 2 => 4,
//  4 => 2, 9 => 1, 10 => 0
//}

const findHtmlPairs = findMatchingBrackets({ '<': '>' });
const htmlStr = '<div><p>Hello, world!</p></div>';
const htmlPairs = findHtmlPairs(htmlStr);
// Map(8) {
//  0 => 4, 5 => 7, 21 => 24, 25 => 30,
//  30 => 25, 24 => 21, 7 => 5, 4 => 0
// }

这个泛化版本的价值体现在：

  • 规则即参数：只要提供 { 开符号: 闭符号 } 字典，任何成对符号都能匹配；
  • 一次配置、多次使用：findBracketPairs 与 findHtmlPairs 各自绑定了一套规则，可被反复调用；
  • 柯里化带来的可组合性：关于柯里化的完整原理（基于 Function.prototype.length 的递归实现、变参函数与 bind 结合等），可阅读仓库中的 JavaScript 柯里化一文。

需要特别提醒的是：用 <、> 匹配 HTML 标签只是字符级的近似，真实 HTML 标签是多字符 token（如 <div>、</p>），单字符括号算法无法直接处理标签名与属性，需要更完整的 tokenizer（见下文仓库实践）。

复杂度与边界行为分析

时间复杂度：整个过程只对字符串做一次线性扫描，每个字符至多入栈一次、出栈一次，Map/数组操作均为 O(1)，因此整体为 O(n)，n 为字符串长度。

空间复杂度：栈最多存放所有左括号索引，pairs 最多存放 n/2 对映射，因此空间复杂度同样为 O(n)。

边界行为归纳：

输入情形 行为
无任何括号（如 'a + b'） 返回空数组 / 空 Map，视为合法
括号完全配对（如 '((a + b))'） 返回全部配对，内层在前
多余右括号（如 'a + b)'） 弹出时栈为空，抛 Error('Invalid string')
未闭合左括号（如 '((a + b)'） 扫描结束栈非空，抛 Error('Invalid string')
括号类型交叉（如 '([a + b}'） 弹出时类型校验失败，抛 Error('Invalid string')
空字符串 '' 不进入分支，栈与 pairs 均为空，返回空结果

仓库实践：从括号匹配到 Tokenizer 与解释器

在 30-seconds-of-code 仓库中，本文被归入 JavaScript Tokenizers & Interpreters 集合（journeyId: js/tokenizers-interpreters）。该集合将 find-matching-bracket-pairs、parse-reverse-polish-notation、math-expression-tokenizer、simple-html-tokenization-validation、smallfuck-interpreter、brainfuck-interpreter 等文章串联成一条从基础算法到完整解释器的学习路径。括号匹配算法正是贯穿这条路径的核心构件：

1. Reverse Polish Notation 解析

在 parse-reverse-polish-notation 中，后缀表达式（RPN）的求值同样依赖一个栈：逐 token 入栈，遇到运算符时弹出最近的两个操作数计算结果再压回栈。文章明确引用了本括号匹配文章作为栈思路的起点——同一套 LIFO 思想，在不同问题上的两次应用。

2. 数学表达式 Tokenizer

math-expression-tokenizer 把表达式拆解为数字、运算符、括号等 token，处理浮点数与负数等边界。括号的嵌套结构随后可以由括号匹配算法验证与索引，为更复杂的表达式解析器打基础。

3. HTML Tokenization 与标签配对

simple-html-tokenization-validation 把括号匹配推广到了 HTML：先由 tokenizer 将字符串切分为 tag / text 两类 token，再对 tag token 执行同样的栈式配对——遇到开标签入栈、遇到闭标签弹出并比对标签名，不匹配则抛错。文中实现 findMatchingTags 时的 pairs 同样是双向 Map，与本文第三阶段的做法一一对应，是理解 "从字符级匹配到 token 级匹配" 的绝佳续篇。

4. Smallfuck 解释器中的循环跳转

最直接的实战应用出现在 smallfuck-interpreter 中。Smallfuck 是仅有 6 条指令的 Esolang，其中 [ 与 ] 表示条件循环，解释器必须预先把所有 [ / ] 配对索引存入 Map（函数 createLoopPairs），执行到 [ 或 ] 时通过 pairMatch 查出跳转目标。其核心实现：

const createLoopPairs = code =>
  [...code].reduce(({ pairs, stack }, symbol, i) => {
    if (symbol === '[') stack.push(i);
    else if (symbol === ']') {
      const openIndex = stack.pop();
      pairs.set(openIndex, i);
      pairs.set(i, openIndex);
    }
    return { pairs, stack };
  }, { pairs: new Map(), stack: [] }).pairs;

可以看到，这与本文 Map 版本的括号匹配几乎是同构的——只是符号从 () 换成了 []，用途从 "找出所有配对" 变成了 "生成循环跳转表"。这正是原文档结论中所说的 "可以轻松扩展为 tokenizer 以解析多字符 token（如完整 HTML 标签）" 的仓库级实证。

总结

括号匹配问题看似简单，却是解析器与解释器工程的基石。本文梳理了它在 30-seconds-of-code 仓库中的完整演进路线：

  1. 栈是核心：LIFO 语义天然契合 "最近开括号与当前闭括号配对" 的规则；
  2. 字典引入类型校验：bracketMap 让多类型括号的交叉错配也能被准确拦截；
  3. Map 双向索引：让从任意括号 O(1) 检索配对成为可能，贴合解释器跳转需求；
  4. 柯里化泛化：把括号规则参数化，一套栈算法可复用于 HTML 标签、Esolang 循环等任意成对符号；
  5. 仓库串联验证：从 RPN 解析、数学表达式 tokenizer、HTML 标签校验到 Smallfuck 解释器，括号匹配算法贯穿 tokenizers-interpreters 集合 的每一步实现。

无论你是在写 CodeWars 的 Esolang 解释器 Kata、构造自己的表达式解析器，还是实现简易 HTML 校验器，这段约 20 行的栈代码都可以作为你解析工具箱里的常备零件，按需扩展。

登录后查看全文
教程文档
版权声明：本文由 AtomGit 博客平台 AIGC 生成并经审核发布，遵循 CC 4.0 BY-SA 版权协议，转载请注明出处。
30-seconds-of-code

相关推荐

30 seconds of code：用 replaceLast 在 JavaScript 字符串中替换最后一个匹配项
本文围绕 30 seconds of code 仓库中的 replace-last-occurrence 代码片段，系统讲解如何在 JavaScript 中替换字符串中**最后一次**出现的匹配模式。你将从零理解其核心算法（正则取末次匹配 + `lastIndexOf` 定位 + `slice` 拼
教程 605
30 Seconds of Code：用 Blob 精确计算 JavaScript 字符串字节大小
本文讲解如何精确计算 JavaScript 字符串的字节大小（byte size），核心方案来自 30 Seconds of Code 仓库中的 byte-size.md 代码片段：利用 `Blob` 对象将字符串按 UTF-8 编码后读取其字节数，一行代码即可正确处理 emoji、中文等非 ASC
教程 1913
30 Seconds of Code 实战：JavaScript 中查询字符串（Query String）与对象的双向转换
本文基于 30-seconds-of-code 仓库中 query-string-to-object.md 一文展开，讲解如何在 JavaScript 中把 URL 查询字符串解析为对象、以及把对象序列化为查询字符串的完整方案。读完本文，你将掌握基于 `URLSearchParams` 与 `Obj
教程 736
上一篇：gbe_fork steamclient 模式实战指南：ColdClientLoader 启动器、配置项与 DLL 注入全解析下一篇：OpenAvatarChat 集成 Edge TTS Handler：零 API Key 使用微软云端语音合成

热门文章

Awesome 清单宣言解读：遵循 awesome 社区标准打造高质量精选资源列表的完整指南 HOT
文档 2674
Awesome 列表贡献指南：从首次提交到 Pull Request 合并的完整实战流程
文档 2520
dgoss 容器测试指南：用 goss 在 Docker 容器内快速验证镜像
测试 2166