正则表达式 – 匹配有限自然数系列

发布时间：2020-12-14 06:05:16 所属栏目：百科来源：网络整理

导读：如何将有限 natural number系列与正则表达式匹配？所以,要求是：字符串包含数字和空格(作为分隔符) 第一个数字是1 每个数字(第一个除外)等于之前的数字1 应该匹配： 1 1 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 长序列的后续数字从1到10 ^ 100

如何将有限 natural number系列与正则表达式匹配？

所以,要求是：

>字符串包含数字和空格(作为分隔符)
>第一个数字是1
>每个数字(第一个除外)等于之前的数字1

应该匹配：

> 1
> 1 2
> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
>长序列的后续数字从1到10 ^ 1000

不应该匹配：

>“
> 1 3 4
> 1 2 3 4 5 6 6

除此之外,还有一些正则表达式的要求：

>它应该是单一的单次表达式,而不是循环条件算法的指令包
>它可以使用perl正则表达式的所有功能

我不确定正则表达式是否实际上是懒惰的,所以如果它们真的很棒.因为自然数系列在数论中的原始含义是非有限的.

最后一个.请注意,我没有使用错误的工具来完成这项工作.它根本不是真正的编程任务.

解决方法

干得好.在Perl v5.10到v5.14上测试过.关键是递归模式,我们在(？& Sequence)规则上进行递归.这是一种归纳证明.

bigint是为了防止您真的想要生成1 … 10 ** 10_000的序列.如果您可以将自己限制为机器本机整数,32位或64位,具体取决于您的平台,它将运行得更快.

#!/usr/bin/env perl
use v5.10;
use bigint;  # only if you need stuff over maxint

my $pat = qr{
    ^
    (?= 1 b )
    (?<Sequence>
        (?<Number> d+ )
        (?:
            s+
            (??{  "(?=" . (1 + $+{Number}) . ")" })
            (?&Sequence)
        )?
    )
    $
}x;

# first test embedded data
while (<DATA>) {
    if ( /$pat/ ) {
        print "PASS: ",$_;

    } else {
        print "FAIL: ",$_;
    }
}

# now generate long sequences
for my $big ( 2,10,25,100,1000,10_000,100_000 ) {
    my $str = q();
    for (my $i = 1; $i <= $big; $i++) {
        $str .= "$i ";
    }
    chop $str;
    if ($str =~ $pat) {
        print "PASS: ";
    } else {
        print "FAIL: ";
    }
    if (length($str) > 60) {
        my $len = length($str);
        my $first = substr($str,10);
        my $last  = substr($str,-10);
        $str = $first . "[$len chars]" . $last;
    }
    say $str;

}


__END__
5
fred
1
1 2 3
1 3 2
1 2 3 4 5
1 2 3 4 6
2 3 4 6
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 2 3 4 5 6 6

哪个运行产生：

FAIL: 5
FAIL: fred
PASS: 1
PASS: 1 2 3
FAIL: 1 3 2
PASS: 1 2 3 4 5
FAIL: 1 2 3 4 6
FAIL: 2 3 4 6
PASS: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
FAIL: 1 2 3 4 5 6 6
PASS: 1 2
PASS: 1 2 3 4 5 6 7 8 9 10
PASS: 1 2 3 4 5 [65 chars]2 23 24 25
PASS: 1 2 3 4 5 [291 chars] 98 99 100
PASS: 1 2 3 4 5 [3892 chars]8 999 1000
PASS: 1 2 3 4 5 [588894 chars]999 100000

看似自私的风险,有a book涵盖了这种事情.请参阅Programming Perl,第4版第5章中的“花式模式”部分.您需要查看“命名组”,“递归模式”和“语法模式”的新章节.这本书是在打印机上,应该在一两天内以电子方式提供.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!