如何实现正则表达式按最小匹配长度从低到高排序

要实现按正则表达式的最小匹配字符数（最不贪婪到最贪婪）排序，你需要自己编写一个函数来计算每个正则的最小匹配长度，再用这个函数作为排序依据。

核心思路 #

正则的"贪婪程度"在这里定义为可匹配的最小字符数，计算规则如下：

• 普通字符（包括转义字符如\.）：每个算1个字符
• 字符类（如[eo]）：算1个字符（最少匹配1个）
• 量词：取最小匹配次数：
  • * → 0次，+ → 1次，? → 0次
  • {n,} → n次，{n,m} → n次
• 分组（如(foo)）：仅计算分组内的字符长度，分组本身不影响长度

实现代码 #

首先编写计算最小匹配长度的函数：

function calculateMinMatchLength(regex) {
  const source = regex.source;
  let totalLength = 0;
  let index = 0;
  const sourceLength = source.length;

  while (index < sourceLength) {
    const currentChar = source[index];

    // 处理转义字符（如 \. \*），算作1个字符
    if (currentChar === '\\') {
      totalLength += 1;
      index += 2;
      continue;
    }

    // 处理字符类（如 [eo]），算作1个字符
    if (currentChar === '[') {
      totalLength += 1;
      // 跳过字符类内容直到闭合 ]
      while (index < sourceLength && source[index] !== ']') {
        if (source[index] === '\\') index++; // 跳过转义符
        index++;
      }
      index++; // 跳过闭合的 ]
      continue;
    }

    // 处理分组（如 (foo)），计算分组内的字符长度
    if (currentChar === '(') {
      index++; // 跳过 (
      // 处理嵌套分组的情况
      let groupDepth = 1;
      while (index < sourceLength && groupDepth > 0) {
        const innerChar = source[index];
        if (innerChar === '(') groupDepth++;
        else if (innerChar === ')') groupDepth--;
        else if (innerChar === '\\') {
          totalLength += 1;
          index += 2;
          continue;
        } else if (innerChar === '[') {
          totalLength += 1;
          while (index < sourceLength && source[index] !== ']') {
            if (source[index] === '\\') index++;
            index++;
          }
          index++;
          continue;
        } else {
          totalLength += 1;
        }
        index++;
      }
      continue;
    }

    // 处理量词逻辑
    let unitLength = 1;
    index++;
    // 检查当前位置是否是量词
    if (index < sourceLength) {
      const quantifier = source[index];
      if (quantifier === '*' || quantifier === '+' || quantifier === '?') {
        const minCount = quantifier === '+' ? 1 : 0;
        totalLength += unitLength * minCount;
        index++;
        continue;
      } else if (quantifier === '{') {
        index++; // 跳过 {
        // 提取最小次数的数字
        let minNumStr = '';
        while (index < sourceLength && /\d/.test(source[index])) {
          minNumStr += source[index];
          index++;
        }
        const minCount = parseInt(minNumStr, 10);
        // 跳过剩余的量词内容直到 }
        while (index < sourceLength && source[index] !== '}') index++;
        index++; // 跳过 }
        totalLength += unitLength * minCount;
        continue;
      }
    }
    // 无量词时，直接累加当前单元长度
    totalLength += unitLength;
  }

  return totalLength;
}

然后用这个函数对正则数组排序：

let patterns = [
    /foo+ba+r/,
    /foo/,
    /foo+bar/,
    /foobar/,
    /m[eo]{4,}w/,
    /boo/,
    /fooo*/,
    /meow/
];

// 按最小匹配长度升序排序（最不贪婪到最贪婪）
patterns.sort((p1, p2) => calculateMinMatchLength(p1) - calculateMinMatchLength(p2));

console.log(patterns);
// 输出结果与预期一致：
// [/foo/, /boo/, /fooo*/, /meow/, /foobar/, /foo+bar/, /m[eo]{4,}w/, /foo+ba+r/]

注意事项 #

• 本方案针对你的示例场景优化，若需处理更复杂的正则（如零宽断言、Unicode转义等），需要进一步扩展函数逻辑。
• 正则的修饰符（如g、i）不影响最小匹配长度，因此无需处理。

内容的提问来源于stack exchange，提问作者cael ras