自学编程难不难系列 之 正则(2) 
..
作者: 一了 <1liao3@funlang.org>
日期: 2016-05-08
上一篇(自学编程难不难系列 之 正则表达式)提到一个简单有用的正则表达式, 有人就问正则表达式要怎么学, 觉得好难哦.
实际上正则表达式蛮简单的, 就看你怎么学了. 本篇以一个例子来开始(注意: 行文有点罗嗦, 正则高手就不要看啦).
^(?:([0369]*+)|([147](?1))(([258](?1))|(?2)(?5))|(?4)((?2)|(?4)(?3)))+$
大家先看看上面这条式子, 有人知道是干什么的么? 这是个蛮无聊的正则表达式, 用来匹配3的倍数 ;-) 我们先不讨论3的倍数用正则来匹配有什么意义, 先就来学一下如何写出来吧.
一个数字是3的倍数, 有一些规律, 一个简单的规律就是所有位上的数字加起来之和也是3的倍数. 单个数字中, 0369直接就是3的倍数; 147模3余1, 258模3余2, 所以147与258配对之和也是3的倍数; 147或者258分别重复3次, 也必然是3的倍数. 有了这些规律, 就有了下面这幅图:
上面这幅图是有限状态自动机的状态图, 我们据此来写正则表达式, 要比传统的学法简单很多. 首先注意到图上有3种状态: A B C, 然后有多个状态转移的边, 概括起来有3种: 0369 147 258, 不过0369多次重复, 可以和初始(终止)状态重用. 下面我们一步步来写正则表达式:
第一步写 ([0369]*+) 表达式, 既可以用在初始终止状态, 也可以在其他状态的 0369 状态转移边中重用; 我们给它作为第一个组;
第二步写 ([147](?1)) 表达式, 这个是 147 转移边, 重用了第一步的 组1, 即 0369 自转移循环; 这个作为第二组;
接下来我们注意到从 B 状态出发有2种可能(0369 循环已经在第二步搞定了, 不用再考虑), 分别是 258 回 A 和 147 到 C, 所以这里预留一个组即第三组;
第三步写 ([258](?1)) 表达式, 这个是 258 转移边, 跟第二步类似, 不详述; 这个是 B 出发的第一种情况; 第四组;
第四步写 B 出发的第二种情况, 即 从 (?2) 第二组转移边即 147 到 C, C 我们暂定为第五组 (?5);
第五步写第五组, 即从 C 出发, 这个也分两种情况, 分别是:
(?2) 回到初始(终止)状态, 或者
(?4) 到 B 状态, 即我们预留的第三组 (?3)
完整的正则表达式还需要加上初始终止状态约束, 完整状态链的循环, 如下:
^(?:
([0369]*+) (?# 1)
|
([147](?1)) (?# 2)
( (?# 3)
([258](?1)) (?# 4)
|
(?2)(?5)
)
|
(?4)
( (?# 5)
(?2)
|
(?4)(?3)
)
)+$
去除空行和注释, 简化可得: ^(?:([0369]*+)|([147](?1))(([258](?1))|(?2)(?5))|(?4)((?2)|(?4)(?3)))+$
这个正则表达式可以正确的匹配所有3的倍数(当然这里没考虑全空或者全0字符串), 用以下代码测试:
var r3 = $`
^(?:
([0369]*+) (?# 1)
|
([147](?1)) (?# 2)
( (?# 3)
([258](?1)) (?# 4)
|
(?2)(?5)
)
|
(?4)
( (?# 5)
(?2)
|
(?4)(?3)
)
)+$
`x;
for i = 1 to 1000 do
var s = '';
var n = 0;
for j = 0.random() to 10000 + 100.random() do
var d = 10.random();
n += d;
s &= d;
end do; #?. s;
if r3.match(s) xor n mod 3 = 0 then
?. s;
end if;
end do; exit;
for i = 0 to 10000 step 1 do
var m = r3.match(i);
if m and i mod 3 <> 0 or not m and i mod 3 = 0 then
?, i;
end if;
end do;
这个代码是 Fun 语言代码, 需要下载安装 Fun 语言的运行环境: fun.zip (999KB). 下载之后解压, 运行 fun-install.bat 可以帮助建立 .fun 文件关联. 上述代码可以在 funide.exe 中输入调试运行(调试运行需要把第25行 for j = 0.random() to 10000 + 100.random() do 中的 10000 改成 1000, 否则容易堆栈溢出, funide 没做预防措施), 或者直接存为 .fun 运行.
上面测试代码运行结果应该为空, 即不输出任何东西方为正确. 在直接 .fun 运行时, 内存大约不超过 8M, 速度大约几秒.
可能有人会吐槽3的倍数的数字拿来模3不就立马出来了么, 这不是屠龙之技么. 实际上有可能碰上非常大的数字, 比如例中上万位十进制数字串, 电脑不容易处理. 当然也可以一位一位的累加然后判断, 不过要比正则麻烦, 说不定还不如正则快呢.
这个正则虽然无聊, 但总比拿来判断是否质数要有用那么一点点, 关键重要的是, 我们可以借此学习如何写出更好的正则表达式.
