侧边栏壁纸
博主头像
神奇的程序员

今天的努力只为未来

  • 累计撰写 170 篇文章
  • 累计创建 27 个标签
  • 累计收到 226 条评论

目 录CONTENT

文章目录

实现正则表达式匹配算法

神奇的程序员
2022-03-28 / 0 评论 / 1 点赞 / 768 阅读 / 1,518 字 正在检测是否收录...

前言

在正则表达式匹配规则中:.代表任意一个字符;* 代表它前面的字符可以出现任意次(含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

示例代码

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

写在最后

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

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

如果你对我感兴趣,请移步我的个人网站,进一步了解。

  • 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
  • 本文首发于神奇的程序员公众号,未经许可禁止转载💌
1

评论区