[查漏补缺]正则表达式匹配算法

516 阅读2分钟
The fool doth think he is wise, but the wise man knows himself to be a fool. 
愚者总自以为聪明,智者则有自知之明。

引言

智者千虑,必有一失;愚者千虑,必有一得。在很多文本编辑器里,正则表达式通常被用来检索、替换那些匹配某个模式的文本。正则表达式也是前后端通吃,百无禁忌。

正则表达式中,最重要的就是通配符。用到的思想还是回溯算法。

在这里做了一个简易版的正则表达式实现。只包含两种通配符:

  • * 匹配任意多个(大于等于 0 个)任意字符
  • ?匹配零个或者一个任意字符

所有源码均已上传至github:链接

实现

分析

  1. 依次考察正则表达式中的每个字符,当是非通配符时,就直接跟文本的字符进行匹配,如果相同,则继续往下处理;如果不同,则回溯。
  2. 如果遇到特殊字符的时候,根据通配符来处理不同的匹配方案。如果匹配到无法匹配的时候,则进行回溯,重新选择一种匹配方案,然后再继续匹配剩下的字符。

初始化

    /**
     * 标识
     */
    private boolean match;
    /**
     * 正则表达式
     */
    private char[] patChars;
    /**
     * 长度
     */
    private int plen;

    /**
     * 初始化
     *
     * @param patten 正则表达式
     */
    private Pattern(String patten) {
        patChars = patten.toCharArray();
        this.plen = patChars.length;
        match = false;
    }

匹配

    private boolean isMatch(String txt) {
        match = false;
        char[] txtChars = txt.toCharArray();
        int tlen = txtChars.length;
        recursiveMatch(0, 0, txtChars, tlen);
        return match;
    }

回溯算法

这里其实就是一个大型的if-else,判断符合哪一种情况,然后进行递归。如果再加几种情况,也就是多加一个if-else,这样的话if-else嵌套层级太多,可以考虑使用switch或者使用设计模式,这是后话,暂且不提。

    private void recursiveMatch(int ti, int pj, char[] txtChars, int tlen) {
        if (match) return;
        if (pj == plen) {
            if (ti == tlen) match = true;
            return;
        }

        if (patChars[pj] == '*') {//* 任意字符
            for (int i = 0; i < tlen - ti; i++) {
                recursiveMatch(ti + i, pj + 1, txtChars, tlen);
            }
        } else if (patChars[pj] == '?') {//? 0 or 1
            recursiveMatch(ti, pj + 1, txtChars, tlen);
            recursiveMatch(ti + 1, pj + 1, txtChars, tlen);
        } else if (ti < tlen && patChars[pj] == txtChars[ti]) {
            recursiveMatch(ti + 1, pj + 1, txtChars, tlen);
        }
    }

测试代码

    public static void main(String[] args) {
        String patten = "*@c?.com";
        Pattern pattern = new Pattern(patten);
        String txtT = "666@cc.com";
        boolean resT = pattern.isMatch(txtT);
        System.out.println(txtT + "的匹配结果:"  + resT);
        String txtF = "666@c.con";
        boolean resF = pattern.isMatch(txtF);
        System.out.println(txtF + "的匹配结果:"  + resF);
    }

测试结果


常用的正则表达式

匹配网站

/((ht|f)tp(s)?:)?(\/\/*)?(w{3}.*)?[-A-Za-z0-9+&@#/%?=~_|!:,.;]+[-A-Za-z0-9+&@#/%=~_|]/g

其他:传送门

end


您的点赞和关注是对我最大的支持,谢谢!