如何编写解析带嵌套括号字符串并转为数组的函数？

需求 #

需要实现一个函数，解析如下格式的字符串：

GEYDQORRGM5D[C[M[A,I,Q,Y],NA],O,Q,S]

将其转换为完全展开的数组，预期输出：

[
  "GEYDQORRGM5DCMA",
  "GEYDQORRGM5DCMI",
  "GEYDQORRGM5DCMQ",
  "GEYDQORRGM5DCMY",
  "GEYDQORRGM5DCNA",
  "GEYDQORRGM5DO",
  "GEYDQORRGM5DQ",
  "GEYDQORRGM5DS",
]

现有问题 #

我尝试了以下代码，但无法处理嵌套括号的场景，输出结果不符合预期：

function splitAndAddString() {
    let regex = /([A-Z0-9]+)(?:\[([A-Z,]+)\])?/g
    const result = []

    let match;
    while ((match = regex.exec(input)) !== null) {
        const prefix = match[1];
        const suffixes = match[2] ? match[2].split(",") : [""];
        for (const suffix of suffixes) {
            result.push(prefix + suffix);
        }
    }


    const newResult = []
    for (let i = 1; i < result.length; i++) {
        newResult.push(result[0] + result[i])
    }

    return newResult
}

const input = 'GEYDQORRGM5D[C[M[A,I,Q,Y],NA],O,Q,S]';
const output = splitAndAddString(input);
console.log(output);

现有代码输出：

[
  "GEYDQORRGM5DC",
  "GEYDQORRGM5DMA",
  "GEYDQORRGM5DMI",
  "GEYDQORRGM5DMQ",
  "GEYDQORRGM5DMY",
  "GEYDQORRGM5DNA",
  "GEYDQORRGM5DO",
  "GEYDQORRGM5DQ",
  "GEYDQORRGM5DS",
]

问题根源：正则表达式无法处理嵌套结构，只能拆分最外层的括号内容，导致嵌套层级的前缀（比如C和M）没有正确拼接。

解决方案：递归处理嵌套结构 #

因为字符串存在多层嵌套的括号，需要用递归遍历每一层结构，逐层展开拼接：

function parseNestedString(str) {
  let index = 0;

  // 递归解析函数，处理当前层级的内容
  function parse() {
    let currentResults = [''];
    while (index < str.length) {
      const char = str[index];
      
      if (char === '[') {
        index++;
        // 递归解析括号内的嵌套内容
        const nestedResults = parse();
        // 笛卡尔积拼接当前结果与嵌套结果
        const temp = [];
        for (const prefix of currentResults) {
          for (const suffix of nestedResults) {
            temp.push(prefix + suffix);
          }
        }
        currentResults = temp;
      } else if (char === ']') {
        index++;
        // 遇到右括号，返回当前层级的所有展开结果
        return currentResults;
      } else if (char === ',') {
        index++;
        // 遇到逗号，新增一个空字符串作为新选项的起始
        currentResults.push('');
      } else {
        // 普通字符，追加到当前所有结果的末尾
        for (let i = 0; i < currentResults.length; i++) {
          currentResults[i] += char;
        }
        index++;
      }
    }
    return currentResults;
  }

  return parse();
}

// 测试示例
const input = 'GEYDQORRGM5D[C[M[A,I,Q,Y],NA],O,Q,S]';
const output = parseNestedString(input);
console.log(output);

代码逻辑说明 #

• 用全局索引index追踪遍历位置，避免重复处理字符
• 递归函数parse负责处理当前层级的字符串：
  • 遇到普通字符时，将字符追加到当前所有结果的末尾
  • 遇到[时，递归解析括号内的内容，然后将当前结果与递归得到的子结果进行笛卡尔积拼接，实现层级嵌套的展开
  • 遇到]时，返回当前层级的所有展开结果，供上层拼接
  • 遇到,时，添加新的空字符串，代表一个新的选项分支

内容的提问来源于stack exchange，提问作者Asher G