正则表达式完全指南：从入门到精通

正则表达式完全指南：从入门到精通

The Complete Guide of Regular Expression: Beginner to Mastery

一、简介 | Introduction

1.1 什么是正则表达式

正则表达式（Regular Expression）是一种用于描述字符串匹配模式的工具。它由一系列特殊字符和普通字符组成，可以用来检索、替换、提取那些符合某个模式的文本。

1.2 发展历史

正则表达式的概念最早由美国数学家斯蒂芬·科尔·克莱尼（Stephen Cole Kleene）于 1951 年提出，用于描述正则语言（即正规语言，能够被有限自动机识别的字符串集合）。1968 年，肯尼斯·蓝·汤普森（Ken Thompson） 将其引入文本编辑器 QED 和 Unix 的 ed 编辑器中，此后逐渐发展出 POSIX 标准和 Perl 风格两大流派，并被几乎所有现代编程语言所支持。

1.3 为什么需要正则表达式

在没有正则表达式的情况下，验证邮箱合法性可能需要写几十行 if-else 代码；而使用正则表达式则十分简洁：

1

^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$

正则表达式广泛应用于：表单验证、批量替换、数据爬取、语法高亮等大家所熟悉的功能。

二、原理 | Principle

2.1 有限状态自动机

正则表达式的原理是有限自动机（Finite Automaton，FA，即由五个主要要素组成的一个顺序系统）。一个正则表达式在匹配时，本质上是在状态机中不断转移状态的过程。

例如正则表达式 ab*c 可以理解为：

1

起始状态 --a--> 状态1 --b*--> 状态2 --c--> 接受状态

当输入字符串沿状态转移路径最终到达"接受状态"时，匹配成功。

2.2 两种引擎

常用的正则表达式的实现引擎有两种，分别是DFA（Deterministic finite automation, 确定有限自动机）和NFA（Nondeterministic Finite Automaton, 非确定有限自动机）。

前者每个状态对每个输入只有唯一转移，效率高但功能受限；后者效率较低，但是支持回溯操作，功能更强，选择更多。

2.3 回溯机制

大多数现代语言使用回溯 NFA引擎。匹配时，引擎会尝试一条路径，若失败则回退到上一个选择点尝试其他路径。

例如用 a.*b 匹配 axxbxxb：

1. a 匹配第一个字符

2. .* 剩余所有字符均被接受

3. 发现后面没有 b 了，开始回溯

4. 回退到最后一个 b，匹配成功

然而，很显然地，回溯可能导致性能问题，如经典的 (a+)+b 面对大量 a 时会产生灾难性回溯（Catastrophic Backtracking）。

三、语法 | Grammar

3.1 普通字符

3.2 非打印字符

3.3 特殊字符

3.3.1 贪婪与非贪婪

称一个符号是贪婪的，即它会尽可能多的匹配；称一个符号是非贪婪的，即它会尽可少多的匹配。在贪婪的符号后加上?即可将其转换为非贪婪。

1
2
3

字符串：<div>Hello</div>
贪婪：<.*>  匹配 <div>Hello</div>
懒惰：<.*?> 匹配 <div> 和 </div> 

3.4 限定符

3.4 分组

3.5 断言

3.6 常用修饰符

四、应用 | Application

5.1 验证合法性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 邮箱
^[\w.%+-]+@[\w.-]+\.[A-Za-z]{2,}$

# 手机号（中国大陆）
^1[3-9]\d{9}$

# 身份证号（18 位）
^[1-9]\d{5}(18|19|20)\d{2}(0[1-9]|1[0-2])(0[1-9]|[12]\d|3[01])\d{3}[\dXx]$

# URL
^https?://[\w.-]+(:\d+)?(/[\w./?%&=]*)?$

# IPv4
^((25[0-5]|2[0-4]\d|[01]?\d\d?)\.){3}(25[0-5]|2[0-4]\d|[01]?\d\d?)$

# 日期（YYYY-MM-DD）
^\d{4}-(0[1-9]|1[0-2])-(0[1-9]|[12]\d|3[01])$

# 密码（8-16位，含大小写和数字）
^(?=.*[a-z])(?=.*[A-Z])(?=.*\d)[A-Za-z\d@$!%*?&]{8,16}$

5.2 查询/更改

• 驼峰转下划线：([a-z])([A-Z]) -> $1_$2，再转小写

• 删除空行：查找 ^\s*\n 替换为空

• …

5.3 OI中高效实现程序

例如对于P7911 [CSP-J 2021] 网络连接，有一步需要判断地址串是否合法，如果用判断写需要如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

bool check(char s[]){
	int a=-1,b=-1,c=-1,d=-1,e=-1;
	int t=sscanf(s,"%d.%d.%d.%d:%d",&a,&b,&c,&d,&e);//尝试读入，保存至s中
	if(t!=5) return 0;//没有5个肯定不行
	if(a<0||a>255) return 0;
	if(b<0||b>255) return 0;
	if(c<0||c>255) return 0;
	if(d<0||d>255) return 0;
	if(e<0||e>65535) return 0;//判断
	char s2[35];
	sprintf(s2,"%d.%d.%d.%d:%d",a,b,c,d,e);//保存至s2中
	int lens=strlen(s);//接下来判断s2和s是否一样
	bool ok=0;
	for(int i=0;i<lens;i++){
		if(s[i]==s2[i]) ok=1;
		else{
			ok=0;
			break;
		}
	}
	return ok;
}

但是如果使用正则表达式仅需要如下代码：

1
2
3
4
5

smatch results;
regex r("(([0-9])|([1-9][0-9])|(1[0-9][0-9])|(2[0-4][0-9])|(25[0-5]))[.](([0-9])|([1-9][0-9])|(1[0-9][0-9])|(2[0-4][0-9])|(25[0-5]))[.](([0-9])|([1-9][0-9])|(1[0-9][0-9])|(2[0-4][0-9])|(25[0-5]))[.](([0-9])|([1-9][0-9])|(1[0-9][0-9])|(2[0-4][0-9])|(25[0-5]))[:](([0-9])|([1-9][0-9])|([1-9][0-9][0-9])|([1-9][0-9][0-9][0-9])|([1-5][0-9][0-9][0-9][0-9])|(6[0-4][0-9][0-9][0-9])|(65[0-4][0-9][0-9])|(655[0-2][0-9])|(6553[0-5]))");
if(regex_match(ad,r)){
	...
}	

5.4 寻找单词/短语

例如匹配网站Nutrimatic便使用了正则表达式的语法和部分拓展，使用它便可轻松匹配符合特定格式的单词/短语，按频率依次排列。

例如使用_t_t_t_即可轻松匹配到statute和其它结果。

六、总结 | Summary

正则表达式是一门投入小、回报大、还能装点小逼的技能，十分建议学习。

掌握正则表达式，绝对能让你的文本处理效率提升一个数量级，并能在各种地方发现它，运用它。

理解、阅读、思辨

参考资源：

• MDN Web Docs - Regular Expressions

• 正则表达式 - 百度百科

• cppreference - Regular expressions

• regex101.com

• 正则表达式 - 菜鸟教程

• 博客园、知乎与CSDN的各种文章