正则表达式多选结构的顺序

正则表达式多选结构的顺序

先看一道编程题

从一段只包含[.,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]?),这样可以匹配到252,而?(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;
    }
}

  1. Friedl, J. E. (2006). Mastering regular expressions. " O‘Reilly Media, Inc.", p174-p175.

  2. Friedl, J. E. (2006). Mastering regular expressions. " O‘Reilly Media, Inc.", p142.

相关推荐