2959. 正则表达式简化版

单点时限: 2.0 sec

内存限制: 256 MB

在程序设计中,正则表达式 (Regular Expressions) 是用来处理复杂的字符串匹配以及模式识别问题的利器。正则表达式的一种常见用法是,给定一个正则表达式和一个字符串,然后询问给定的正则表达式能否匹配整个字符串,你需要处理的就是这种询问。

当然,编写一个优秀的正则表达式引擎是有难度的,在这道题目中,你需要编程处理一种经过高度简化的正则表达式。以下是这种正则表达式简化版的定义。

简化版的正则表达式可能包含以下字符:0~9 的数字,A~Z 以及 a~z 的大小写英文字母,下划线 “_”,方括号 “[” 和 “]”,花括号 “{” 和 “}”,短横线 “-”。其中,方括号和花括号一定以成对的方式出现且不会存在任何嵌套;短横线一定出现在方括号内,且短横线两边的字符或者同为数字,或者同为小写字母,或者同为大写字母,且短横线前面的字符的 ASCII 码不大于后面的字符;花括号内只会出现数字。下面将数字、英文字母和下划线统称为 “ 普通字符 ”。

出现在括号外的普通字符即表示与字符串中同样的单个字符匹配,例如正则表达式 “dd” 可匹配字符串 “dd”,但不能匹配 “Dd”(因为大小写敏感),也不能匹配 “dd_”(正则表达式中不存在与最后的 “_” 匹配的元素)。

成对的方括号以及之间的部分也匹配字符串中的单个字符,但可以匹配的单个字符是一个集合,这个集合包含方括号中间的普通字符。例如正则表达式 “[Dd]d_engi” 既能匹配 “Dd_engi” 又能匹配 “dd_engi”;正则表达式 “[AaB][aAb]” 可匹配 “Ab”“aA”“Ba” 等,但不能匹配 “AB”“bA” 或 “bB”;正则表达式 “13[56789]” 可匹配 “135”“136”“137”“138”“139” 中的任何一个,且不能匹配其它字符串。

成对的方括号间,除了普通字符外,也可能出现短横线 “-”,表示与连续的一段字符匹配。例如,“[A-Z]” 可匹配任何单个大写字符构成的字符串,如 “E”“N”“G”“I” 等;“[0-9]” 可匹配任何单个数字构成的字符串;“[2-4A-Z]” 可匹配 2~4 的数字或者大写字母,但不能匹配 “1”“5” 或者 “a”;正则表达式 “13[5-9]”、“13[85-79]”、“13[956-8]”、“13[5-78-9]”、“13[56789]”“13[98765]”“13[567898765]”“13[5-56-67-78-89-9]” 互相之间都是等价的,都表示可匹配 “135”“136”“137”“138”“139” 中的任何一个,且不能匹配其它字符串。

成对的花括号内含一个整数,表示 “ 前一元素的标准应重复匹配若干次 ”。例如,“D{2}” 表示将字符 D 重复两次,匹配字符串 “DD”;正则表达式 “D{1}” 与 “D” 等价;“D{11}” 与 “DDDDDDDDDDD” 等价;“[Dd]{2}” 可匹配 “dd”“dD”“Dd”“DD” 四种字符串;“dd_[eng]{3}i” 可匹配 “dd_engi”“dd_eeei”“dd_enni”“dd_eeni”“dd_gnei” 等。成对的花括号的前面或者是普通字符或者是成对的方括号,不可能是另一对花括号。正则表达式 “1[35][0-9]{8}” 的意义是 “ 第一位是 1,第二位可以是 3 或 5,后面有 8 个 0~9 的数字 ”,它可以用来匹配中国大陆的手机号码。

【题目包含多组输入输出!】

输入格式

第一行是一个简化版的正则表达式。

以下若干行,每行一个字符串,直到文件结束,是对于第一行给定的正则表达式能否将其匹配的询问。以一个 0 截止。

不会出现空字符串。

输出格式

对于第二行开始的每个字符串,根据能否进行匹配,输出一行 “Regular Expression is Fun!” 或者 “Boring String Matching…”,不包括引号,其中的标点是英文标点(半角)。

样例

Input
[Dd]{2}_[eE][n-n][g_v][ii-jj]
dd_engi
Dd_engi
DD_envj
dD_eegi
dd-engi
ddengi
DD_Enhi
0
Output
Regular Expression is Fun!
Regular Expression is Fun!
Regular Expression is Fun!
Boring String Matching...
Boring String Matching...
Boring String Matching...
Boring String Matching...

21 人解决,28 人已尝试。

30 份提交通过,共有 173 份提交。

5.2 EMB 奖励。

创建: 7 年,8 月前.

修改: 2 年前.

最后提交: 10 月前.

来源: dd_engi

题目标签