使用正则表达式来比较数字

Question

所以这是一个明显的例子,"你做错了".我实际上并不打算这样做,但是在工作中的谈话引发了这个问题:

您是否可以生成正则表达式来确定整数是否小于任意值.

对于某些值,这很容易.对于小于1000的整数,\ d {1,3}应该可以解决问题.对于整数<500,它有点棘手,但不是那么糟糕,因为你可以使用[0-4] {0,1}\d {1,2}.

一旦你达到任意值,它就会变得很多.例如,小于255的所有数字都类似于\ d {1,2} | [0-1]\d {2} | [2] [0-4]\d | [2] [5] [0-4].

有一个正则表达式可以在这里工作吗？或者你必须以编程方式生成正则表达式？

(再次,让我指出,我无意实际做到这一点.显然,在您喜欢的编程语言中使用"foo <bar"更有效,更容易阅读.)

Answer 1

这很容易。

#!/usr/bin/env perl
use strict;
use warnings;
use Regexp::Assemble;

for my $n (@ARGV)  {
    my $asm = new Regexp::Assemble;
    for (1 .. $n) { $asm->add($_) }
    for ($asm->re){
        s/\)$/\$/;
        s/^[^:]*:/^/;
        print "$n => /$_/\n";
    }
}

现在运行它来查找与 1 和该数字之间的整数匹配的模式：

$ perl /tmp/ra 5 15 153 401 1144
5 => /^[12345]$/
15 => /^(?:[23456789]|1[012345]?)$/
153 => /^(?:1(?:[6789]|5[0123]?|0\d?|1\d?|2\d?|3\d?|4\d?)?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)$/
401 => /^(?:1(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|2(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|3(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|4(?:[123456789]|0[01]?)?|5\d?|6\d?|7\d?|8\d?|9\d?)$/
1144 => /^(?:1(?:0(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|1(?:[56789]|4[01234]?|0\d?|1\d?|2\d?|3\d?)?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|2(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|3(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|4(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|5(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|6(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|7(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|8(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|9(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?)$/

Answer 2

您将需要为每个边界数生成表达式。假设有一个正则表达式可以完成这项工作。然后，该正则表达式必须能够将某些字符序列作为输入。然而，我们知道正则表达式和有限状态自动机是等价的，所以这相当于我们可以构造一个 FSM，因为可能的数量是无限的，这将需要无限数量的状态，这与 FSA 的定义相矛盾。