使用正则表达式查找斐波纳契数

Question

我在这篇博客文章中找到了以下代码示例:

final String FIBONACCI = 
   "(?x) .? | ( \\2?+ (\\1|^.) )* ..";

for (int n = 0; n < 10000; n++) {
   String s = new String(new char[n]);
   if (s.matches(FIBONACCI)) {
      System.out.printf("%s ", n);
   }
}

输出: 0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 ...

如何(?x) .? | ( \\2?+ (\\1|^.) )* ..符合斐波那契数？

Answer 1

(?x) .? | ( \\2?+ (\\1|^.) )* ..

这里有很多事情可能会混淆.我将详细介绍这些内容,以解释算法的工作原理.

1. 匹配是在正则表达式长度的字符串上完成的,而不是实际的数字.字符串中唯一真实的数据是它的长度.

2. \\双反斜杠只是因为在Java字符串文字中反斜杠必须反斜杠,这样很明显你没有逃避其他东西.我将不会在此答案的任何未来代码中显示它们.

3. (?x):这可以启用扩展的正则表达式模式.在此模式下,将忽略未反斜杠或在字符类中的空格,从而允许将正则表达式拆分为具有嵌入式注释的更易读的部分.[sarand.com].

4. .?:这将匹配0或1个字符串.此匹配仅用于f(0),f(1)和f(2)情况,否则将被丢弃.

5. |:这意味着如果第一次尝试匹配1或2个字符不起作用,那么尝试匹配右侧的所有内容.

6. (:这将打开第一个组(\1稍后引用).

7. (\2?+这+使得?占有量量化.在这种情况下,结果是,如果定义?了\2反向引用,则该方法使用反向引用,并且+如果正则表达式不起作用,则均值不返回并尝试不使用它.

8. (\1|^.):这将匹配到目前为止匹配的所有内容或单个字符.这当然意味着第一个"到目前为止匹配的所有东西"是一个单一的角色.由于这是第二个正则表达式,它也是新的\2

9. )*:这将重复算法.每次它重复它会定义新的价值\1和\2.对于当前迭代,这些值将等于F(n-1)和F(n-2),其将是F(n).每次迭代都将添加到前一次,这意味着您有一个F(n)0到n的和.尝试通过头脑运行算法获取一些较小的数字来获得想法.

10. ..:需要一个点来匹配未包括在总和中的f(1),第二个是因为Fibonacci数的第二个同一性表明斐波那契数列的总和是斐波纳契数减1.(1)

    

11. 通过替换,你可以看到这将如何继续添加斐波那契数字,直到填充字符串.第一次迭代匹配^.,所以1.第二次迭代将前一次部分匹配与前一次匹配\2以及前一次匹配匹配\1.这使得第二次迭代有两次.第三次迭代从第二次迭代(1)以及整个第二次迭代(2)获取匹配的第二部分.这使得第三次迭代中有三次.将迭代添加到一起,您就得到了一些fib数.

请参阅为什么Java正则表达式引擎会在+重复上抛出StringIndexOutOfBoundsException？有关此重现实际有效的原因的更多信息.