之前在知乎上看到了有人用正則表達(dá)式匹配 3 的倍數(shù)，很驚訝，原來正則表達(dá)式還能這么用。先看下正則表達(dá)式：
^[0369]*(([147][0369]*|[258][0369]*[258][0369]*)([147][0369]*[258][0369]*)*([258][0369]*|[147][0369]*[147][0369]*)|[258][0369]*[147][0369]*)*$
是不是很難懂？知乎上有對這個表達(dá)式的簡要說明，不過比較簡略。本文將對該表達(dá)式的推導(dǎo)過程進(jìn)行詳細(xì)說明。
整除判斷
本文將介紹一種通用的方法，同樣后面闡述的方法也不局限于 3，而是以 3 為例，可以推廣到任意自然數(shù) n 的方法。
判斷一個數(shù)能否被 n 整除，可以轉(zhuǎn)換為判斷一個數(shù)被 n 除后的余數(shù)是否為 0。假設(shè)需要判斷的數(shù)是 m，那么有 m = i * n + p。假設(shè) m 是一個 k 位數(shù)，則可寫為 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)的表達(dá)式不太好描述。。。），那么 f(2) mod n = (10 * a + b) mod n，根據(jù)模運算加法和乘法的性質(zhì)，可知 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
由上面的分析我們可以知道：
- 一個數(shù)除以
n的余數(shù)只有可能在 [0,n-1] 上； - 一個數(shù)的前
k位數(shù)除以n的余數(shù)可以通過這個數(shù)前k - 1位除以n的余數(shù)計算出來（遞推式）。
例如判斷 120 是否能被3 整除的過程如下：
1 mod 3 余數(shù)為 1
12 mod 3 余數(shù)為 (1 * 1 + 2) mod 3 = 0
120 mod 3 余數(shù)為 (1 * 0 + 0) mod 3 = 0，從而 120 能被 3 整除
由此可知，我們可以寫出被除數(shù)的每一位數(shù)字和被 n 除后余數(shù)之間的狀態(tài)轉(zhuǎn)換過程，每一個余數(shù)是一種狀態(tài)，而每一個數(shù)字是轉(zhuǎn)換的一條邊。那么對于 n = 3 來說，余數(shù)有 0、1、2 三種狀態(tài)，輸入有 0、1、2、…、9 十種。
下面用表格列出所有狀態(tài)：
| 上一個狀態(tài)（余數(shù)） | 輸入（0-9） | 下一個狀態(tài) |
|---|---|---|
| 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 轉(zhuǎn)正規(guī)文法
為了區(qū)分，我們標(biāo)記 A 為終止到狀態(tài)0的字符串集合，B C類似，那么可以列出三個方程：
A = A[0369]|B[258]|C[147]|ε
B = A[147]|B[0369]|C[258]
C = A[258]|B[147]|C[0369]
由此可知，這是左線性文法，易推導(dǎo)出產(chǎn)生式：
L -> LU|V
消除左遞歸，推導(dǎo)得：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]*)*
對結(jié)果加上開始結(jié)束符^$，即完成了對3的倍數(shù)正則表達(dá)式的推導(dǎo)。
驗證
用 JavaScript 寫一段程序測試運行結(jié)果，代碼如下：
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));
運行結(jié)果如下，說明能正確匹配出結(jié)果。
