18

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

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|^.) )* ..匹配斐波那契数字？

4

2 回答 2

16 
(?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)，第二个是因为斐波那契数列的第二恒等式表明斐波那契数列的总和是斐波那契数减一。(1)

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

  11. 遍历替换，您可以看到它将如何继续添加斐波那契数，直到填充字符串。第一次迭代匹配^.，所以 1。第二次迭代将前一个部分匹配与 匹配，\2以及整个前一个匹配与 匹配\1。这为第二次迭代提供了两个。第三次迭代从第二次迭代 (1) 以及整个第二次迭代 (2) 中获取匹配的第二部分。这为第三次迭代生成了三个。将迭代加在一起，您就有了 fib 数的总和。

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

于 2013-09-04T23:47:42.980 回答
0

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

首先要注意的是正则表达式对整数使用一元。因此String s = new String(new char[n]);，在 Java 代码中，会将整数n转换为包含许多 ( '\0') 个字符的字符串。这个字符串包含哪个字符并不重要，重要的是一元的长度。（例如，Java 11+ 中的替代方案可能是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
于 2020-05-15T08:19:17.477 回答