The fool doth think he is wise, but the wise man knows himself to be a fool.
愚者总自以为聪明,智者则有自知之明。
引言
智者千虑,必有一失;愚者千虑,必有一得。在很多文本编辑器里,正则表达式通常被用来检索、替换那些匹配某个模式的文本。正则表达式也是前后端通吃,百无禁忌。
正则表达式中,最重要的就是通配符。用到的思想还是回溯算法。
在这里做了一个简易版的正则表达式实现。只包含两种通配符:
- * 匹配任意多个(大于等于 0 个)任意字符
- ?匹配零个或者一个任意字符
所有源码均已上传至github:链接
实现
分析
- 依次考察正则表达式中的每个字符,当是非通配符时,就直接跟文本的字符进行匹配,如果相同,则继续往下处理;如果不同,则回溯。
- 如果遇到特殊字符的时候,根据通配符来处理不同的匹配方案。如果匹配到无法匹配的时候,则进行回溯,重新选择一种匹配方案,然后再继续匹配剩下的字符。
初始化
/**
* 标识
*/
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
您的点赞和关注是对我最大的支持,谢谢!