正则表达式匹配N的倍数

来源：https://jex.im/programming/triple-regex.html

Regex Golf上有一道题名为 Triples，即要求用正则表达式匹配3的倍数，还有一道匹配7的倍数的练习题。这种问题如果人肉解决的话，相当于做一道包含几十个数的四则运算题，不管你怎么想，反正我小时候遇到五个数以上的四则运算题都是直接略过。小时候不好好学习，现在该怎么办呢？——现在我会写代码了啊。 解决方案其实很简单：写程序构造一个接受3的倍数的DFA，再将其转换成正则式即可。

Finite Automaton

术语听起来都好抽象，其实解决思路就像小学生做除法一样简单。比如我们如何判定4641是3的倍数？ 从左往右一个数一个数地计算，最后余0即可：

4641
4    % 3 => 1
16   % 3 => 1
 14  % 3 => 2
  21 % 3 => 0

一次读一个数字，然后输出一个余数，如果最后余0则表示OK。影响我们判断的有两个因素：上次运算结果的余数，当前读入的字符。自动机就是这样一种机器，开始处于一个状态，每次读入一个字符，然后输出一个新状态。所以上面的运算可以用下面的自动机执行过程表示，起始状态为0，余数即为输出状态：

  4
0 => 1

用人话来讲就是：上次余数为0时，遇到4则余1；上次余1时遇到6则还余1；……
数字只有10个，所以我们可以穷举，除3余数只有0、1、2三种可能，当余数为任意一个时，下一次遇到的数字只有10种可能， 全部情况列举成一张表：

教科书都喜欢画DFA流程图，我也用GraphViz将就画个（这么乱的图真能帮助理解吗）：

接下来其实就可以动手写程序自动生成这张表了：

/**
自动构造接受N的倍数的DFA
@return { fromState => { Char => toState } }
*/
function buildDFA(N) {
  var map={},i,208)">jto;
  // i 为 From State
  for i=0;<++) //FromState不会超过N，因为余数肯定小于N嘛
    j<10{ // j 为枚举Input Digit Char
      //当上次余i这次碰到j时，除N的余数即为输出状态
      to*10+) % ;
      map[]=||{})[;
    }
  return ;
}

这代码也太简单了，用JavaScript写的好处就是现在按下F12将代码贴进去运行下就能看到结果了。可生成这张表有什么用呢？再写个执行DFA的函数就大功告成了：

至此已经做到了生成及执行匹配任意整数倍数的DFA，注意是任意位数的N及其倍数哦。接下来的工作就是将自动机转换成正则表达式。有很多种算法，这里只介绍最易于理解的解方程法。

Arden's Lemma

这种方法就是将自动机中的状态变换看成方程组，然后用解方程的方式化简自动机，逐步消减状态，最后合并成一个正则式。该方法基于Arden's Lemma：

看上去好抽象，其实只是Minify过了而已。其中的道理很简单，先看下面的DFA如何转换成正则式：

其中0、1为状态，a、b表示Char，0为起始状态，1为接受状态。这个只包含两条变换的自动机对应于正则式：a*b，这就是Arden's Lemma表达的意思。单这一条引理其实还不够，我们还需要了解正则式其它几个基础性质。我们把这正则式整体当成一个自动机的话，它就是0 => 1这样一个变换。 正则式的串联，比如a*bc*d，对应于自动机的串联：

其中2为接受状态。那么两个正则式的串联，则可以看成将整体串联成0 => 1 => 2得到0 => 2。 依此类推，正则式的并联，如(a|b)c，对应于自动机的并联：

: {
    : "[0369]"
  }

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

LOOP_TIMES10000000;
=/^(?:[0369]|[258][0369]*[147]|(?:[147]|[258][0369]*[258])(?:[0369]|[147][0369]*[258])*(?:[258]|[147][0369]*[147]))*$/s="31457283145728"isTriple;
=+new Date;
test);
consolelog"  RegExp:"+-);

parseInt%3 === "parseInt:");