实现正则表达式匹配算法

前言

在正则表达式匹配规则中：.代表任意一个字符；* 代表它前面的字符可以出现任意次（含0次）。例如：字符串dpaaab与规则d.a*b匹配（所有字符匹配模式）。

本文将带着大家实现这个匹配算法，欢迎各位感兴趣的开发者阅读本文。

实现思路

接下来，我们来分析下字符串与规则之间的比对思路：

• 比对两个字符串同一位置的字符：同位置的字符相等或者当前位置的字符为.则满足相等条件
• 规则字符数>1且当前字符串的下一位字符等于*，则执行下述两个条件，满足任意一个即可：
  • 字符串保持不变，从规则字符的下下位开始递归（*前面的字符可以出现任意次数，故从*后面开始寻找）进行比对获取结果
  • 同位置的字符符合相等条件且规则字符串保持不变从字符串的下一位开始递归进行比对获取结果
• 否则，同位置的字符符合相等条件且从字符串与匹配字符的下一位开始递归进行比对获取结果

我们将上述思路代入前言的例子中，它的递归栈就如下图所示：

image-20220328220443088

实现代码

有了思路后，我们就可以愉快的写出代码了，如下所示（完整代码请从 示例代码 章节获取）：

  /**
   * 匹配.与*的正则表达式
   *  1. .代表可以匹配任意字符
   *  2. *代表它前面的字符可以出现任意次数
   * @param str
   * @param pattern
   */
  public match(str: string, pattern: string): boolean {
    if (pattern.length === 0) {
      return str.length === 0;
    }
    // 相同位置的字符相等或者当前位置的字符为.代表匹配成功
    const matchResult =
      str.length > 0 &&
      (str.charAt(0) === pattern.charAt(0) || pattern.charAt(0) === ".");
    // 有*
    if (pattern.length > 1 && pattern.charAt(1) === "*") {
      // *前面的字符可以出现任意次数，故：从*后面开始寻找递归寻找
      return (
        this.match(str, pattern.substring(2)) ||
        (matchResult && this.match(str.substring(1), pattern))
      );
    } else {
      // 无*
      return matchResult && this.match(str.substring(1), pattern.substring(1));
    }
  }

接下来，我们写一个测试用例，将前言中的例子代入，再举一个不符合条件的例子（完整代码请从 示例代码 章节获取）

const regExprMatch = new RegExprMatch();
let result = regExprMatch.match("dpaaab", "d.a*b");
console.log("匹配结果", result);
result = regExprMatch.match("dsaaap", "d.a*b");
console.log("匹配结果", result);

执行结果如下所示：

image-20220328221746809

示例代码

本文所用代码的完整版本请移步：

• RegExprMatch.ts[1]
• regExprMatch-test.ts[2]

写在最后

至此，文章就分享完毕了。

我是神奇的程序员，一位前端开发工程师。

参考资料

[1]RegExprMatch.ts: https://github.com/likaia/algorithm-practice/blob/f4d1827a7a1ff61d17985c21719ceed62af3405e/src/RegExprMatch.ts#L9

[2]regExprMatch-test.ts: https://github.com/likaia/algorithm-practice/blob/f4d1827a7a1ff61d17985c21719ceed62af3405e/src/test-case/regExprMatch-test.ts#L3

[3]个人网站: https://www.kaisir.cn/