Поиск чисел Фибоначчи с использованием регулярных выражений

Я нашел следующий пример кода на этом сообщении в блоге:

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

Здесь происходит много вещей, которые могут смутить. Я рассмотрю каждую из этих вещей, чтобы объяснить, почему работает алгоритм.

  • Совпадение выполняется с строкой с длиной регулярного выражения, а не с фактическим числом. Единственными реальными данными в строке являются ее длина.

  • \\ Двойная обратная косая черта только потому, что в строковых литералах Java обратная косая черта должна быть обратной, чтобы было ясно, что вы не избегаете чего-то другого. Я не буду показывать их в любом будущем коде в этом ответе.

  • (?x): Это позволяет расширенный режим регулярного выражения. В этом режиме пробелы, которые не являются обратными или внутри символьного класса, игнорируются, позволяя регулярному выражению разбиваться на более читаемые части со встроенными комментариями. [sarand.com].

  • .?: Это будет соответствовать 0 или 1 символьным строкам. Это совпадение используется только для случаев f (0), f (1) и f (2), в противном случае оно будет отброшено.

  • |: Это означает, что если первая попытка сопоставить 1 или два символа не сработала, попробуйте сопоставить все, что находится справа от нее.

  • (: Это открывает первую группу (позже упоминается \1).

  • (\2?+ + делает ? притяжательным квантором. В этом случае результат ? означает использование обратной ссылки \2, если оно определено, а средство + не возвращается и не пытается его использовать, если регулярное выражение не работает с ним.

  • (\1|^.): Это будет соответствовать либо всем, что было согласовано до сих пор, либо одному символу. Это, конечно, означает, что первое "все, что соответствует до сих пор" - это один символ. Поскольку это второе регулярное выражение, это также новый \2

  • )*: Это повторит алгоритм. Каждый раз, когда он повторяется, он будет определять новые значения для \1 и \2. Эти значения будут равны F (n-1) и F (n-2) для текущей итерации, которая будет F (n). Каждая итерация будет добавлена ​​к предыдущей, что означает, что у вас есть сумма F (n) от 0 до n. Попробуйте запустить алгоритм через голову для получения меньших чисел, чтобы получить эту идею.

  • ..: одна точка должна соответствовать f (1), которая не включена в сумму, вторая - потому, что Вторая идентичность чисел Фибоначчи утверждает, что сумма последовательности чисел фибоначчи является числом финнакси минус единица. (1)

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

  • Пройдя через замены, вы увидите, как это будет продолжать добавлять числа Фибоначчи до заполнения строки. Первая итерация соответствует ^., поэтому 1. Вторая итерация соответствует предыдущему частичному совпадению с \2, а также всему предыдущему совпадению с \1. Это делает два для второй итерации. Третья итерация занимает эту вторую часть матча со второй итерации (1), а также всю вторую итерацию (2). Это делает три для третьей итерации. Добавьте итерации вместе, и у вас есть сумма чисел fib.

Посмотрите Почему механизм регулярных выражений Java выкидывает StringIndexOutOfBoundsException на + повторение? для получения дополнительной информации о том, почему это повторение действительно работает.