活用regex的例子 zz.

在reddit推荐的文章上看到的。下面的代码在CMD窗口下运行通过。如果在BASH下面运行,单引号和双引号要对调。

perl -wle "print 'prime' if (1 x shift) !~ /^1?$|^(11+?)\1+$/" <任意一个数>

Python的代码是:

import re
def is_prime(num):
    
return not re.match(r"^1?$|^(11+?)\1+$""1" * num)

Ruby有Perl的血脉,所以代码和Perl版本几乎一样(其实无所谓,反正关键都是同样一段regex):

ruby -"puts 'prime' if ('1' * ARGV.shift.to_i) !~ /^1?$|^(11+?)\1+$/" <任意一个数>

判断方法很有意思。把给出的数用一进制表示。比如5就是11111。然后从2开始一个数一个数地看这段表示中1的数目是否是其中任意一个的数的倍 数。比如说当给出的数是4,则对应的表示是1111。那么1111匹配^11\1,也就是说它匹配^(11+?)\1+$。那么它是2的倍数。所以4不是 质数。而当给出的数是7时,对应的表示是1111111。那这葛字符串不能匹配11\1+,也不能匹配111\1+,...,也不能匹配1111111 \1+,所以7是质数。

解释一下regex的构造:
^1?$,匹配空的字串或者"1"。换句话说,0和1不是质数。

(11+?)\1+,(11+?)匹配长度为2或者2以上且形如"11.....111"的字串。注意那个问号,说明匹配点到即止,不是贪婪匹配。 这点很重要,不然(11+)可以匹配所有长度大于2且形如"11...1"的字串。回溯参考符\1表示匹配之前匹配到的字串,也就是(11+?)了。点睛 之笔来了:\1+表示匹配一到多个之前匹配到的(11+?)。换句话说,匹配长度为N*M的字串,这里N大于0,而M就是(11+?)匹配上的长度。因为 Perl的regex自动回溯,所以(11), (111), (1111)...都会被自动尝试。

这段代码除了漂亮精巧值得欣赏,以及可以用来玩味理解regex以 外,还有什么价值呢?效率?显然不够高。实用性?恐怕也没有多少。不过,这段代码隐含了重要的编程思想:编码。我们可以把一段问题用某种方式表达出来,再 根据这段表达谋求解决之道。这种方法看似简单,却应用广泛。我们可以把各式自动机用字符串表示出来,由此相对容易地发现很多深刻的性质。我们把系统规格用 状态机描述出来,再把状态机用逻辑公式表达出来,于是我们可以自动验证系统规格有没有逻辑上的缺陷,有没有安全问题。进一步说,我们赖以为生的整个计算体 系也是建立编码的基础上:所有的数据所有的命令最终被转换为01表示。计算理论基础更离不开编码。从歌德尔定理到图灵机理论到自动机理论到计算复杂性,不知多少伟大的证明依靠编码。

还有一点好玩儿的。Perlregex匹配是NP-Complete的问题。这里有证明。数独(sudoku)也是NP-Complete问题。所以我们可以通过写出regex表达式来解决数独猜谜。关键还是把数独的题面转化成可以匹配的字串。牛人Abigail给出了一个方案Abigail也是上面判断质数代码的作者。呵呵,其实我们也可以把regex配备问题转换成数独问题,然后用数独程序来实现匹配。哪位闲得不行的老大可以去试试。

http://blog.csdn.net/g9yuayon/archive/2007/03/19/1533798.aspx

 

Powered by Jekyll and Theme by solid

本站总访问量