之前在知乎上看到了有人用正则表达式匹配3的倍数，不觉呀然一惊，原来正则表达式还能这么用，匹配邮箱、URL简直是太弱了。先看下正则表达式：

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

是不是完全看不懂？即便是有多年经验的Web前端工程师，写过无数的正则表达式，估计也难以理解。知乎上有对这个表达式的简要说明，不过比较简略。本文将对该表达式的推导过程进行详细说明。

1 整除判断

如何判断一个数能被3整除？相信大家小学就学过，可以采用各个位数相加再判断的方法。那么如何判断一个数能被n整除呢？本文将介绍一种通用的方法，同样后面阐述的方法也不局限于3，而是以3为例，可以推广到任意自然数n的方法。

判断一个数能否被n整除，可以转换为判断一个数被n除后的余数是否为0。假设需要判断的数是m，那么有m=i*n+p。假设m是一个k位数，则可写为m=10^(k-1)*a+10^(k-2)*b+10^(k-3)*c+…+10*g+h，其中a、b、c、…、g、h∈{0,1,2,3,4,5,6,7,8,9}，若定义f(0)=0，f(1)=a，f(2)=10*a+b，f(3)=100*a+10*b+c（f(x)的表达式不太好描述。。。），那么f(2) mod n=(10*a+b) mod n，根据模运算加法和乘法的性质，可知f(2) mod n=(10*a+b) mod n=(10*a mod n+b mod n) mod n=(10 mod n*a mod n+b mod n) mod n=(10 mod n*f(1) mod n+b mod n)，同理可得到一个递推式：

f(k) mod n=(10 mod n*f(k-1) mod n+h mod n) mod n

2 确定DFA

由上面的分析我们可以知道：

一个数除以n的余数只有可能在[0,n-1]上；
一个数的前k位数除以n的余数可以通过这个数前k-1位除以n的余数计算出来（递推式）。

例如判断120是否能被3整除的过程如下：

1 mod 3余数为1
12 mod 3余数为(1*1+2) mod 3=0
120 mod 3余数为(1*0+0) mod 3=0，从而120能被3整除

由此可知，我们可以写出被除数的每一位数字和被n除后余数之间的状态转换过程，每一个余数是一种状态，而每一个数字是转换的一条边。那么对于n=3来说，余数有0、1、2三种状态，输入有0、1、2、…、9十种。

下面用表格列出所有状态（十进制真的不少。。。）

上一个状态（余数）	输入（0-9）	下一个状态
0	0	(1*0+0) mod 3=0
1	0	(1*1+0) mod 3=1
2	0	(1*2+0) mod 3=2
0	1	(1*0+1) mod 3=1
1	1	(1*1+1) mod 3=2
2	1	(1*2+1) mod 3=0
0	2	(1*0+2) mod 3=2
1	2	(1*1+2) mod 3=0
2	2	(1*2+2) mod 3=1
0	3	(1*0+3) mod 3=0
1	3	(1*1+3) mod 3=1
2	3	(1*2+3) mod 3=2
0	4	(1*0+4) mod 3=1
1	4	(1*1+4) mod 3=2
2	4	(1*2+4) mod 3=0
0	5	(1*0+5) mod 3=2
1	5	(1*1+5) mod 3=0
2	5	(1*2+5) mod 3=1
0	6	(1*0+6) mod 3=0
1	6	(1*1+6) mod 3=1
2	6	(1*2+6) mod 3=2
0	7	(1*0+7) mod 3=1
1	7	(1*1+7) mod 3=2
2	7	(1*2+7) mod 3=0
0	8	(1*0+8) mod 3=2
1	8	(1*1+8) mod 3=0
2	8	(1*2+8) mod 3=1
0	9	(1*0+9) mod 3=0
1	9	(1*1+9) mod 3=1
2	9	(1*2+9) mod 3=2

由此可见：0—[0,3,6,9]—>0，0—[1,4,7]—>1，0—[2,5,8]—>2，1—[2,5,8]—>0，1—[0,3,6,9]—>1，1—[1,4,7]—>2，2—[1,4,7]—>0，2—[2,5,8]—>1，2—[0,3,6,9]—>2。用DFA表示如下：

DFA

3 DFA转3型文法（正规文法）

为了区分，我们标记A为终止到状态0的字符串集合，B C类似，那么可以列出三个方程：

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

由此可知，这是左线性文法，易推导出产生式：

L -> LU|V

消除左递归，推导得：L -> VU*

因此上面方程可以改写为：

A = (ε|B[258]|C[147])[0369]*   (1)
B = (A[147]|C[258])[0369]*   (2)
C = (A[258]|B[147])[0369]*   (3)

将(3)代入(1)(2)得

A = (ε|B[258]|(A[258]|B[147])[0369]*[147])[0369]*  (4)
B = (A[147]|(A[258]|B[147])[0369]*[258])[0369]*   (5)

用分配律展开(5)中的竖线得到

B = A[147][0369]*|A[258][0369]*[258][0369]*|B[147][0369]*[258][0369]*

故

B = A[147][0369]*([147][0369]*[258][0369]*)*|A[258][0369]*[258][0369]*([147][0369]*[258][0369]*)*

把它代入(4)得

A = (ε|B[258]|(A[258]|B[147])[0369]*[147])[0369]*
= [0369]*|B[258][0369]*|A[258][0369]*[147][0369]*|B[147][0369]*[147][0369]*
= [0369]*|A[147][0369]*([147][0369]*[258][0369]*)*[258][0369]*|A[258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[258][0369]*|A[258][0369]*[147][0369]*|A[147][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]*|A[258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]*
= [0369]*([147][0369]*([147][0369]*[258][0369]*)*[258][0369]*|[258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[258][0369]*|[147][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]*|[258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]*|[258][0369]*[147][0369]*)*
= [0369]*(([147][0369]*|[258][0369]*[258][0369]*)([147][0369]*[258][0369]*)*([258][0369]*|[147][0369]*[147][0369]*)|[258][0369]*[147][0369]*)*

对结果加上开始结束符^$，即完成了对3的倍数正则表达式的推导。

4 验证

用js写一段程序测试运行结果，代码如下：

const regexp = /^[0369]*(([147][0369]*|[258][0369]*[258][0369]*)([147][0369]*[258][0369]*)*([258][0369]*|[147][0369]*[147][0369]*)|[258][0369]*[147][0369]*)*$/;
console.log(regexp.test(120));
console.log(regexp.test(112233));
console.log(regexp.test(1024));

运行结果如下，说明能正确匹配出结果。

运行结果

用正则表达式匹配3的倍数

1 整除判断

2 确定DFA

3 DFA转3型文法（正规文法）

4 验证

Reference