正则表达式匹配3的倍数

你能写一个正则表达式只匹配3的倍数吗?例如,你要匹配3,03,24,1122,
但是不匹配5, 10或20. 继续读下去学到新一手

困难的解决方式

你可能认为可以这样写: /^(0|102|10101|201)+$/ – 在这里0代表[0369]
,1代表[147], 2代表[258] . 但这少了1122,2211或222.
你继续添加不同情况, 最后可能会得到答案, 但很困难…

用有限状态机

有一种简单的方法需要你知道正则表达式和有限状态机是可以互相转换的.
我们从3的倍数的状态机开始.
一个数如果是3的倍数,当且仅当它的所有数字的和是3的倍数.

状态机处理输入并跟踪数字的和.我们只需要把和对3取余,得到一个简单的状态机,只有3个状态
:A(开始状态),B(余1),C(余2).
在状态A时, 输入0,3,6,9, 还在状态A.
输入1,4,7转到状态B.输入2,5,8转入状态C. 图片1:
状态A
在状态B时, 有类似的规则图片2:
状态B
最后,这是最终的状态机图片3:
状态C

转换状态机

要转换状态机到正则表达式,我们先写一些等式. 对每个状态,我们有如下等式:

A = ∅ | A[0369] | B[258] | C[147]
B = A[147] | B[0369] | C[258]
C = A[258] | B[147] | C[0369]

∅ 表示初始状态. 为了表达简单,我们用0,1,2表示3组数字:

A = ∅ | A0 | B2 | C1
B = A1 | B0 | C2
C = A2 | B1 | C0

我们的目标是替换B和C, 得到一个A的表达式. 递归的规则是这样

 X=Xw|Y|Z 转换为X=Yw*|XW* , 也可以写成X=(Y|X)w*

A = ( ∅ | B2 | C1 ) 0*
B = ( A1 | C2 ) 0*
C = ( A2 | B1 ) 0*

C很容易代替:

A = ( ∅ | B2 | ( A2 | B1 ) 0* 1 ) 0*
B = (A1 | ( A2 | B1 ) 0* 2 ) 0*

再重复这一过程:

A = 0* | B2 0* | ( A2 | B1 ) 0* 1 0*
B = A1 0* | ( A2 | B1 ) 0* 2 0*

A = 0* | B2 0* | A2 0* 1 0* | B1 0* 1 0*
B = A1 0* | A2 0* 2 0* | B1 0* 2 0*

A = ( 0* | B2 0* | B1 0* 1 0* ) ( 2 0* 1 0* )*
B = ( A1 0* | A2 0* 2 0* ) ( 1 0* 2 0* )*

现在可以代替B:

A = (
      0* |
      ( A1 0* | A2 0* 2 0* ) (1 0* 2 0* )* 2 0* |
      ( A1 0* | A2 0* 2 0* ) (1 0* 2 0* )* 1 0* 1 0*
    ) (2 0* 1 0* )*

A = 0* ( 2 0* 1 0* )* |
    A1 0* ( 1 0* 2 0* )* 2 0* ( 2 0* 1 0* )* |
    A2 0* 2 0* ( 1 0* 2 0* )* 2 0* ( 2 0* 1 0* )* |
    A1 0* ( 1 0* 2 0* )* 1 0* 1 0* ( 2 0* 1 0* )* |
    A2 0* 2 0* ( 1 0* 2 0* )* 1 0* 1 0* ( 2 0* 1 0* )*

这时,我们有如以转换:

X = a | Xb | Xc 可以写成 X = a (b | c)*

那么A就可以写成:

A = 0* ( 2 0* 1 0* )* (
      1 0* ( 1 0* 2 0* )* 2 0* ( 2 0* 1 0* )* |
      2 0* 2 0* ( 1 0* 2 0* )* 2 0* ( 2 0* 1 0* )* |
      1 0* ( 1 0* 2 0* )* 1 0* 1 0* ( 2 0* 1 0* )* |
      2 0* 2 0* ( 1 0* 2 0* )* 1 0* 1 0* ( 2 0* 1 0* )*
    )*

我们得到了一个答案,这个规则可以转换成正则表达式! 我们可以再简化一下

a* ( b a* )* becomes ( a | b )*

A = 0* (
      2 0* 1 0* |
      1 0* ( 1 0* 2 0* )* 2 0* |
      2 0* 2 0* ( 1 0* 2 0* )* 2 0* |
      1 0* ( 1 0* 2 0* )* 1 0* 1 0* |
      2 0* 2 0* ( 1 0* 2 0* )* 1 0* 1 0*
    )*

现用一次同样的规则:

A = (
      0* |
      2 0* 1 |
      1 ( 0 | 1 0* 2 )* 2 |
      2 0* 2 ( 0 | 1 0* 2 )* 2 |
      1 ( 0 | 1 0* 2 )* 1 0* 1 |
      2 0* 2 ( 0 | 1 0* 2 )* 1 0* 1
    )*

解决方案

上面的规则可以转换成正则表达式,加上^和$的限制:

/^(0|20*1|1(0|10*2)*2|20*2(0|10*2)*2|1(0|10*2)*10*1|20*2(0|10*2)*10*1)*$/

然后把0,1,2替换回它们所代表的内容:

/^([0369]|[258][0369]*[147]|[147]([0369]|[147][0369]*[258])*[258]|[258][0369]*[258]([0369]|[147][0369]*[258])*[258]|[147]([0369]|[147][0369]*[258])*[147][0369]*[147]|[258][0369]*[258]([0369]|[147][0369]*[258])*[147][0369]*[147])*$/

不相信?来试一下: 输入一个数字:

一些链接

regex.alf.nu : test your regexp skills
A regular expression crossword
(pdf)
regexp.quaxio.com : A tool I wrote to
visulize regexps

感谢

erling for challenging me with this stuff :)
joel for finding a shorter solution:

/^(0|201|(1|202)(0|102)(2|101))$/
camitz for pointing out a
mistake