正则表达式详解

[$\Huge\text{\color{aqua}更好的阅读体验在这里}$](https://0and1story.github.io/) **目录：** 0. 序言 1. 什么是正则表达式？ 2. 正则表达式语法： 理论 基本语法 选择 数量限定 匹配 PCRE表达式 Unicode处理 POSIX字符组 优先级 常用正则 示例 3. C++中正则表达式的使用方法： 1. 检查身份证号： 2. 检索HTML文件里的所有网页链接： 3. 简易Markdown转HTML： 4. 正则表达式在OI上的应用：(虽然应该不能用) 4. 总结 ------ ### 0. 序言 `正则表达式`是现在很火的一个计算机科学概念，在`字符串处理`上有很广泛的应用。 现在很多语言都加入了正则表达式的内容，像`Python`、`PHP`、`JavaScript`都支持正则表达式。 当然，`C++`也不例外，在`C++11`(-0x1x)的标准中就加入了对正则表达式的支持， 在`C++17`(-0x1z)中更是加入了对多行正则_(multiline)_的支持。 下面我就主要使用C++对正则表达式进行一个简单的讲解。 ------ ### 1. 什么是正则表达式？ **正则表达式**（英语：_**Regular Expression**_，在代码中常简写为`regex`、`regexp`或`RE`~~(emmm...OIer都知道这意味着什么)~~），又称**正规表示式**、**正规表示法**、**正规表达式**、**规则表达式**、**常规表示法**，是`计算机科学`的一个概念。正则表达式使用单个字符串来描述、匹配一系列匹配某个句法规则的字符串。在很多文本编辑器里，正则表达式通常被用来**检索、替换**那些匹配某个模式的文本。 > 以上部分引用自维基百科条目: [正则表达式](https://zh.wikipedia.org/wiki/正则表达式) 通俗来说：**正则表达式就是用来在一个字符串中查找符合条件的子串，并且对字串进行如替换等操作的** ------ ### 2. 正则表达式语法： #### 理论 > 温馨提示：此部分较反人类，看不懂属正常现象 > > 看不懂请移步：**[基本语法](#基本语法)** 正则表达式可以用[形式化语言](https://zh.wikipedia.org/wiki/形式化语言)理论的方式来表达。正则表达式由常量和算子组成，它们分别表示字符串的集合和在这些集合上的运算。给定有限字母表Σ定义了下列常量： - [空集](https://zh.wikipedia.org/wiki/空集)$\varnothing$表示集合$\varnothing$。 - [空串](https://zh.wikipedia.org/wiki/空串)$\varepsilon$表示集合$\{\varepsilon\}$。 - [文字字符](https://zh.wikipedia.org/w/index.php?title=字符串文字&action=edit&redlink=1)在$\Sigma$中的$a$表示集合$\{a\}$。 定义了下列运算： - [串接](https://zh.wikipedia.org/wiki/串接)$RS$表示集合$\{\alpha \beta \mid \alpha \in R,\beta \in S\}$。例如：$\{ab,c\}\{d,ef\}=\{abd,abef,cd,cef\}$。 - 选择$R|S$表示$R$和$S$的[并集](https://zh.wikipedia.org/wiki/并集)。例如：$\{ab,c\}|\{ab,d,ef\}=\{ab,c,d,ef\}$。 - [Kleene星号](https://zh.wikipedia.org/wiki/Kleene星号)$R^*$表示包含$\varepsilon$并且[闭合](https://zh.wikipedia.org/wiki/闭包_(数学))在字符串串接下的$R$的最小[子集](https://zh.wikipedia.org/wiki/子集)。这是可以通过$R$中的零或多个字符串的串接得到所有字符串的集合。例如：$\{ab,c\}^{*}=\{\varepsilon ,ab,c,abab,abc,cab,cc,ababab,\cdots \}$。 上述常量和算子形成了[克莱尼代数](https://zh.wikipedia.org/wiki/克莱尼代数)。 很多课本使用对选择使用符号$\cup$、$+$或$\vee$替代竖线。 为了避免括号，假定Kleene星号有最高优先级，接着是串接，接着是并集。如果没有歧义则可以省略括号。例如：`(ab)c`可以写为`abc`而`a|(b(c*))`可以写为`a|bc*`。 例子： - `a|b*`表示$\{\varepsilon ,a,b,bb,bbb,\cdots \}$。 - `(a|b)*`表示由包括空串、任意数目个*a*或*b*字符组成的所有字符串的集合：$\{\varepsilon ,a,b,aa,ab,ba,bb,aaa\cdots \}$。 - `ab*(c|ε)`表示开始于一个*a*接着零或多个*b*和最后一个可选的*c*组成的字符串的集合：$\{a,ac,ab,abc,abb,abbc\cdots \}$。 正则表达式为了避免多余的量词，定义了`?`和`+`，例如；`aa*`可以被表达为`a+`；`(a|ε)`可以被表达为`a?`。有时增加补算子$\sim$；$\sim R$表示在$\Sigma ^{*}$上但不在$R$中的所有字符串的集合。补算子是多余的，因为它可以使用其他算子来表达（尽管计算这种表示的过程是复杂的，而结果可能以指数增大）。 这种意义上的正则表达式可以表达[正则语言](https://zh.wikipedia.org/wiki/正则语言)，精确的是可被[有限状态自动机](https://zh.wikipedia.org/wiki/有限状态自动机)接受的语言类。但是在简洁性上有重要区别。某类正则语言只能用大小指数增长的自动机来描述，而要求的正则表达式的长度只线性的增长。 正则表达式对应于[乔姆斯基层级](https://zh.wikipedia.org/wiki/乔姆斯基层级)的[类型-3](https://zh.wikipedia.org/wiki/正则文法)[文法](https://zh.wikipedia.org/wiki/形式文法)。但通常编程语言或其相关库（例如[PCRE](https://zh.wikipedia.org/wiki/正则表达式#PCRE表达式全集)）中实现的正则表达式的表达能力是[乔姆斯基层级](https://zh.wikipedia.org/wiki/乔姆斯基层级)中[类型-3](https://zh.wikipedia.org/wiki/正则文法)[文法](https://zh.wikipedia.org/wiki/形式文法)的超集。在另一方面，在正则表达式和不导致这种大小上的爆炸的[非确定有限状态自动机](https://zh.wikipedia.org/wiki/非确定有限状态自动机)（NFA）之间有简单的映射；为此NFA经常被用作正则表达式的替表示式。 我们还要在这种形式化中研究表达力。如下面例子所展示的，不同的正则表达式可以表达同样的语言：这种形式化中存在着冗余。 有可能对两个给定正则表达式写一个[算法](https://zh.wikipedia.org/wiki/算法)来判定它们所描述的语言是否本质上相等，简约每个表达式到极小确定有限自动机，确定它们是否[同构](https://zh.wikipedia.org/wiki/同构)（等价）。 这种冗余可以消减到什么程度？我们可以找到仍有完全表达力的正则表达式的有趣的子集吗？Kleene星号和并集明显是需要的，但是我们或许可以限制它们的使用。这提出了一个令人惊奇的困难问题。因为正则表达式如此简单，没有办法在语法上把它重写成某种规范形式。过去公理化的缺乏导致了[星号高度问题](https://zh.wikipedia.org/w/index.php?title=星号高度问题&action=edit&redlink=1)。最近Dexter Kozen用[克莱尼代数](https://zh.wikipedia.org/wiki/克莱尼代数)公理化了正则表达式。 很多现实世界的“正则表达式”引擎实现了不能用正则表达式代数表达的特征。 > 以上引用自维基百科条目[正则表达式：理论](https://zh.wikipedia.org/wiki/正则表达式#理论) ~~(其实我也看不懂)~~ ------ #### 基本语法 一个正则表达式通常被称为一个**模式**（pattern），为用来描述或者匹配一系列匹配某个[句法](https://zh.wikipedia.org/wiki/句法)规则的[字符串](https://zh.wikipedia.org/wiki/字符串)。例如：Handel、Händel和Haendel这三个字符串，都可以由`H(a|ä|ae)ndel`这个模式来描述。大部分正则表达式的形式都有如下的结构： ##### 选择 - 竖线`|`代表选择（即[或集](https://zh.wikipedia.org/wiki/逻辑或)），具有最低优先级。例如`gray|grey`可以匹配grey或gray。 ##### 数量限定 某个字符后的数量限定符用来限定前面这个字符允许出现的个数。最常见的数量限定符包括`+`、`?`和`*`（不加数量限定则代表出现一次且仅出现一次）： - 加号`+`代表前面的字符必须至少出现一次。（1次或多次）。例如，`goo+gle`可以匹配google、gooogle、goooogle等; - 问号`?`代表前面的字符最多只可以出现一次。（0次或1次）。例如，`colou?r`可以匹配color或者colour; - 星号`*`代表前面的字符可以不出现，也可以出现一次或者多次。（0次、1次或多次）。例如，`0*42`可以匹配42、042、0042、00042等。 ##### 匹配 - 圆括号`()`可以用来定义操作符的范围和优先度。例如，`gr(a|e)y`等价于`gray|grey`，`(grand)?father`匹配father和grandfather。 上述这些构造子都可以自由组合，因此`H(ae?|ä)ndel`和`H(a|ae|ä)ndel`是相同的。 精确的语法可能因不同的工具或程序而异。 ------ #### PCRE表达式 正则表达式有多种不同的风格，下表是在`PCRE`中元字符及其在正则表达式上下文中的行为的一个完整列表: | 字符 | 描述 | | :------------: | :----------------------------------------------------------: | | `\` | 将下一个字符标记为一个特殊字符、或一个原义字符（有"`^＄()*+?.[\{|`"共计12个)、或一个向后引用、或一个八进制转义符。例如，"`n`"匹配字符"`n`"。"`\n`"匹配一个换行符。序列"`\\`"匹配"`\`"而"`\(`"则匹配"`(`"。(即转义的作用) | | `^` | 匹配输入字符串的**开始位置**。如果设置了正则表达式的`多行属性(Multiline)`，`^`也匹配"`\n`"或"`\r`"之后的位置。 | | `＄` | 匹配输入字符串的**结束位置**。如果设置了正则表达式的`多行属性(Multiline)`，`＄`也匹配"`\n`"或"`\r`"之前的位置。 | | `*` | 匹配前面的子表达式**零次或多次**。例如，`zo*`能匹配"`z`"、"`zo`"以及"`zoo`"(任意个`o`，包括零次)。`*`等价于`{0,}`。 | | `+` | 匹配前面的子表达式**一次或多次**。例如，"`zo+`"能匹配"`zo`"以及"`zoo`"，但不能匹配"`z`"(任意个`o`，不包括零次)。+等价于`{1,}`。 | | `?` | 匹配前面的子表达式**零次或一次**。例如，"`do(es)?`"可以匹配"`do`"或"`does`"。`?`等价于`{0,1}`。 | | `{n}` | *n*是一个非负整数。**匹配确定的*n*次**。例如，"`o{2}`"不能匹配"`Bob`"中的"`o`"，但是能匹配"`food`"中的两个`o`(即*n*个`o`可以被匹配)。 | | `{n,}` | *n*是一个非负整数。**至少匹配*n*次**。例如，"`o{2,}`"不能匹配"`Bob`"中的"`o`"，但能匹配"`foooood`"中的所有o。"`o{1,}`"等价于"`o+`"。"`o{0,}`"则等价于"`o*`"。 | | `{n,m}` | *m*和*n*均为非负整数，其中*n*<=*m*。**最少匹配*n*次且最多匹配*m*次**。例如，"`o{1,3}`"将匹配"`fooooood`"中的前三个`o`(默认为贪心量化，即尽可能多的匹配)。"`o{0,1}`"等价于"`o?`"。**请注意在逗号和两个数之间不能有空格**。 | | `?` | **非贪心量化**：当该字符紧跟在任何一个其他重复修饰符`（*,+,?`，`{n}`，`{n,}`，`{n,m}`）后面时，匹配模式是**非贪婪**的。非贪婪模式尽**可能少的匹配**所搜索的字符串，而**默认的贪婪模式则尽可能多的匹配**所搜索的字符串。例如，对于字符串"`oooo`"，"`o+?`"将匹配单个"`o`"，而"`o+`"将匹配所有"`o`"。 | | `.` | 匹配**除"`\r`""`\n`"之外的任何单个字符**。要匹配包括"`\r`""`\n`"在内的任何字符，请使用像"`(.|\r|\n)`"的模式。 | | `(pattern)` | **匹配pattern并获取这一匹配的子字符串**。该子字符串用于向后引用。所获取的匹配可以从产生的Matches集合得到。**要匹配圆括号字符，请使用"`\(`"或"`\)`"**。可带数量后缀(即`{n,m}`)。 | | `(?:pattern)` | 匹配pattern但**不获取**匹配的子字符串，也就是说**这是一个非获取匹配**，不存储匹配的子字符串**用于向后引用**。这在使用或字符"`(|)`"来组合一个模式的各个部分是很有用。例如"`industr(?:y|ies)`"就是一个比"`industry|industries`"更简略的表达式。 | | `(?=pattern)` | **正向肯定预查**，在任何匹配pattern的字符串开始处匹配查找字符串。这是一个**非获取匹配**，也就是说，该匹配不需要获取供以后使用。例如，"`Windows(?=95|98|NT|2000)`"能匹配"`Windows2000`"中的"`Windows`"，但不能匹配"`Windows3.1`"中的"`Windows`"。预查不消耗字符，也就是说，在一个匹配发生后，在最后一次匹配之后立即开始下一次匹配的搜索，而不是从包含预查的字符之后开始。 | | `(?!pattern)` | **正向否定预查**，在任何**不匹配**pattern的字符串开始处匹配查找字符串。这是一个**非获取匹配**，也就是说，该匹配不需要获取供以后使用。例如"`Windows(?!95|98|NT|2000)`"能匹配"`Windows3.1`"中的"`Windows`"，但不能匹配"`Windows2000`"中的"`Windows`"。预查不消耗字符，也就是说，在一个匹配发生后，在最后一次匹配之后立即开始下一次匹配的搜索，而不是从包含预查的字符之后开始 | | `(?<=pattern)` | **反向肯定预查**，与正向肯定预查类似，**只是方向相反**。例如，"`(?<=95|98|NT|2000)Windows`"能匹配"`2000Windows`"中的"`Windows`"，但不能匹配"`3.1Windows`"中的"`Windows`"。 | | `(?<!pattern)` | **反向否定预查**，与正向否定预查类似，**只是方向相反**。例如"`(?<!95|98|NT|2000)Windows`"能匹配"`3.1Windows`"中的"`Windows`"，但不能匹配"`2000Windows`"中的"`Windows`"。 | | `x|y` | 没有包围在()里，其范围是整个正则表达式。例如，**"`z|food`"能匹配"`z`"或"`food`"**。"`(?:z|f)ood`"则匹配"`zood`"或"`food`"。**(其实相当于或运算)** | | `[xyz]` | **字符集合**。**匹配所包含的任意一个字符**。例如，"`[abc]`"可以匹配"`plain`"中的"`a`"。特殊字符**仅有反斜线\保持特殊含义，用于转义字符**。其它特殊字符如**星号、加号、各种括号等均作为普通字符**。**脱字符^如果出现在首位则表示负值字符集合**；**如果出现在字符串中间就仅作为普通字符**。**连字符 - 如果出现在字符串中间表示字符范围描述**；**如果如果出现在首位（或末尾）则仅作为普通字符**。**右方括号应转义出现，也可以作为首位字符出现**。 | | `[^xyz]` | **排除型字符集合**。**匹配未列出的任意字符**。例如，"`[^abc]`"可以匹配"`plain`"中的"`plain`"。 | | `[a-z]` | **字符范围**。**匹配指定范围内的任意字符**。例如，"`[a-z]`"可以匹配"`a`"到"`z`"范围内的任意小写字母字符。 | | `[^a-z]` | **排除型的字符范围**。**匹配任何不在指定范围内的任意字符**。例如，"`[^a-z]`"可以匹配任何不在"`a`"到"`z`"范围内的任意字符。 | | `[:name:]` | 增加**命名字符类**中的字符到表达式。**只能用于方括号表达式**。 | | `[=elt=]` | **增加当前locale下排序**等价于字符"_**elt**_"的元素。例如，[=a=]可能会增加ä、á、à、ă、ắ、ằ、ẵ、ẳ、â、ấ、ầ、ẫ、ẩ、ǎ、å、ǻ、ä、ǟ、ã、ȧ、ǡ、ą、ā、ả、ȁ、ȃ、ạ、ặ、ậ、ḁ、ⱥ、ᶏ、ɐ、ɑ 。**只能用于方括号表达式**。 | | `[.elt.]` | **增加排序元素_elt_到表达式中**。这是因为某些排序元素由多个字符组成。例如，29个字母表的西班牙语， "CH"作为单个字母排在字母C之后，因此会产生如此排序"cinco, credo, chispa"。**只能用于方括号表达式**。 | | `\b` | 匹配一个**单词边界**，也就是指**单词和空格间的位置**。例如，"`er\b`"可以匹配"`never`"中的"`er`"，但不能匹配"`verb`"中的"`er`"。 | | `\B` | 匹配**非单词边界**。"`er\B`"能匹配"`verb`"中的"`er`"，但不能匹配"`never`"中的"`er`"。 | | `\cx` | 匹配由*x*指明的**控制字符**。x的值**必须为`A-Z`或`a-z`之一**。否则，将c视为一个原义的"`c`"字符。控制字符的值等于x的值最低5比特（即对3210进制的余数）。例如，\cM匹配一个Control-M或回车符。\ca等效于\u0001, \cb等效于\u0002, 等等... | | `\d` | 匹配一个**数字字符**。等价于[0-9]。注意Unicode正则表达式会匹配全角数字字符。 | | `\D` | 匹配一个**非数字字符**。等价于`[^0-9]`。 | | `\f` | 匹配一个**换页符**。等价于\x0c和\cL。 | | `\n` | 匹配一个**换行符**。等价于\x0a和\cJ。 | | `\r` | 匹配一个**回车符**。等价于\x0d和\cM。 | | `\s` | 匹配任何**空白字符**，包括*空格、制表符、换页符*等等。等价于[ \f\n\r\t\v]。注意Unicode正则表达式会匹配全角空格符。 | | `\S` | 匹配任何**非空白字符**。等价于`[^ \f\n\r\t\v]`。 | | `\t` | 匹配一个**制表符**。等价于\x09和\cI。 | | `\v` | 匹配一个**垂直制表符**。等价于\x0b和\cK。 | | `\w` | 匹配**包括下划线**的任何**单词字符**(即*字母、数字、下划线*)。等价于"`[A-Za-z0-9_]`"。注意Unicode正则表达式会匹配中文字符。 | | `\W` | 匹配任何**非单词字符**。等价于"`[^A-Za-z0-9_]`"。 | | `\xnn` | **十六进制转义字符序列**。匹配两个十六进制数字*nn*表示的字符。例如，"`\x41`"匹配"`A`"。"`\x041`"则等价于"`\x04&1`"。正则表达式中可以使用ASCII编码。. | | `\num` | **向后引用**一个子字符串，该子字符串与正则表达式的第*num*个用括号围起来的捕捉群子表达式匹配。其中*num*是从1开始的十进制正整数，其上限可能是9、31、99甚至无限。例如："`(.)\1`"匹配两个连续的相同字符。 | | `\n` | 标识一个**八进制转义值**或一个**向后引用**。如果*`\n`*之前至少*n*个获取的子表达式，则*n*为向后引用。否则，如果*n*为八进制数字（0-7），则*n*为一个八进制转义值。 | | `\nm` | **3位八进制数字**，标识一个**八进制转义值**或一个**向后引用**。如果*`\nm`*之前至少有*nm*个获得子表达式，则*nm*为向后引用。如果*`\nm`*之前至少有*n*个获取，则*n*为一个后跟文字*m*的向后引用。如果前面的条件都不满足，若*n*和*m*均为八进制数字（0-7），则*`\nm`*将匹配八进制转义值*nm*。 | | `\nml` | 如果*n*为八进制数字（0-3），且*m和l*均为八进制数字（0-7），则匹配八进制转义值*nm*l。 | | `\un` | Unicode转义字符序列。其中*n*是一个用四个十六进制数字表示的Unicode字符。例如，\u00A9匹配著作权符号（©）。 | > 以上部分引用自维基百科条目[正则表达式：PCRE表达式](https://zh.wikipedia.org/wiki/正则表达式#PCRE表达式全集) ------ #### Unicode处理 在正则表达式中，可以用`\uXXXX`表示一个Unicode字符，其中`XXXX`为四位16进制数字。 Unicode字符的三种性质： - Unicode Property：字符属于标点、空格、字母等等。每个Unicode字符只能属于唯一Unicode Property。.NET、Java、PHP和Ruby等语言支持。具体分类为： - 字符`\p{L}` - `\p{Ll}`或`\p{Lowercase_Letter}`：小写字符（必须有大写的形式）。 - `\p{Lu}`或`\p{Uppercase_Letter}`：大写字符（必须有小写的形式）。 - `\p{Lt}`或`\p{Titlecase_Letter}`：全词首字母大写的字符。 - `\p{L&}`或`\p{Cased_Letter}`：存在大小写形式的字符（Ll, Lu, Lt的组合）。 - `\p{Lm}`或`\p{Modifier_Letter}`：音标修饰字符。 - `\p{Lo}`或`\p{Other_Letter}`：不具有大小写的字符或字形。 - 附加符号`\p{M}` - `\p{Mn}`或`\p{Non_Spacing_Mark}`：与其他字符结合，不额外占用空间的字符，例如[日耳曼语元音变音](https://zh.wikipedia.org/wiki/日耳曼語元音變音)。 - `\p{Mc}`或`\p{Spacing_Combining_Mark}`：与其他字符结合，额外占用空间的字符，例如[马拉雅拉姆文：元音字母及附标](https://zh.wikipedia.org/wiki/馬拉雅拉姆文#元音字母及附标)。 - `\p{Me}`或`\p{Enclosing_Mark}`：包含其他字符的字符，例如圆圈、方块。 - 分隔符`p{Z}` - `\p{Zs}`或`\p{Space_Separator}`：a whitespace character that is invisible, but does take up space。 - `\p{Zl}`或`\p{Line_Separator}`：line separator character U+2028。 - `\p{Zp}`或`\p{Paragraph_Separator}`：paragraph separator character U+2029。 - 符号`\p{S}` - `\p{Sm}`或`\p{Math_Symbol}`：数学符号。 - `\p{Sc}`或`\p{Currency_Symbol}`：通货符号。 - `\p{Sk}`或`\p{Modifier_Symbol}`：组合为其他字符的符号。 - `\p{So}`或`\p{Other_Symbol}`：其他符号。 - 数值字符`\p{N}` - `\p{Nd}`或`\p{Decimal_Digit_Number}`：所有文本中的数字0至9字符，不含[形意符号](https://zh.wikipedia.org/wiki/形意符号)。 - `\p{Nl}`或`\p{Letter_Number}`：看起来像字母的符号，包含[罗马数字](https://zh.wikipedia.org/wiki/罗马数字)。 - `\p{No}`或`\p{Other_Number}`：上角标或下角标数字，或者其他不属于0至9的数字。不含[形意符号](https://zh.wikipedia.org/wiki/形意符号)。 - 标点符号`\p{P}` - `\p{Pd}`或`\p{Dash_Punctuation}`：任何种类的[连字号](https://zh.wikipedia.org/wiki/连字号)或[连接号](https://zh.wikipedia.org/wiki/连接号)。 - `\p{Ps}`或`\p{Open_Punctuation}`：任何种类开[括号](https://zh.wikipedia.org/wiki/括号)。 - `\p{Pe}`或`\p{Close_Punctuation}`：任何种类闭括号。 - `\p{Pi}`或`\p{Initial_Punctuation}`：任何种类开[引号](https://zh.wikipedia.org/wiki/引号)。 - `\p{Pf}`或`\p{Final_Punctuation}`：任何种类闭引号。 - `\p{Pc}`或`\p{Connector_Punctuation}`：连接词的标点符号，如下划线。 - `\p{Po}`或`\p{Other_Punctuation}`：其他标点符号。 - 其它符号`\p{C}` （包括不可见控制字符与未用码位） - `\p{Cc}`或`\p{Control}`：[ASCII](https://zh.wikipedia.org/wiki/ASCII)或[Latin-1](https://zh.wikipedia.org/wiki/Latin-1)[控制字符](https://zh.wikipedia.org/wiki/控制字符)`0x00-0x1F`与`0x7F-0x9F`。 - `\p{Cf}`或`\p{Format}`：不可见的格式化指示字符。 - `\p{Co}`或`\p{Private_Use}`：私用[码位](https://zh.wikipedia.org/wiki/码位)。 - `\p{Cs}`或`\p{Surrogate}`：[UTF-16](https://zh.wikipedia.org/wiki/UTF-16)编码的代理对的一半。 - `\p{Cn}`或`\p{Unassigned}`：未被使用的[码位](https://zh.wikipedia.org/wiki/码位)。 - Unicode Block：按照编码区间划分Unicode字符，每个Unicode Block中的字符编码属于一个编码区间。例如Java语言`\p{ InCJK_Compatibility_Ideographs }`，.NET语言`\p{IsCJK_Compatibility_Ideographs}`。 - Unicode Script：按照字符所属的书写系统来划分Unicode字符。PHP和Ruby（版本不低于1.9）支持Unicode Script。例如`\p{Han}`表示汉字（中文字符）。 这三种Unicode性质对应的字符组补集是将开头的`\p`改为`\P`，其它不变。 > 以上引用自维基百科条目[正则表达式：Unicode处理](https://zh.wikipedia.org/wiki/正则表达式#Unicode处理) ------ #### POSIX字符组 | 字符组 | 说明 | ASCII环境 | Unicode环境 | | :----------: | :-----------------------------: | :----------------------------: | :-----------------------: | | `[:alnum:]` | 字母字符和数字字符 | `[a-zA-Z0-9]` | `[\p{L&}\p{Nd}]` | | `[:alpha:]` | 字母 | `[a-zA-Z]` | `\p{L&}` | | `[:ascii:]` | ASCII字符 | `[\x00-\x7F]` | `\p{InBasicLatin}` | | `[:blank:]` | 空格字符和制表符 | `[ \t]` | `[\p{Zs}\t]` | | `[:cntrl:]` | 控制字符 | `[\x00-\x1F\x7F]` | `\p{Cc}` | | `[:digit:]` | 数字字符 | `[0-9]` | `\p{Nd}` | | `[:graph:]` | 空白字符之外的字符 | `[\x21-\x7E]` | `[^\p{Z}\p{C}]` | | `[:lower:]` | 小写字母字符 | `[a-z]` | `\p{Ll}` | | `[:print:]` | 类似`[:graph:]`，但包括空白字符 | `[\x20-\x7E]` | `\P{C}` | | `[:punct:]` | 标点符号 | `[][!"#＄%&'()*+,./:;<=>?@\^_`{ | }~-]` | `[\p{P}\p{S}]` | | `[:space:]` | 空白字符 | `[ \t\r\n\v\f]` | `[\p{Z}\t\r\n\v\f]` | | `[:upper:]` | 大写字母字符 | `[A-Z]` | `\p{Lu}` | | `[:word:]` | 字母字符 | `[A-Za-z0-9_]` | `[\p{L}\p{N}\p{Pc}]` | | `[:xdigit:]` | 十六进制字符 | `[A-Fa-f0-9]` | `[A-Fa-f0-9]` | > 以上引用自维基百科条目[正则表达式：POSIX字符组](https://zh.wikipedia.org/wiki/正则表达式#POSIX字符组) ------ #### 优先级 | 优先级 | 符号 | | :----: | :-----------------------------------: | | 最高 | `\` | | 高 | `()`、`(?:)`、`(?=)`、`[]` | | 中 | `*`、`+`、`?`、`{n}`、`{n,}`、`{n,m}` | | 低 | `^`、`＄`、中介字符 | | 次最低 | 串接，即相邻字符连接在一起 | | 最低 | `|` | > 以上引用自维基百科条目[正则表达式：优先权](https://zh.wikipedia.org/wiki/正则表达式#优先权) ------ #### 常用正则 | 字符 | 描述 | | :---------: | :----------------------------------------------------------: | | `\` | 将下一个字符标记为一个特殊字符、或一个原义字符（有"`^＄()*+?.[\{|`"共计12个)、或一个向后引用、或一个八进制转义符。例如，"`n`"匹配字符"`n`"。"`\n`"匹配一个换行符。序列"`\\`"匹配"`\`"而"`\(`"则匹配"`(`"(即转义的作用)。若要查看完整转移字符表，请移步：[PCRE表达式](#PCRE表达式) | | `^` | 匹配输入字符串的**开始位置**。如果设置了正则表达式的`多行属性(Multiline)`，`^`也匹配"`\n`"或"`\r`"之后的位置。 | | `＄` | 匹配输入字符串的**结束位置**。如果设置了正则表达式的`多行属性(Multiline)`，`＄`也匹配"`\n`"或"`\r`"之前的位置。 | | `*` | 匹配前面的子表达式**零次或多次**。例如，`zo*`能匹配"`z`"、"`zo`"以及"`zoo`"(任意个`o`，包括零次)。`*`等价于`{0,}`。 | | `+` | 匹配前面的子表达式**一次或多次**。例如，"`zo+`"能匹配"`zo`"以及"`zoo`"，但不能匹配"`z`"(任意个`o`，不包括零次)。+等价于`{1,}`。 | | `?` | 匹配前面的子表达式**零次或一次**。例如，"`do(es)?`"可以匹配"`do`"或"`does`"。`?`等价于`{0,1}`。 | | `{n,m}` | *m*和*n*均为非负整数，其中*n*<=*m*。**最少匹配n次且最多匹配m次**。其中，`{n}`表示匹配一个字符*n*次，`{n,}`表示匹配一个字符最少*n*次，例如，"`o{1,3}`"将匹配"`fooooood`"中的前三个`o`(默认为贪心量化，即尽可能多的匹配)。"`o{0,1}`"等价于"`o?`"。**请注意在逗号和两个数之间不能有空格**。 | | `?` | **非贪心量化**：当该字符紧跟在任何一个其他重复修饰符`（*,+,?`，`{n}`，`{n,}`，`{n,m}`）后面时，匹配模式是**非贪婪**的。非贪婪模式尽**可能少的匹配**所搜索的字符串，而**默认的贪婪模式则尽可能多的匹配**所搜索的字符串。例如，对于字符串"`oooo`"，"`o+?`"将匹配单个"`o`"，而"`o+`"将匹配所有"`o`"。 | | `.` | 匹配**除"\r""\n"之外的任何单个字符**。要匹配包括"`\r`""`\n`"在内的任何字符，请使用像"`(.|\r|\n)`"的模式。 | | `(pattern)` | **匹配pattern并获取这一匹配的子字符串**。该子字符串用于向后引用。所获取的匹配可以从产生的Matches集合得到。**要匹配圆括号字符，请使用"\("或"\)"**。可带数量后缀(即`{n,m}`)。 | | `x|y` | 没有包围在()里，其范围是整个正则表达式。例如，**"z\|food"能匹配"z"或"food"**。"`(?:z|f)ood`"则匹配"`zood`"或"`food`"。**(其实相当于或运算)** | | `[xyz]` | **字符集合**。**匹配所包含的任意一个字符**。例如，"`[abc]`"可以匹配"`plain`"中的"`a`"。特殊字符**仅有反斜线\保持特殊含义，用于转义字符**。其它特殊字符如**星号、加号、各种括号等均作为普通字符**。**脱字符^如果出现在首位则表示负值字符集合**；**如果出现在字符串中间就仅作为普通字符**。**连字符 - 如果出现在字符串中间表示字符范围描述**；**如果如果出现在首位（或末尾）则仅作为普通字符**。**右方括号应转义出现，也可以作为首位字符出现**。 | | `[^xyz]` | **排除型字符集合**。**匹配未列出的任意字符**。例如，"`[^abc]`"可以匹配"`plain`"中的"`plain`"。 | | `[a-z]` | **字符范围**。**匹配指定范围内的任意字符**。例如，"`[a-z]`"可以匹配"`a`"到"`z`"范围内的任意小写字母字符。 | | `[^a-z]` | **排除型的字符范围**。**匹配任何不在指定范围内的任意字符**。例如，"`[^a-z]`"可以匹配任何不在"`a`"到"`z`"范围内的任意字符。 | | `[:name:]` | 增加**命名字符类**(即POSIX字符组)中的字符到表达式。**只能用于方括号表达式**。若要查看完整命名字符类，请移步：[POSIX字符组](#POSIX字符组) | ------ #### 示例 1. 若要匹配一个中国大陆的11位手机号，可使用正则表达式"`^\d{11}$`"或"`^[0-9]{11}$`"进行匹配(即检查字符串适配是由11个数字组成)； 2. 若要匹配一个中国大陆的身份证号，可使用正则表达式"`^\d{17}(\d|X)$`"或"`^[0-9]{17}[0-9X]`"进行匹配(即检查字符串是否由17位数字本体和1位校验码组成)。 ------ ### 3. C++中正则表达式的使用方法： C++在`C++11`的标准中加入了`regex`正则表达式库，大大方便了我们使用正则表达式 下面我就讲解一下如何使用`regex`库 > 使用C++的regex库可以参照：[正则表达式库](https://zh.cppreference.com/w/cpp/regex) ------ #### 1. 检查身份证号： $$\underbrace\text{431723~19950328~453}_\text{17位数字本体}~\underbrace{\text{6}}_\text{1位校验码(数字或X)}$$ $$\bold{\text{身份证号的组成}}$$ $$\color{gray}\text{(不要以为这就是我的身份证号，那是不可能的)}$$ ```cpp #include <iostream> #include <iterator> #include <regex> //使用regex库 #include <string> using namespace std; int w[] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2}; int main() { string ID_card; //用于存储身份证号 cout << "请输入身份证号："; cin >> ID_card; //输入身份证号 regex check_regex("^[0-9]{17}[0-9X]$"); //定义检查用的正则表达式 if (regex_search(ID_card, check_regex)) { //判断是否有匹配 cout << "身份证号检查通过！" << endl; //有则正确 else cout << "身份证号错误！" << endl; //无则错误 return 0; } ``` **温馨提示：请使用支持`C++11`及以上版本的C++进行编译，否则会编译错误** (这里只是检查了身份证号是否是正确的格式，并没有检验校验码，若想知道如何检验校验码，请参照我的另一篇博客：[计算身份证号校验码](https://www.luogu.org/blog/0AND1STORY/calc-idcard-check-number)) 是不是很简单呢？这还只是正则表达式的简单应用，并不能很好地体现正则表达式的优势 除此之外还有一些比较常见的应用如检索和替换等 ------ #### 2. 检索HTML文件里的所有网页链接： $$\text{属性:}\left\{\begin{array}{c}href\\src\end{array}\right\}+\text{任意数量的空白字符}+=+\text{任意数量的空白字符}+\text{"链接"}$$ ```cpp #include <iostream> #include <fstream> #include <iterator> #include <regex> #include <string> using namespace std; int main() { ios::sync_with_stdio(false); //优化无处不在 ifstream fin("HTMLFile.html"); //读入HTML文件 string text = ""; while (!fin.eof()) { string tmp; getline(fin, tmp); //逐行读入 text += tmp + '\n'; } string pattern = "(?:href|src)\\s*=\\s*\"([0-9A-Za-z/\\.]*)\""; //定义要匹配的模式串 regex word_regex(pattern, regex_constants::icase); //定义正则表达式 //这里的icase是指获得所有的子匹配串(每一个用圆括号()括起来的都是一个子匹配串) //像这里就有一个子匹配串：([0-9A-Za-z/\.])，而(?:XXX)则不算作子匹配串 auto words_begin = sregex_token_iterator(text.begin(), text.end(), word_regex, 1); //这里的1表示获取第一个子匹配串的迭代器 auto words_end = sregex_token_iterator(); cout << "找到 " << distance(words_begin, words_end) << " 个链接: " << endl; //输出匹配串的个数 for (auto i = words_begin; i != words_end; ++i) { cout << i->str() << endl; //循环输出每一个匹配串 } return 0; } ``` 这个程序就实现了读入一个HTML文件并且检索所有的网页链接的功能 这就是正则表达式更高级一点的应用了，相对于传统的比较方式，使用正则表达式的代码相较写状态自动机更短了，时间复杂度相较写朴素算法更小了，所以这才是正则表达式的真正优势所在~~(虽然OI能不能用不清楚)~~ ------ #### 3. 简易Markdown转HTML： ```cpp #include <iostream> #include <fstream> #include <iterator> #include <regex> #include <string> using namespace std; int main() { ios::sync_with_stdio(false); //依然是无处不在的优化 ifstream fin("MDFile.md"); //读入Markdown文件 string text = "\n"; while (!fin.eof()) { string tmp; getline(fin, tmp); //逐行读入 text += tmp + '\n'; } //实现6个级别的标题 //其中替换字符串中的`$n`代表第n个子匹配串的引用，`$&`表示整个匹配串的引用 text = regex_replace(text, regex("\\n#{6}\\s+(.+)"), "\n<h6>$1</h6>"); text = regex_replace(text, regex("\\n#{5}\\s+(.+)"), "\n<h5>$1</h5>"); text = regex_replace(text, regex("\\n#{4}\\s+(.+)"), "\n<h4>$1</h4>"); text = regex_replace(text, regex("\\n#{3}\\s+(.+)"), "\n<h3>$1</h3>"); text = regex_replace(text, regex("\\n#{2}\\s+(.+)"), "\n<h2>$1</h2>"); text = regex_replace(text, regex("\\n#{1}\\s+(.+)"), "\n<h1>$1</h1>"); //实现粗体 text = regex_replace(text, regex("\\*\\*(.*?)\\*\\*"), "<strong>$1</strong>"); //实现两种形式的斜体 text = regex_replace(text, regex("\\*(.*?)\\*"), "<em>$1</em>"); text = regex_replace(text, regex("_(.*?)_"), "<em>$1</em>"); //实现删除线，其中delete是已经定义好的class text = regex_replace(text, regex("~~(.*?)~~"), "<span class=\"delete\">$1</span>"); //实现代码块 text = regex_replace(text, regex("```(.*)\\s+((.|\\s)*?)```"), "<pre><code class=\"%1\">\n$2</code></pre>"); //实现分割线 text = regex_replace(text, regex("\\n-{3,}"), "\n<hr>"); cout << text << endl; //输出结果 return 0; } ``` 这个程序就很好的演示了`regex`库的替换功能 其实很多将Markdown转成HTML文件的工具所使用的方法就是正则表达式，这里因为只是一个演示，并没有做得太复杂，只实现了**标题、粗体、斜体、删除线、代码块、分割线**的功能，但是能够很好的体现出正则表达式在替换功能上的巨大优势 ------ #### 4. 正则表达式在OI上的应用：~~(虽然应该不能用)~~ 我们知道**AC自动机**是一个非常厉害的字符串算法，对于我这种**蒟蒻**来说，打一个AC自动机是极其不愿意的，总想通过一些神奇的STL容器来减少代码量，**那么有没有这样的库呢？** $$ \Huge{\text{「有的！}{\color{#ff3333}\mathbb{~REGEX~}}\text{就是其中之一！」}} $$ 资料上显示，正则表达式引擎采用的是**有限状态自动机**，而AC自动机则属于**确定有限状态自动机**，是有限状态自动机的一种，**那么，我们是不是可以用正则表达式来做AC自动机的题呢？** 从理论上来讲，答案是**肯定**的，比如说这一道AC自动机入门题：[P2292 [HNOI2004]L语言](https://www.luogu.org/problemnew/show/P2292) [](https://www.luogu.org/problemnew/show/P2292) 题目描述非常简单，就是求字符串中有多少个可被识别的单词，我们很容易就能想到： 假设所有的单词为一个集合$W$，则可以用正则表达式"_^(W)*_"进行匹配，**答案为匹配到的字符串的长度**，因为正则表达式默认为**贪心量化**，所以可以保证匹配到的字符串长度最大。 以此为理论写出的代码如下： ```cpp #include <cstdio> #include <cctype> #include <iterator> #include <regex> #include <string> using namespace std; //由于文章长度小于1M，超过了cin的输入范围，需要手写字符串读入 class readString { private: char* buffer; size_t size; public: readString(size_t max_size = 1 << 20) { buffer = new char[max_size]; } ~readString() { delete buffer; } char* getStringBuffer() { return buffer; } char* readStringBuffer() { size = 0; char ch = getchar(); while (!isalpha(ch)) ch = getchar(); while (isalpha(ch)) buffer[size++] = ch, ch = getchar(); buffer[size] = 0; return getStringBuffer(); } void operator>>(string& str) { str = readStringBuffer(); } }; int n, m; readString readStr; //对字符串读入对象实例化 int main() { scanf("%d%d", &n, &m); string words = ""; //构造正则表达式的模式串 for (int i = 0; i < n; i ++) { string tmp; readStr >> tmp; words += (!i ? "" : "|") + tmp; //判断是否需要在前面加| } words = "^(" + words + ")*"; //按照样例构造后的模式串为：`^(is|name|what|your)*` regex word_regex(words); //生成regex对象 for (int i = 0; i < m; i ++) { string text; readStr >> text; //循环读入每篇文章 auto words_begin = sregex_iterator(text.begin(), text.end(), word_regex); //找到第一个匹配串并输出长度即可 printf("%d\n", words_begin->str().size()); } return 0; } ``` 理论上来说AC并没有太大的问题，但是因为种种原因~~(没有TLE，但是居然还有MLE)~~并没有通过，如果有**大佬**能看出来错在哪里，请在评论区留言orz ### 4. 总结 总体上来说正则表达式在计算机科学领域有非常广泛的应用，特别是在**数据分析**等行业有着非常重要的地位，学好正则表达式，就是向计算机科学领域又迈出了一步。 $$\huge\text{蒟蒻第一次投洛谷日报，}$$ $$\huge\text{文中有一部分是我的个人见解，}$$ $$\huge\text{若有什么错误，}$$ $$\huge\text{欢迎在留言中指正。}$$