之前在知乎上看到了有人用正则表达式匹配 3 的倍数，很惊讶，原来正则表达式还能这么用。先看下正则表达式：
^[0369]*(([147][0369]*|[258][0369]*[258][0369]*)([147][0369]*[258][0369]*)*([258][0369]*|[147][0369]*[147][0369]*)|[258][0369]*[147][0369]*)*$
是不是很难懂？知乎上有对这个表达式的简要说明，不过比较简略。本文将对该表达式的推导过程进行详细说明。
整除判断
本文将介绍一种通用的方法，同样后面阐述的方法也不局限于 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
确定 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 转正规文法
为了区分，我们标记 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的倍数正则表达式的推导。
验证
用 JavaScript 写一段程序测试运行结果，代码如下：
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));
运行结果如下，说明能正确匹配出结果。
