preface

In regular expression matching rules:. Represents any character. * indicates that the character before it can appear any number of times (including 0). For example, the string dpaaab matches the rule d.a*b (all character matching patterns).

This article will take you through the implementation of the matching algorithm. Interested developers are welcome to read this article.

Implementation approach

Next, let’s analyze the alignment between strings and rules:

  • Aligns characters at the same position of two strings: characters at the same position are equal or characters at the current position are.The equality condition is satisfied
  • Rule number of characters >1 and the next character of the current string is equal to*If either of the following conditions is met:
    • The string remains the same, recursively starting at the bottom of the regular character (*The preceding character can occur any number of times, so from*Then start to look for) for comparison to obtain results
    • Characters in the same position are equal and the regular string remains the same and the result is obtained by recursive alignment starting at the next bit of the string
  • Otherwise, characters in the same position meet the equality condition and are recursively compared from the next bit of the string to the matching character

We substitute the above idea into the foreword example, whose recursive stack looks like this:

The implementation code

With that in mind, we can happily write code like this (see the sample code section for the full code) :

  /** * matches. The regular expression * 1.. means it can match any character * 2. * means it can be preceded by any number of characters *@param str
   * @param pattern* /
  public match(str: string.pattern: string) :boolean {
    if (pattern.length === 0) {
      return str.length === 0;
    }
    // Characters in the same position are equal or characters in the current position are. Indicates the match is successful
    const matchResult =
      str.length > 0 &&
      (str.charAt(0) === pattern.charAt(0) || pattern.charAt(0) = = =".");
    // 有*
    if (pattern.length > 1 && pattern.charAt(1) = = ="*") {
      // The character before * can occur any number of times, so: start the search recursively after *
      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)); }}Copy the code

Next, we write a test case, plugging in the example from the introduction, and giving an example that doesn’t meet the criteria (see the sample code section for the full code)

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

Copy the code

The following information is displayed:

The sample code

For the full version of the code used in this article, go to:

  • RegExprMatch.ts

  • regExprMatch-test.ts

Write in the last

At this point, the article is shared.

I’m an amazing programmer, a front-end developer.

If you are interested in me, please visit my personal website for further information.

  • If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
  • This article was first published in the magic programmer public number, without permission to prohibit reprinting 💌