给定一个十进制数N
作为数字字符串,我如何检查它是否可被M
整除,只使用正则表达式,而不转换为?
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上失败),但“如何到达那里”部分非常有教育意义。
发布于 2012-11-05 07:08:53
可能令人惊讶的结果是,这样的正则表达式总是存在的。不太令人惊讶的是,它通常是没有用的。
存在的结果来自于deterministic finite automata和正则表达式之间的对应关系。因此,让我们来做一个DFA。用N表示模数(它不需要是素数),用B表示数基,对于普通的十进制数,B是10。具有N个状态的DFA,标记为0到N-1。初始状态为0。DFA的符号是数字0到B-1。状态表示输入字符串的左前缀的剩余部分,在除以N时解释为整数。边表示向右侧添加数字时状态的变化。在算术上,这是状态映射S(状态,数字)=B*状态+数字(模N)。接受状态为0,因为零余数表示可除性。所以我们有一个DFA。DFA识别的语言与正则表达式识别的语言相同,因此存在一种语言。因此,虽然这很有趣,但它没有帮助,因为它没有告诉您如何确定表达式的太多信息。
如果您需要一个通用算法,那么在运行时构建这样一个DFA并通过直接计算填充它的状态表是很容易的。初始化只是一对运行时间为O(M * N)的嵌套循环。机器的识别是每个输入字符的恒定时间。这是非常快的,但是没有使用regexp库,如果你真的需要的话。
为了得到一个真正的正则表达式,我们需要看看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,这是一组长度为一百万个字符的正则表达式;我可以想象这会破坏大多数正则表达式库。
这与示例代码中的表达式如何工作有关;表达式(?1)
匹配等于0(Mod3)的字符串。从10^1 == 1 (mod 3)开始使用N=3,这意味着A0B == AB (Mod3)。当指数大于1时,这会更复杂,但原理是相同的。(注意,严格地说,示例代码使用的识别器不仅仅是正则表达式。)表达式[0369]
、[147]
和[258]
是模3表达式中数字0、1和2的正则表达式。一般而言,您将以类似的方式使用上面的regexp数字。
我没有提供代码,因为(1)编写代码的时间会比这个答案更长,(2)我真的怀疑它是否可以在任何已知的实现中执行。
发布于 2012-09-14 19:58:01
如果你的数字是基于一元的,你可以使用这个正则表达式:s/1{divisor}//g
,然后测试这个数字是否为空。
下面是Perl的一种方法
my @divs = (2,3,5,7,11,13);
for my $num(2..26) {
my $unary = '1'x$num; # convert num to unary
print "\n$num can be divided by : ";
for(@divs) {
my $test = $unary;
$test =~ s/1{$_}//g;
print "$_, " unless $test;
}
}
输出:
2 can be divided by : 2,
3 can be divided by : 3,
4 can be divided by : 2,
5 can be divided by : 5,
6 can be divided by : 2, 3,
7 can be divided by : 7,
8 can be divided by : 2,
9 can be divided by : 3,
10 can be divided by : 2, 5,
11 can be divided by : 11,
12 can be divided by : 2, 3,
13 can be divided by : 13,
14 can be divided by : 2, 7,
15 can be divided by : 3, 5,
16 can be divided by : 2,
17 can be divided by :
18 can be divided by : 2, 3,
19 can be divided by :
20 can be divided by : 2, 5,
21 can be divided by : 3, 7,
22 can be divided by : 2, 11,
23 can be divided by :
24 can be divided by : 2, 3,
25 can be divided by : 5,
26 can be divided by : 2, 13,
发布于 2017-09-27 00:45:24
这是一个古老的问题,但现有的答案中没有一个包含代码。早在2010年,我就编写了计算这些正则表达式的代码which is online here,并且有一个到the commented source code的链接,所以我想在这里添加一个链接可能会很有用。
除了我使用状态消除直接从eh9’s answer计算正则表达式,然后对结果进行一些简化之外,该技术基本上与DFA中描述的技术相同。它们是普通的正则表达式,没有递归。(使用递归将使结果更短,但我认为有趣的是,不使用递归也是可能的。)
结果并不像EH9估计的那样冗长。例如,下面是一个正则表达式,它匹配基数为10的7的倍数:
/*
* 提示:该行代码过长,系统自动注释不进行高亮。一键复制会移除系统注释
* ^(0|7|[18]5*4|(2|9|[18]5*6)(3|[29]5*6)*(1|8|[29]5*4)|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4))|(4|[18]5*[18]|(2|9|[18]5*6)(3|[29]5*6)*(5|[29]5*[18])|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(2|9|35*4|(4|35*6)(3|[29]5*6)*(1|8|[29]5*4)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4)))|(5|[18]5*[29]|(2|9|[18]5*6)(3|[29]5*6)*(6|[29]5*[29])|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(4|[18]5*[18]|(2|9|[18]5*6)(3|[29]5*6)*(5|[29]5*[18])|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))(4|[07]5*[29]|(1|8|[07]5*6)(3|[29]5*6)*(6|[29]5*[29])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))*(6|[07]5*4|(1|8|[07]5*6)(3|[29]5*6)*(1|8|[29]5*4)|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(2|9|35*4|(4|35*6)(3|[29]5*6)*(1|8|[29]5*4)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4))))|(6|[18]5*3|(2|9|[18]5*6)(3|[29]5*6)*(0|7|[29]5*3)|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3))|(4|[18]5*[18]|(2|9|[18]5*6)(3|[29]5*6)*(5|[29]5*[18])|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(1|8|35*3|(4|35*6)(3|[29]5*6)*(0|7|[29]5*3)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3)))|(5|[18]5*[29]|(2|9|[18]5*6)(3|[29]5*6)*(6|[29]5*[29])|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(4|[18]5*[18]|(2|9|[18]5*6)(3|[29]5*6)*(5|[29]5*[18])|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))(4|[07]5*[29]|(1|8|[07]5*6)(3|[29]5*6)*(6|[29]5*[29])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))*(5|[07]5*3|(1|8|[07]5*6)(3|[29]5*6)*(0|7|[29]5*3)|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(1|8|35*3|(4|35*6)(3|[29]5*6)*(0|7|[29]5*3)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3)))))(2|9|45*3|(5|45*6)(3|[29]5*6)*(0|7|[29]5*3)|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3))|(0|7|45*[18]|(5|45*6)(3|[29]5*6)*(5|[29]5*[18])|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(1|8|35*3|(4|35*6)(3|[29]5*6)*(0|7|[29]5*3)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3)))|(1|8|45*[29]|(5|45*6)(3|[29]5*6)*(6|[29]5*[29])|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(0|7|45*[18]|(5|45*6)(3|[29]5*6)*(5|[29]5*[18])|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))(4|[07]5*[29]|(1|8|[07]5*6)(3|[29]5*6)*(6|[29]5*[29])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))*(5|[07]5*3|(1|8|[07]5*6)(3|[29]5*6)*(0|7|[29]5*3)|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(1|8|35*3|(4|35*6)(3|[29]5*6)*(0|7|[29]5*3)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3)))))*(3|45*4|(5|45*6)(3|[29]5*6)*(1|8|[29]5*4)|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4))|(0|7|45*[18]|(5|45*6)(3|[29]5*6)*(5|[29]5*[18])|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(2|9|35*4|(4|35*6)(3|[29]5*6)*(1|8|[29]5*4)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4)))|(1|8|45*[29]|(5|45*6)(3|[29]5*6)*(6|[29]5*[29])|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(0|7|45*[18]|(5|45*6)(3|[29]5*6)*(5|[29]5*[18])|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))(4|[07]5*[29]|(1|8|[07]5*6)(3|[29]5*6)*(6|[29]5*[29])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))*(6|[07]5*4|(1|8|[07]5*6)(3|[29]5*6)*(1|8|[29]5*4)|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(2|9|35*4|(4|35*6)(3|[29]5*6)*(1|8|[29]5*4)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4))))))*$
*/
它“只有”12,733个字符,在我尝试过的实现中工作得很好。
PS。为了了解使用递归有多不有趣,下面是一个Perl程序,它使用递归正则表达式测试7的可除性:
my $re = qr{
^($|[07](?1)|[18](?2)|[29](?3)|3(?4)|4(?5)|5(?6)|6(?7))
|(?!)(?:
([07](?4)|[18](?5)|[29](?6)|3(?7)|4(?1)|5(?2)|6(?3))
| ([07](?7)|[18](?1)|[29](?2)|3(?3)|4(?4)|5(?5)|6(?6))
| ([07](?3)|[18](?4)|[29](?5)|3(?6)|4(?7)|5(?1)|6(?2))
| ([07](?6)|[18](?7)|[29](?1)|3(?2)|4(?3)|5(?4)|6(?5))
| ([07](?2)|[18](?3)|[29](?4)|3(?5)|4(?6)|5(?7)|6(?1))
| ([07](?5)|[18](?6)|[29](?7)|3(?1)|4(?2)|5(?3)|6(?4))
)
}x;
while (<>) {
print(/$re/ ? "matches\n" : "does not match\n");
}
这只是DFA作为递归正则表达式的直接表达式。
https://stackoverflow.com/questions/12403842
复制相似问题