正则表达式详解

0. 序言

正则表达式是现在很火的一个计算机科学概念，在字符串处理上有很广泛的应用。

现在很多语言都加入了正则表达式的内容，像Python、PHP、JavaScript都支持正则表达式。

当然，C++也不例外，在C++11(-0x1x)的标准中就加入了对正则表达式的支持，

在C++17(-0x1z)中更是加入了对多行正则(multiline)的支持。

下面我就主要使用C++对正则表达式进行一个简单的讲解。

1. 什么是正则表达式？

正则表达式（英语：Regular Expression，在代码中常简写为regex、regexp或RE(emmm...OIer都知道这意味着什么)），又称正规表示式、正规表示法、正规表达式、规则表达式、常规表示法，是计算机科学的一个概念。正则表达式使用单个字符串来描述、匹配一系列匹配某个句法规则的字符串。在很多文本编辑器里，正则表达式通常被用来检索、替换那些匹配某个模式的文本。

以上部分引用自维基百科条目: 正则表达式

通俗来说：正则表达式就是用来在一个字符串中查找符合条件的子串，并且对字串进行如替换等操作的

2. 正则表达式语法：

理论

温馨提示：此部分较反人类，看不懂属正常现象

看不懂请移步：基本语法

正则表达式可以用形式化语言理论的方式来表达。正则表达式由常量和算子组成，它们分别表示字符串的集合和在这些集合上的运算。给定有限字母表Σ定义了下列常量：

• 空集$\varnothing$表示集合$\varnothing$。
• 空串$\varepsilon$表示集合$\{\varepsilon\}$。
• 文字字符在$\Sigma$中的$a$表示集合$\{a\}$。

定义了下列运算：

• 串接$RS$表示集合$\{\alpha \beta \mid \alpha \in R,\beta \in S\}$。例如：$\{ab,c\}\{d,ef\}=\{abd,abef,cd,cef\}$。
• 选择$R|S$表示$R$和$S$的并集。例如：$\{ab,c\}|\{ab,d,ef\}=\{ab,c,d,ef\}$。
• Kleene星号$R^*$表示包含$\varepsilon$并且闭合在字符串串接下的$R$的最小子集。这是可以通过$R$中的零或多个字符串的串接得到所有字符串的集合。例如：$\{ab,c\}^{*}=\{\varepsilon ,ab,c,abab,abc,cab,cc,ababab,\cdots \}$。

上述常量和算子形成了克莱尼代数。

很多课本使用对选择使用符号$\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$中的所有字符串的集合。补算子是多余的，因为它可以使用其他算子来表达（尽管计算这种表示的过程是复杂的，而结果可能以指数增大）。

这种意义上的正则表达式可以表达正则语言，精确的是可被有限状态自动机接受的语言类。但是在简洁性上有重要区别。某类正则语言只能用大小指数增长的自动机来描述，而要求的正则表达式的长度只线性的增长。

正则表达式对应于乔姆斯基层级的类型-3文法。但通常编程语言或其相关库（例如PCRE）中实现的正则表达式的表达能力是乔姆斯基层级中类型-3文法的超集。在另一方面，在正则表达式和不导致这种大小上的爆炸的非确定有限状态自动机（NFA）之间有简单的映射；为此NFA经常被用作正则表达式的替表示式。

我们还要在这种形式化中研究表达力。如下面例子所展示的，不同的正则表达式可以表达同样的语言：这种形式化中存在着冗余。

有可能对两个给定正则表达式写一个算法来判定它们所描述的语言是否本质上相等，简约每个表达式到极小确定有限自动机，确定它们是否同构（等价）。

这种冗余可以消减到什么程度？我们可以找到仍有完全表达力的正则表达式的有趣的子集吗？Kleene星号和并集明显是需要的，但是我们或许可以限制它们的使用。这提出了一个令人惊奇的困难问题。因为正则表达式如此简单，没有办法在语法上把它重写成某种规范形式。过去公理化的缺乏导致了星号高度问题。最近Dexter Kozen用克莱尼代数公理化了正则表达式。

很多现实世界的“正则表达式”引擎实现了不能用正则表达式代数表达的特征。

以上引用自维基百科条目正则表达式：理论

(其实我也看不懂)

基本语法

一个正则表达式通常被称为一个模式（pattern），为用来描述或者匹配一系列匹配某个句法规则的字符串。例如：Handel、Händel和Haendel这三个字符串，都可以由H(a|ä|ae)ndel这个模式来描述。大部分正则表达式的形式都有如下的结构：

选择

• 竖线|代表选择（即或集），具有最低优先级。例如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中元字符及其在正则表达式上下文中的行为的一个完整列表:

以上部分引用自维基百科条目正则表达式：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}：与其他字符结合，不额外占用空间的字符，例如日耳曼语元音变音。
    • \p{Mc}或\p{Spacing_Combining_Mark}：与其他字符结合，额外占用空间的字符，例如马拉雅拉姆文：元音字母及附标。
    • \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字符，不含形意符号。

  • \p{Nl}或\p{Letter_Number}：看起来像字母的符号，包含罗马数字。

  • \p{No}或\p{Other_Number}：上角标或下角标数字，或者其他不属于0至9的数字。不含形意符号。

  • 标点符号\p{P}

    • \p{Pd}或\p{Dash_Punctuation}：任何种类的连字号或连接号。

  • \p{Ps}或\p{Open_Punctuation}：任何种类开括号。

    • \p{Pe}或\p{Close_Punctuation}：任何种类闭括号。

  • \p{Pi}或\p{Initial_Punctuation}：任何种类开引号。

    • \p{Pf}或\p{Final_Punctuation}：任何种类闭引号。

  • \p{Pc}或\p{Connector_Punctuation}：连接词的标点符号，如下划线。

  • \p{Po}或\p{Other_Punctuation}：其他标点符号。

  • 其它符号\p{C}

    （包括不可见控制字符与未用码位）

    • \p{Cc}或\p{Control}：ASCII或Latin-1控制字符0x00-0x1F与0x7F-0x9F。

  • \p{Cf}或\p{Format}：不可见的格式化指示字符。

    • \p{Co}或\p{Private_Use}：私用码位。

  • \p{Cs}或\p{Surrogate}：UTF-16编码的代理对的一半。

    • \p{Cn}或\p{Unassigned}：未被使用的码位。

• 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处理

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库可以参照：正则表达式库

1. 检查身份证号：

xxxxxxxxxx
17
1
#include <iostream>
2
#include <iterator>
3
#include <regex>                                //使用regex库
4
#include <string>
5
using namespace std;
6
​
7
int main() {
8
    string ID_card;                             //用于存储身份证号
9
    cout << "请输入身份证号：";
10
    cin >> ID_card;                             //输入身份证号
11
    regex check_regex("^[0-9]{17}[0-9X]$");     //定义检查用的正则表达式
12
    if (regex_search(ID_card, check_regex))     //判断是否有匹配
13
        cout << "身份证号检查通过！" << endl;      //有则正确
14
    else
15
        cout << "身份证号错误！" << endl;          //无则错误
16
    return 0;
17
}

温馨提示：请使用支持C++11及以上版本的C++进行编译，否则会编译错误

是不是很简单呢？这还只是正则表达式的简单应用，并不能很好地体现正则表达式的优势

除此之外还有一些比较常见的应用如检索和替换等

2. 检索HTML文件里的所有网页链接：

xxxxxxxxxx
30
1
#include <iostream>
2
#include <fstream>
3
#include <iterator>
4
#include <regex>
5
#include <string>
6
using namespace std;
7
​
8
int main() {
9
    ios::sync_with_stdio(false); //优化无处不在
10
    ifstream fin("HTMLFile.html"); //读入HTML文件
11
    string text = "";
12
    while (!fin.eof()) {
13
        string tmp;
14
        getline(fin, tmp); //逐行读入
15
        text += tmp + '\n';
16
    }
17
    string pattern = "(?:href|src)\\s*=\\s*\"([0-9A-Za-z/\\.]*)\""; //定义要匹配的模式串
18
    regex word_regex(pattern, regex_constants::icase); //定义正则表达式
19
    //这里的icase是指获得所有的子匹配串(每一个用圆括号()括起来的都是一个子匹配串)
20
    //像这里就有一个子匹配串：([0-9A-Za-z/\.])，而(?:XXX)则不算作子匹配串
21
    auto words_begin = sregex_token_iterator(text.begin(), text.end(), word_regex, 1);
22
    //这里的1表示获取第一个子匹配串的迭代器
23
    auto words_end = sregex_token_iterator();
24
    cout << "找到 " << distance(words_begin, words_end) << " 个链接: " << endl;
25
    //输出匹配串的个数
26
    for (auto i = words_begin; i != words_end; ++i) {
27
        cout << i->str() << endl; //循环输出每一个匹配串
28
    }
29
    return 0;
30
}

这个程序就实现了读入一个HTML文件并且检索所有的网页链接的功能

这就是正则表达式更高级一点的应用了，相对于传统的比较方式，使用正则表达式的代码相较写状态自动机更短了，时间复杂度相较写朴素算法更小了，所以这才是正则表达式的真正优势所在(虽然OI能不能用不清楚)

3. 简易Markdown转HTML：

xxxxxxxxxx
38
1
#include <iostream>
2
#include <fstream>
3
#include <iterator>
4
#include <regex>
5
#include <string>
6
using namespace std;
7
​
8
int main() {
9
    ios::sync_with_stdio(false); //依然是无处不在的优化
10
    ifstream fin("MDFile.md"); //读入Markdown文件
11
    string text = "\n";
12
    while (!fin.eof()) {
13
        string tmp;
14
        getline(fin, tmp); //逐行读入
15
        text += tmp + '\n';
16
    }
17
    //实现6个级别的标题
18
    //其中替换字符串中的`$n`代表第n个子匹配串的引用，`$&`表示整个匹配串的引用
19
    text = regex_replace(text, regex("\\n#{6}\\s+(.+)"), "\n<h6>$1</h6>");
20
    text = regex_replace(text, regex("\\n#{5}\\s+(.+)"), "\n<h5>$1</h5>");
21
    text = regex_replace(text, regex("\\n#{4}\\s+(.+)"), "\n<h4>$1</h4>");
22
    text = regex_replace(text, regex("\\n#{3}\\s+(.+)"), "\n<h3>$1</h3>");
23
    text = regex_replace(text, regex("\\n#{2}\\s+(.+)"), "\n<h2>$1</h2>");
24
    text = regex_replace(text, regex("\\n#{1}\\s+(.+)"), "\n<h1>$1</h1>");
25
    //实现粗体
26
    text = regex_replace(text, regex("\\*\\*(.*?)\\*\\*"), "<strong>$1</strong>");
27
    //实现两种形式的斜体
28
    text = regex_replace(text, regex("\\*(.*?)\\*"), "<em>$1</em>");
29
    text = regex_replace(text, regex("_(.*?)_"), "<em>$1</em>");
30
    //实现删除线，其中delete是已经定义好的class
31
    text = regex_replace(text, regex("~~(.*?)~~"), "<span class=\"delete\">$1</span>");
32
    //实现代码块
33
    text = regex_replace(text, regex("```(.*)\\s+((.|\\s)*?)```"), "<pre><code class=\"%1\">\n$2</code></pre>");
34
    //实现分割线
35
    text = regex_replace(text, regex("\\n-{3,}"), "\n<hr>");
36
    cout << text << endl; //输出结果
37
    return 0;
38
}

这个程序就很好的演示了regex库的替换功能

其实很多将Markdown转成HTML文件的工具所使用的方法就是正则表达式，这里因为只是一个演示，并没有做得太复杂，只实现了标题、粗体、斜体、删除线、代码块、分割线的功能，但是能够很好的体现出正则表达式在替换功能上的巨大优势

4. 正则表达式在OI上的应用：(虽然应该不能用)

我们知道AC自动机是一个非常厉害的字符串算法，对于我这种蒟蒻来说，打一个AC自动机是极其不愿意的，总想通过一些神奇的STL容器来减少代码量，那么有没有这样的库呢？

资料上显示，正则表达式引擎采用的是有限状态自动机，而AC自动机则属于确定有限状态自动机，是有限状态自动机的一种，那么，我们是不是可以用正则表达式来做AC自动机的题呢？

从理论上来讲，答案是肯定的，比如说这一道AC自动机入门题：P2292 [HNOI2004]L语言

题目描述非常简单，就是求字符串中有多少个可被识别的单词，我们很容易就能想到：

假设所有的单词为一个集合$W$，则可以用正则表达式"^(W)*"进行匹配，答案为匹配到的字符串的长度，因为正则表达式默认为贪心量化，所以可以保证匹配到的字符串长度最大。

以此为理论写出的代码如下：

xxxxxxxxxx
64
1
#include <cstdio>
2
#include <cctype>
3
#include <iterator>
4
#include <regex>
5
#include <string>
6
using namespace std;
7
​
8
//由于文章长度小于1M，超过了cin的输入范围，需要手写字符串读入
9
class readString {
10
private:
11
    char* buffer;
12
    size_t size;
13
​
14
public:
15
    readString(size_t max_size = 1 << 20) {
16
        buffer = new char[max_size];
17
    }
18
​
19
    ~readString() {
20
        delete buffer;
21
    }
22
​
23
    char* getStringBuffer() {
24
        return buffer;
25
    }
26
​
27
    char* readStringBuffer() {
28
        size = 0;
29
        char ch = getchar();
30
        while (!isalpha(ch)) ch = getchar();
31
        while (isalpha(ch)) buffer[size++] = ch, ch = getchar();
32
        buffer[size] = 0;
33
        return getStringBuffer();
34
    }
35
​
36
    void operator>>(string& str) {
37
        str = readStringBuffer();
38
    }
39
};
40
​
41
int n, m;
42
readString readStr; //对字符串读入对象实例化
43
​
44
int main() {
45
    scanf("%d%d", &n, &m);
46
    string words = "";
47
    //构造正则表达式的模式串
48
    for (int i = 0; i < n; i ++) {
49
        string tmp;
50
        readStr >> tmp;
51
        words += (!i ? "" : "|") + tmp; //判断是否需要在前面加|
52
    }
53
    words = "^(" + words + ")*";
54
    //按照样例构造后的模式串为：`^(is|name|what|your)*`
55
    regex word_regex(words); //生成regex对象
56
    for (int i = 0; i < m; i ++) {
57
        string text;
58
        readStr >> text; //循环读入每篇文章
59
        auto words_begin = sregex_iterator(text.begin(), text.end(), word_regex);
60
        //找到第一个匹配串并输出长度即可
61
        printf("%d\n", words_begin->str().size());
62
    }
63
    return 0;
64
}

理论上来说AC并没有太大的问题，但是因为种种原因(没有TLE，但是居然还有MLE)并没有通过，如果有大佬能看出来错在哪里，请在评论区留言orz

4. 总结

总体上来说正则表达式在计算机科学领域有非常广泛的应用，特别是在数据分析等行业有着非常重要的地位，学好正则表达式，就是向计算机科学领域又迈出了一步。