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

2022-09-02 22:05:23

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

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|^.) )* ..


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

这里发生了很多事情,可能会让人感到困惑。我将逐一介绍这些事情,以解释为什么算法有效。

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

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

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

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

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

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

  7. (\2?+使 成为所有格量词。在这种情况下,结果是,如果定义了反向引用,则均值使用反向引用,并且如果正则表达式不使用它,则均值不会返回并尝试不使用它。+??\2+

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

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

  10. ..:需要一个点来匹配未包含在总和中的f(1),第二个点是因为斐波那契数列的第二恒等式表明斐波那契数列的总和是斐波那契数列减去一。(1)

    http://i.stack.imgur.com/SaRUR.png

  11. 浏览替换,您可以看到这将如何继续添加斐波那契数列,直到填充字符串。第一次迭代与 匹配,因此 1.第二次迭代将前一个部分匹配与 匹配,以及上一个与 .这使得第二次迭代有两个。第三次迭代从第二次迭代 (1) 以及整个第二次迭代 (2) 中获取匹配的第二部分。这使得第三次迭代有三个。将迭代相加,您将获得fib数的总和。^.\2\1

请参阅为什么 Java 正则表达式引擎会在 + 重复时抛出 StringIndexOutOfBoundsException?,以获取有关为什么这种递归实际上有效的更多信息。


答案 2

我知道它已经在另一个答案中详细解释了(包括对一般使用的正则表达式的更好解释),但是我最近遇到了这个正则表达式而没有解释,所以我自己添加了一些评论。我想我也会在这里分享它,让其他人看到。

首先要注意的是,正则表达式使用一元数作为整数。因此,在Java代码中,将整数转换为包含许多()字符的字符串。此字符串包含哪个字符并不重要,重要的是长度对于一元数。(例如,Java 11+ 中的替代方案可能是 ,并且它仍然可以按预期工作。String s = new String(new char[n]);n'\0'String s = "x".repeat(n);

至于正则表达式本身:

"(?x) .? | ( \\2?+ (\\1|^.) )* .." # Since this is a Java-String, where the `\` are escaped
                                   # as `\\` and `String#matches` also implicitly adds a 
                                   # leading/trailing `^...$` to regex-match the entire
^(?x) .? | ( \2?+  (\1 |^.) )* ..$ # String, the actual regex will be this:
                                   # The `(?x)` is used to enable comments and whitespaces,
                                   # so let's ignore those for now:
^.?|(\2?+(\1|^.))*..$
    (           )*                 # First capture group repeated 0 or more times.
                                   # On each iteration it matches one Fibonacci number.
            |^.                    # In the first iteration, we simply match 1 as base case.
                                   # Afterwards, the ^ can no longer match, so the
                                   # alternative is used.
     \2?+                          # If possible, match group 2. This ends up being the
                                   # Fibonacci number before the last. The reason we need
                                   # to make his optional is that this group isn't defined
                                   # yet in the second iteration. The reason we have the `+`
                                   # is to prevent backtracking: if group 2 exists, we
                                   # *have* to include it in the match, otherwise we would
                                   # allow smaller increments.  
         (\1|  )                   # Finally, match the previous Fibonacci number and store
                                   # it in group 2 so that it becomes the second-to-last
                                   # Fibonacci number in the next iteration.

                                   # This in total ends up adding Fibonacci numbers starting
                                   # at 1 (i.e. 1,2,3,5,8,... will add up to 3,6,11,19,...
                  ..               # They are all two less than the Fibonacci numbers, so
                                   # we add 2 at the end.

                                   # Now it's only missing the 0 and 1 of the Fibonacci
 .?|                               # numbers, so we'll account for those separately