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

先看一道编程题

从一段只包含[.,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;
    }
}

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.