正则表达式多选结构的顺序
正则表达式多选结构的顺序
先看一道编程题
从一段只包含[
.
,0
-9
]字符的字符串中提取出全部可能的ipv4地址。ipv4地址由十进制数和点来表示,每个地址包含4个十进制数,其范围为
0-255
,比如172.16.254.1
;同时,4个十进制数不会以0
开头,比如172.16.254.01
是不合法的。现输入一段文本
str="1.1.1111.16..172.16.254.1.1"
,要求用程序答出该字符串所有子串可能形成的ipv4地址。
很多人会想到,ipv4的正则表达式我可熟悉啦,肯定能快速完成!
于是从网上搜索到ipv4的正则表达式,写出了以下代码:
// java语言 import java.util.*; import java.util.regex.*; class solution { private static final pattern ipv4_pattern = pattern.compile("((([1-9][0-9]?)|(1[0-9]{2})|(2[0-4]\\d)|(25[0-5])|0)\\.){3}" + "(([1-9][0-9]?)|(1[0-9]{2})|(2[0-4]\\d)|(25[0-5])|0)"); public set<string> findallipv4(string input) { set<string> s = new treeset<string>(); matcher m = ipv4_pattern.matcher(input); int from = 0; while (m.find(from)) { s.add(input.substring(m.start(), m.end())); from++; } return s; } }
我们看完这一段代码,可以确定的是:1. 正则表达式没问题,正确的ipv4地址可以用它来验证;2. java regex api用法也没有太大问题,基本符合预期。
输入:0.0.0.255 输出:[0.0.0.25]
但这段代码的结果是不正确的,正确输出是[0.0.0.2, 0.0.0.25, 0.0.0.255]
,原因就出在正则中多选结构|
的用法上。
多选结构(alternation)
多选结构在不同的正则引擎中,工作原理是截然不同的。在传统型nfa
引擎中,会按照从左到右的顺序检查表达式中的多选分支,一旦可以匹配完成,其他的多选分支就不会尝试了。
以上节的正则表达式为例,我们单独摘出每个十进制数的表达式(([1-9][0-9]?)|(1[0-9]{2})|(2[0-4]\\d)|(25[0-5])|0)
,它会以如下顺序进行匹配:
1. ([1-9][0-9]?) # 一位数或两位数 2. (1[0-9]{2}) # 位于区间[100-199]的三位数 3. (2[0-4]\\d) # 位于区间[200-249]的三位数 4. (25[0-5]) # 位于区间[250-255]的三位数 5. 0 # 0
那么在针对输入字符串0.0.0.255
的匹配过程中,在进行第四个十进制数255
的匹配时,会优先计算表达式([1-9][0-9]?)
,这样可以匹配到25
和2
,而?(question mark)
在正则中是一个贪婪量词,因此仅会留下25
,所以最终我们看到了运行结果是[0.0.0.25]
。
以这些知识为前提,我们可以通过优先匹配多位数字,手工解析少量数字
的方式得到正确的解答程序,这样做的话,正则表达式需要做一些调整,将多位数匹配的多选分支放在前面,即(25[0-5]|2[0-4]\\d|1\\d{2}|[1-9]\\d|\\d)
,代码如下:
// java语言 import java.util.*; import java.util.regex.*; class solution { private static final pattern ipv4_pattern = pattern.compile("((25[0-5]|2[0-4]\\d|1\\d{2}|[1-9]\\d|\\d)\\.){3}" + "(25[0-5]|2[0-4]\\d|1\\d{2}|[1-9]\\d|\\d)"); public set<string> findallipv4(string input) { set<string> s = new treeset<string>(); matcher m = ipv4_pattern.matcher(input); int from = 0; int lastdotidx = 0; string sub = null; while (m.find(from)) { sub = input.substring(m.start(), m.end()); s.add(sub); lastdotidx = sub.lastindexof('.'); if (lastdotidx == sub.length() - 3) { s.add(sub.substring(0, sub.length() - 1)); } else if (lastdotidx == sub.length() - 4) { s.add(sub.substring(0, sub.length() - 1)); s.add(sub.substring(0, sub.length() - 2)); } from++; } return s; } }
friedl, j. e. (2006). mastering regular expressions. " o'reilly media, inc.", p174-p175.
friedl, j. e. (2006). mastering regular expressions. " o'reilly media, inc.", p142.