正则表达式

本文章最后修改于2018年5月3日。


写在前面

写这篇文章的初衷是解决一些简单的字符串模拟题目,对于特定的某些题目,有时候用C++11的正则表达式会方便很多。

本文主要总结一下常见的一些正则表达式写法,以及如何使用C++11的regex库,最后以几个具体题目举例。

总的来说,正则表达式最简单的应用是判断一个字符串中是否包含特定字符串。正则表达式是一种文本模式,由普通字符和元字符组成。


常用的元字符

  1. “.” 匹配除“\n”之外的任何单个字符。
  2. “^” 匹配输入字符串的开始位置,不匹配任何字符,要匹配“^”字符本身,需使用“\^”;同样的,“$”匹配输入字符串的结束位置。
  3. “[xyz]”字符集,匹配其中包含的任一字符。
  4. “|” 两个匹配条件逻辑或。
  5. “\w” 匹配字母或数字或下划线;“\W”匹配任意不是字母、数字、下划线的字符。
  6. “\d” 匹配任意一个数字;“\D”匹配任意非数字字符。
  7. “\s” 匹配任意的空白符,包括空格、制表符、换页符等空白字符的其中任意一个,与“[ \f\n\r\t\v]”等效;“\S” 匹配任意不是空白符的字符。
  8. “\b” 匹配一个单词边界;“\B” 匹配非单词边界。
  9. “*” 0次或多次匹配前面的字符或子表达式,“+” 1次或多次匹配前面的字符或子表达式,“?” 0次或1次匹配前面的字符或子表达式。
  10. “{n}” 正好匹配n次,“{n,}” 至少匹配n次,“{n,m}” 匹配n到m次。

举一些例子:

“him|her”匹配“him”和“her”,也可写作“h(im|er)”

“\bthe\b”匹配“in the war”中的“the”,但不匹配“other”中的“the”


分组、捕获、反向引用

“( )” 可以将“(”和“)”之间的表达式定义为组,并且将匹配这个表达式的字符保存到一个临时区域。匹配后的各组按照左括号出现的顺序(?)分别存到$1,$2,$3…中。

比如“2018-04-25”,我们用“(\d{4})-(\d\d)-(\d\d)”去匹配,

那么2018 → $1, 04 → $2, 25 → $3。

如果想让某个括号里的内容不被捕获到,需要用到非捕获性分组

比如“h(im|er)”,就要改为“h(?:im|er)”

然后一个很重要的问题来了!如果想要匹配“看了看”、“研究研究”这样的重叠结构怎么办呢?

这时候需要用到反向引用,用\1,\2,\3…表示

上面的例子可以用“(..?)了?\1”去匹配。

语法就先总结到这里,实际还有很多,估计是用不到了。


C++11 regex

http://www.cplusplus.com/reference/regex/

最常用的两个类

regex Regex (class )

smatch match_results for string objects (class )

以及三个函数

regex_match、regex_search、regex_replace

 

要注意的一点就是在C++中“\”需要转义,即“\d”在C++中要写成“\\d”,诸如此类。

下面用具体的代码介绍这三个函数

regex_match 判断一个正则表达式是否能匹配整个字符串

regex_search 来查找第一个能匹配正则表达式的子串

regex_replace 匹配并替换

可能用到的

characters replacement
$n n-th backreference (i.e., a copy of the n-th matched group specified with parentheses in the regex pattern).
n must be an integer value designating a valid backreference, greater than 0, and of two digits at most.
$& A copy of the entire match
$` The prefix (i.e., the part of the target sequence that precedes the match).
The suffix (i.e., the part of the target sequence that follows the match).
$$ A single $ character.


题目

基本的工具基本介绍完了,可以来切一些水题了!

Two strings

from 2017 Multi-University Training Contest

题意:给两个字符串A、B,其中A只包含大小写字母,B只包含大小写字母和两个特殊符号“.”、“*”。“.”可以匹配任意字母,“*”表示前一个字符可以出现任意次。保证“*”不会在字符串开头,不会有两个连续的“*”。问A与B能否匹配。

首先,这里的“.*”和正则表达式里介绍的概念不一样。因为“*”使用的条件是前一个字符确定。即“.*”不能匹配“ab”,但是可以匹配“aa”或“bbb”这样。

这里用反向引用就好了,先将“.*”换成“(\w)\1*”即可。

AC代码只有这么短

 

Abbreviation

from 2016-2017 ACM-ICPC Northeastern European Regional Contest (NEERC 16)

题意:大概是给一段包含大小写字母和逗号句号的文本,要求缩写连续的大写字母开头的单词。当时这个模拟写的十分难受想死,结果题解上写了一句有队伍用正则表达式很快就A了这个题目。

样例输入:

样例输出:

AC代码(当时赛后补的,写的有点挫,等完改):

赛中写的代码,直接跳过即可:

命名规范问题

from 第十六届北京师范大学程序设计竞赛现场决赛

题意:给一些变量名,将符合(题中描述的) 驼峰命名法规范的变
量名转换为下划线命名法。不符合的原样输出。

好吧,这个题其实是我出的,标程用正则表达式,20行左右搞定。

应该并不毒瘤吧,看大家模拟的挺开心的

代码:

 

参考资料: