正则表达式难题

这应该有效:

^(?:0|(?:(?:[369]|[147](?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\
+)*[369]0*)*\+?(?:0\+)*[258])*(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]|0*(?:
\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147])|[
258](?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0
\+)*[147])*(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]|0*(?:\+?(?:0\+)*[369]0*)
*\+?(?:0\+)*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]))0*)+)(?:\+(?:0|(?:(?
:[369]|[147](?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\+)*[369]0*)
*\+?(?:0\+)*[258])*(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]|0*(?:\+?(?:0\+)*
[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147])|[258](?:0*(?
:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147])*
(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]|0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)
*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]))0*)+))*$

它的工作原理是,有三种状态表示迄今为止模3的数字之和。它不允许数字的前导零、字符串开头和结尾的加号以及两个连续的加号。

正则表达式和测试台的生成:

a = r'0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*'
b = r'a[147]'
c = r'a[258]'

r1 = '[369]|[147](?:bc)*(?:c|bb)|[258](?:cb)*(?:b|cc)'
r2 = '(?:0|(?:(?:' + r1 + ')0*)+)'
r3 = '^' + r2 + r'(?:\+' + r2 + ')*$'
r = r3.replace('b', b).replace('c', c).replace('a', a)

print r

# Test on 10000 examples.

import random, re
random.seed(1)
r = re.compile(r)
for _ in range(10000):
    x = ''.join(random.choice('0123456789+') for j in range(random.randint(1,50)))
    if re.search(r'(?:\+|^)(?:\+|0[0-9])|\+$', x):
        valid = False
    else:
        valid = eval(x) % 3 == 0
    result = re.match(r, x) is not None
    if result != valid:
        print 'Failed for ' + x

请注意,我对dfa语法的记忆已经过时了,所以我的答案无疑有点支离破碎。希望这能给你一个大概的想法。我选择忽略 + 完全。正如amirw所说,abc+def和abc def在可分割性方面是相同的。

接受状态为C。

A=1,4,7,BB,AC,CA  
B=2,5,8,AA,BC,CB  
C=0,3,6,9,AB,BA,CC

请注意,上述语言使用了所有9种可能的ABC配对。它总是以a、b或c结尾,并且每个变量的使用都是成对的,这意味着每个处理迭代都将缩短变量串。

例子:

1490 = AACC = BCC = BC = B (Fail)  
1491 = AACA = BCA = BA = C  (Success)

不是完整的解决方案,只是一个想法:

(b)单独:“加号”在这里并不重要。 abc + def 是一样的 abcdef 为了能被3除尽。对于后一种情况,这里有一个regexp: http://blog.vkistudios.com/index.cfm/2008/12/30/Regular-Expression-to-determine-if-a-base-10-number-is-divisible-by-3

为了将此与需求(a)结合起来,我们可以采用(b)的解决方案并对其进行修改:

• 第一个读取字符必须在0到9之间(不是加号)

• 输入不能以加号结尾,因此:复制每个状态(将使用 S 对于原始状态和 S' 以便复制品区分它们)。如果我们在州里 S 我们读了一个加号,我们将转到 S’ .

• 当我们读到一个数字时,我们会进入新的状态 S . S’ 各州不能接受(另一个)加号。

• 也, S’ 不是“接受状态”,即使 S 是。(因为输入不能以加号结尾)。