欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-11-14 18:19:34
多选结构在不同的正则引擎中,工作原理是截然不同的。在传统型NFA引擎中,会按照从左到右的顺序检查表达式中的多选分支,一旦可以匹配完成,其他的多选分支就不会尝试了。 ......

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

先看一道编程题

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