regex - 使用正则表达式检查数字可除性

Question

给定一个十进制数字N作为一串数字，我如何仅使用正则表达式检查它是否可以被M整除，而不转换为int？

M = 2、4、5、10很明显。对于M = 3，这里有一些有趣的见解：Regex filter numbers divisible by 3

谁能为M = 7、9、11、13等提供解决方案？一个通用的？

测试代码（使用python，但可以使用任何语言）：

M = your number, e.g. 2
R = your regexp, e.g., '^[0-9]*[02468]$'

import re
for i in range(1, 2000):
    m = re.match(R, str(i))
    if i % M:
        assert not m, '%d should not match' % i
    else:
        assert m, '%d must match' % i

对于那些好奇的人，下面是 M=3的示例（假定引擎具有递归支持）：

^
(
    | [0369]+ (?1)
    | [147] (?1) [258] (?1)
    | [258] (?1) [147] (?1)
    | ( [258] (?1) ) {3}
    | ( [147] (?1) ) {3}
)
$

更新：有关更多讨论和示例，请参见此 thread。在那里张贴的表达式原来是错误的（70 * N失败），但是“如何到达”部分很有教育意义。

Answer 1

可能令人惊讶的结果是，这样的正则表达式始终存在。毫不奇怪的是，它通常没有用。

存在结果来自deterministic finite automata（DFA）与正则表达式之间的对应关系。因此，让我们制作一个DFA。用N表示模数（不必是质数），用B表示数值基，对于普通的十进制数，该数字为10。具有标记为0到N-1的N个状态的DFA。初始状态为0。DFA的符号为数字0到B-1。状态代表输入字符串左前缀的其余部分，除以N时，将被解释为整数。边沿表示在右侧添加数字时的状态变化。可以说，这是状态图S（状态，数字）= B *状态+数字（模N）。接受状态为0，因为余数为零表示可分割。所以我们有一个DFA。 DFA可以识别的语言与正则表达式可以识别的语言相同，因此存在。因此，尽管这很有趣，但它并没有帮助，因为它不会告诉您如何确定表达式的太多信息。

如果需要通用算法，则可以在运行时轻松构建此类DFA，并通过直接计算填充其状态表。初始化只是一对运行时间为O（M * N）的嵌套循环。机器识别每个输入字符的时间是恒定的。这是非常快的，但是如果您确实需要，则不使用正则表达式库。

在获得实际的正则表达式时，我们需要查看Fermat's Little Theorem。根据定理，我们知道B ^（N-1）== 1（模N）。例如，当N = 7和B = 10时，这意味着每6位数字的块等效于0 ... 6范围内的某个数字。指数可以小于N-1；通常，它是N的Euler totient function的一个因数。称为块D的大小。D个数字的块有N个正则表达式，每个正则表达式表示N的余数的一个特定等价类。最多，这些表达式具有长度O（B ^ D），很大。对于N = 7，这是一组正则表达式，长度为一百万个字符；我想这会破坏大多数regexp库。

这与示例代码中表达式的工作方式有关。表达式(?1)是等于0（mod 3）的匹配字符串。这适用于N = 3，因为10 ^ 1 == 1（mod 3），这意味着A0B == AB（mod 3）。当指数大于1时，这会更复杂，但是原理是相同的。 （严格来说，请注意示例代码使用的识别器不仅仅是正则表达式。）表达式[0369]，[147]和[258]是a中数字0、1和2的正则表达式。模3表达式。概括地说，您将以类似方式使用上述正则表达式数字。

我之所以没有提供代码，是因为（1）与该答案相比，编写时间更长；（2）我真的怀疑它是否可以在任何已知的实现中执行。