來源：https://jex.im/PRogramming/triple-regex.html

Regex Golf上有一道題名為 Triples，即要求用正則表達式匹配3的倍數，還有一道匹配7的倍數的練習題。這種問題如果人肉解決的話，相當于做一道包含幾十個數的四則運算題，不管你怎么想，反正我小時候遇到五個數以上的四則運算題都是直接略過。小時候不好好學習，現在該怎么辦呢？——現在我會寫代碼了啊。 解決方案其實很簡單：寫程序構造一個接受3的倍數的DFA，再將其轉換成正則式即可。

Finite Automaton

術語聽起來都好抽象，其實解決思路就像小學生做除法一樣簡單。比如我們如何判定4641是3的倍數？ 從左往右一個數一個數地計算，最后余0即可：

46414    % 3 => 116   % 3 => 1 14  % 3 => 2  21 % 3 => 0
一次讀一個數字，然后輸出一個余數，如果最后余0則表示OK。影響我們判斷的有兩個因素：上次運算結果的余數，當前讀入的字符。自動機就是這樣一種機器，開始處于一個狀態，每次讀入一個字符，然后輸出一個新狀態。所以上面的運算可以用下面的自動機執行過程表示，起始狀態為0，余數即為輸出狀態：
  40 => 1
  61 => 1
  41 => 2
  12 => 0
用人話來講就是：上次余數為0時，遇到4則余1；上次余1時遇到6則還余1；……數字只有10個，所以我們可以窮舉，除3余數只有0、1、2三種可能，當余數為任意一個時，下一次遇到的數字只有10種可能， 全部情況列舉成一張表：
上次余數（From State）
遇到數字（Input Char）
輸出余數（To State）
0
0、3、6、9
0
1、4、7
1
2、5、8
2
1
0、3、6、9
1
1、4、7
2
2、5、8
0
2
0、3、6、9
2
1、4、7
0
2、5、8
1
教科書都喜歡畫DFA流程圖，我也用GraphViz將就畫個（這么亂的圖真能幫助理解嗎）：
接下來其實就可以動手寫程序自動生成這張表了：
/**自動構造接受N的倍數的DFA@return { fromState => { Char => toState } }*/function buildDFA(N) {  var map={},i,j,to;  // i 為 From State  for (i=0;i<N;i++) //FromState不會超過N，因為余數肯定小于N嘛    for (j=0;j<10;j++) { // j 為枚舉Input Digit Char      //當上次余i這次碰到j時，除N的余數即為輸出狀態      to=(i*10+j) % N;      (map[i]=map[i]||{})[j]=to;    }  return map;}
這代碼也太簡單了，用javaScript寫的好處就是現在按下F12將代碼貼進去運行下就能看到結果了?？缮蛇@張表有什么用呢？再寫個執行DFA的函數就大功告成了：
/**運行DFA@param {DFA}    a 就是buildDFA返回的表@param {String} s 輸入數字串@return 如果輸入匹配則返回true*/function runDFA(a,s) {  for (var i=0,from=0,l=s.length;i<l;i++) {    from=a[from][s[i]];//獲取到下一個狀態    if (from===undefined) return false;  }  return from===0;//最后余0則OK}//測試是否是3的倍數runDFA(buildDFA(3), ""+4614);
至此已經做到了生成及執行匹配任意整數倍數的DFA，注意是任意位數的N及其倍數哦。接下來的工作就是將自動機轉換成正則表達式。有很多種算法，這里只介紹最易于理解的解方程法。
Arden's Lemma
這種方法就是將自動機中的狀態變換看成方程組，然后用解方程的方式化簡自動機，逐步消減狀態，最后合并成一個正則式。該方法基于Arden's Lemma：
L = UL ∪ V ? L = U ? V
看上去好抽象，其實只是Minify過了而已。其中的道理很簡單，先看下面的DFA如何轉換成正則式：
  a0 => 0
  b0 => 1
其中0、1為狀態，a、b表示Char，0為起始狀態，1為接受狀態。這個只包含兩條變換的自動機對應于正則式：a*b，這就是Arden's Lemma表達的意思。單這一條引理其實還不夠，我們還需要了解正則式其它幾個基礎性質。我們把這正則式整體當成一個自動機的話，它就是0 => 1這樣一個變換。 正則式的串聯，比如a*bc*d，對應于自動機的串聯：
  a0 => 0
  b0 => 1
  c1 => 1
  d1 => 2
其中2為接受狀態。那么兩個正則式的串聯，則可以看成將整體串聯成 0 => 1 => 2得到0 => 2。 依此類推，正則式的并聯，如(a|b)c，對應于自動機的并聯：
  a0 => 1
  c1 => 2
  b0 => 1
好了，其實正則表達式與自動機相互轉換的方法就這些。應用到前面的Triple DFA，比如0 => 0的變換有四條，所以正則式為(0|3|6|9)*，當然更簡單的寫法是[0369]*，前面buildDFA函數生成的表雖易于執行，但卻不便于轉換到正則式，所以寫一個直接輸出如下格式的函數更方便：
{  "0":{    "0":"[0369]",    "1":"[147]",    "2":"[258]",  }}
改寫后的buildTable函數（其中reflect表后面再解釋）：
function buildTable(n) {  var map={},reflect={},i,j,to,path;  for (i=0;i<n;i++) {    path=map[i]={};    for (j=0;j<10;j++) {      to=(i*10+j) % n;      path[to]=path[to] || '';      path[to]+=j;      if (to>i)        (reflect[to]=reflect[to] || {})[i]=1;    }    for (to in path)      if (path[to].length>1)        path[to]='['+path[to]+']';  }  for (to in reflect)    reflect[to]=Object.keys(reflect[to]);  return {map:map,reflect:reflect};}
我們的目標是轉換成的正則式只匹配除3余0的數，最終生成的正則式只能是一個0 => 0的變換，這樣才能保證成功匹配時的結束狀態一定是0。所以只需要把所有可能的0 => …… => 0不重復的變換路徑進行并聯，就能得到最終的正則式。 比如將0 => 1 => 0和0 => 0并聯得到正則式：([0369]|[147][258])*，依此類推。應用前面的Arden's Lemma及其它幾條方法，將所有的變換都化簡成一條0 => 0變換，這個過程就像在解一個方程，將不可接受狀態當成未知量化解成用0這個可接受狀態表示。例如對于TripleDFA，約去狀態2的步驟如下所示：
Origin
應用Arden's Lemma
{  "2": {    "0": "[147]",    "1": "[258]",    "2": "[0369]"  }}
{  "2": {    "0": "[0369]*[147]",    "1": "[0369]*[258]"  }}
然后再將狀態1輸出中的狀態2替換掉，其它依此類推：
Origin
{ "1": {    "0": "[258]",    "1": "[0369]",    "2": "[147]"  }}
1 => 2 => X串聯
{  "1": {    "0": "[258]",    "1": "[0369]",    "0": "[147][0369]*[147]",    "1": "[147][0369]*[258]"  }}
1 => X并聯
{  "1": {    "0": "[258]|[147][0369]*[147]",    "1": "[0369]|[147][0369]*[258]"  }}
前面buildTable中的reflect表就是用于反查哪些狀態可以到達當前要約去的狀態，以便將其替換掉。
在化簡過程中，無非對正則式進行串聯、并聯、重復這三種操作，相應的處理函數如下：
// seq(["[147]","[258]"]) => "[147][258]"function seq(a) {  return {    type:'seq',    toString:function () {      var re=a.join("");      if (this.repeat)        re=a.length>1?'('+re+')*':re+'*';      return re;    }  };}// choice(["[147]","[258]"]) => "[147]|[258]"function choice(a) {  var items=[];  //這一步其實只是為了使生成的正則式更短一些  //按并聯的結合性，"a|(b|c)" 等同于 "a|b|c"  a.forEach(function (re) {    if (re.type==='choice')      items=items.concat(re.items);    else if (re)      items.push(re);  });  return {    type:'choice', items:items,    toString:function () {      var re=items.join("|");      if (items.length>1 || this.repeat) re='('+re+')';      if (this.repeat) re+='*';      return re;    }  };}// 將一個正則式標志為重復function repeat(re) {  if (typeof re==='string') return re+'*';  re.repeat=true;  return re;}
除去拼接正則式的代碼，最終的函數也不算長：
function buildRegex(n) {  var table=buildTable(n),i=n,j,k,to,path;  var map=table.map,reflect=table.reflect;  while (--i) {    var trans=map[i],t={},        prefix=trans[i]?repeat(trans[i]):'';    for (to in trans)      if (to<i) t[to]=trans[to];    trans=t;    if (prefix) for (to in trans)      trans[to]=seq([prefix,trans[to]]);    var entrances=reflect[i];    for (j=entrances.length;j--;) {      var from=entrances[j];      path=map[from];      prefix=path[i];      for (to in trans)        path[to]=choice([path[to] || '',seq([prefix,trans[to]])]);    }  }  return '^'+repeat(map[0][0])+'$';}
執行buildRegex(3)生成的正則表達式如下，Regex Golf評分 523 Points：
^([0369]|[258][0369]*[147]|([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147]))*$
這個函數生成出的匹配7的倍數的正則式有近16K，雖然說它能生成匹配任意位整數倍數的正則式，但這并不現實，因為它生成的正則式體積呈指數級增漲，生成20以上的正則式內存就不夠用了。而這么長的正則式讓JS的正則引擎去解析的話，大約15以上就會報錯。如果去執行匹配測試的話，大于13就有可能返回 False，這是因為執行時間過長，正則引擎就會放棄執行。優化當然還是可以做的，比如生成的正則式輸出時使用非捕獲分組如(:?[147])，執行速度則可以提升好幾倍。
我知道很多人會說用正則式匹配3的倍數效率太低了，有什么必要呢？我當然知道沒人真的會這么用正則式，但這道理還是需要講明白的。姑且不談使用atoi的方法即使在64位機上也只能處理長度不超過二十位的數字，試問這個正則表達式真的很慢嗎？這可不一定。正則引擎其實還是將正則式轉換成DFA或NFA執行的，如果是編譯到DFA，雖然編譯會花費些時間和內存，但執行速度只慢在額外的內存讀取，DFA復雜度和atoi函數一樣都是Θ(n)，即使慢也只是常數倍。如果直接執行原始DFA，理論上可以和atoi函數一樣快，這道理是明擺著的。 你不信的話，用下面的C++程序測試看，即使re2也只不過慢了5倍而已：
#include <stdio.h>#include <time.h>#include <stdlib.h>#include <re2/re2.h>#define LOOP_TIMES 10000000int main() {  int dfa[3][10]={    0,1,2,0,1,2,0,1,2,0,    1,2,0,1,2,0,1,2,0,1,    2,0,1,2,0,1,2,0,1,2};  clock_t start;int i;  const char* num="2147483646";  i=LOOP_TIMES;  start=clock();  while (i--) {    const char* str=num;    int from=0;    while( *str ) {      from=dfa[from][(*str++ - '0')];    }    int isTriple=from==0;  }  printf(" DFA:%d/n",clock()-start);  i=LOOP_TIMES;  start=clock();  while (i--) {    unsigned int val = atoi(num);    int isTriple = (val % 3)==0;  }  printf("atoi:%d/n",clock()-start);  RE2::Options opt(RE2::Latin1);  opt.set_never_capture(true);  RE2 re("(?:[0369]|[258][0369]*[147]|"  "(?:[147]|[258][0369]*[258])"  "(?:[0369]|[147][0369]*[258])*"  "(?:[258]|[147][0369]*[147]))*",opt);  i=LOOP_TIMES;  start=clock();  while (i--) {    int isTriple =RE2::FullMatch(num, re);  }  printf(" re2:%d/n",clock()-start);}
如果你仍然覺得正則表達式肯定很慢的話，那看下面的Javascript測試程序：
var LOOP_TIMES=10000000;var re=/^(?:[0369]|[258][0369]*[147]|(?:[147]|[258][0369]*[258])(?:[0369]|[147][0369]*[258])*(?:[258]|[147][0369]*[147]))*$/;var s="31457283145728",    i,isTriple,start;start=+new Date;i=LOOP_TIMES;while (i--) isTriple=re.test(s);console.log("  RegExp:",(+new Date)-start);start=+new Date;i=LOOP_TIMES;while (i--) isTriple=parseInt(s)%3 === 0;console.log("parseInt:",(+new Date)-start);
運行結果顯示parseInt方式更慢！為什么？呵呵，因為JS中 Number 是雙精度64位浮點數，如果將上面C++程序中atoi改成atof、使用fmod取余的話，運行結果顯示取余比正則式只快了不到一倍！
好了，現在至少沒人再拿這正則表達式效率低說事了吧。