Как это регулярное выражение находит треугольные числа?

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

Первые несколько треугольных чисел:

 1 = 1
 3 = 1 + 2
 6 = 1 + 2 + 3
10 = 1 + 2 + 3 + 4
15 = 1 + 2 + 3 + 4 + 5

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

  • Учитывая n, мы сначала создаем строку длиной n, заполненную тем же символом
  • Затем мы сопоставляем эту строку с шаблоном ^(\1.|^.)+$
    • n является треугольным тогда и только тогда, когда этот шаблон соответствует строке

Вот несколько фрагментов, показывающих, что это работает на нескольких языках:

PHP (на ideone.com)

$r = '/^(\1.|^.)+$/';

foreach (range(0,50) as $n) {
  if (preg_match($r, str_repeat('o', $n))) {
     print("$n ");
  }
}

Java (на ideone.com)

for (int n = 0; n <= 50; n++) {
    String s = new String(new char[n]);
    if (s.matches("(\\1.|^.)+")) {
        System.out.print(n + " ");
    }
}

C# (на ideone.com)

Regex r = new Regex(@"^(\1.|^.)+$");

for (int n = 0; n <= 50; n++) {
    if (r.IsMatch("".PadLeft(n))) {
       Console.Write("{0} ", n);
    }
}

Так что это регулярное выражение работает, но может кто-нибудь объяснить, как?

Похожие вопросы

Источник

1 ответ

Решение

объяснение

Вот схематическая разбивка шаблона:

from beginning…
|         …to end
|         |
^(\1.|^.)+$
 \______/|___match
  group 1    one-or-more times

(…) скобки определяют группу захвата 1, и эта группа неоднократно сопоставляется с +, Этот подшаблон привязан с ^ а также $ чтобы увидеть, может ли он соответствовать всей строке.

Группа 1 пытается соответствовать this|that чередует:

  • \1. то есть, какой группе 1 соответствует (самостоятельная ссылка!) плюс один из "любых" символов,
  • или же ^. то есть просто "любой" один символ в начале

Обратите внимание, что в группе 1 у нас есть ссылка на то, что соответствует группе 1! Это вложенная / самостоятельная ссылка, и это основная идея, представленная в этом примере. Имейте в виду, что когда группа захвата повторяется, как правило, она сохраняет только последний захват, поэтому в этом случае ссылка на себя по существу говорит:

"Попытайтесь соответствовать тому, что я соответствовал в прошлый раз, плюс еще один. Это то, что я буду соответствовать на этот раз".

Подобно рекурсии, должен быть "базовый случай" с собственными ссылками. На первой итерации + группа 1 еще ничего не зафиксировала (это НЕ то же самое, что сказать, что она начинается с пустой строки). Следовательно, второе чередование вводится как способ "инициализации" группы 1, то есть разрешается захватывать один символ, когда он находится в начале строки.

Так как это повторяется с + группа 1 сначала пытается сопоставить 1 символ, затем 2, затем 3, затем 4 и т. д. Сумма этих чисел представляет собой треугольное число.

Дальнейшие исследования

Обратите внимание, что для упрощения мы использовали строки, состоящие из того же повторяющегося символа, что и входные данные. Теперь, когда мы знаем, как работает этот шаблон, мы можем видеть, что этот шаблон может также соответствовать строкам, таким как "1121231234", "aababc", так далее.

Также обратите внимание, что если мы обнаружим, что n является треугольным числом, то есть n = 1 + 2 +… + k, длина строки, захваченной группой 1 в конце, будет k.

Обе эти точки показаны в следующем фрагменте кода C# ( также можно увидеть на ideone.com):

Regex r = new Regex(@"^(\1.|^.)+$");

Console.WriteLine(r.IsMatch("aababc"));     // True
Console.WriteLine(r.IsMatch("1121231234")); // True
Console.WriteLine(r.IsMatch("iLoveRegEx")); // False

for (int n = 0; n <= 50; n++) {
    Match m = r.Match("".PadLeft(n));
    if (m.Success) {
       Console.WriteLine("{0} = sum(1..{1})", n, m.Groups[1].Length);
    }
}
// 1 = sum(1..1)
// 3 = sum(1..2)
// 6 = sum(1..3)
// 10 = sum(1..4)
// 15 = sum(1..5)
// 21 = sum(1..6)
// 28 = sum(1..7)
// 36 = sum(1..8)
// 45 = sum(1..9)

Вкусовые ноты

Не все версии поддерживают вложенные ссылки. Всегда ознакомьтесь с особенностями аромата, с которым вы работаете (и, следовательно, почти всегда помогает предоставлять эту информацию всякий раз, когда вы задаете вопросы, связанные с регулярными выражениями).

В большинстве разновидностей стандартный механизм сопоставления регулярных выражений пытается увидеть, может ли шаблон соответствовать какой-либо части входной строки (возможно, но не обязательно, всему вводу). Это означает, что вы должны помнить, чтобы всегда привязывать свой шаблон с ^ а также $ когда необходимо.

Ява немного отличается в этом String.matches, Pattern.matches а также Matcher.matches попытаться сопоставить шаблон со всей входной строкой. Вот почему якоря могут быть опущены в приведенном выше фрагменте.

Обратите внимание, что в других случаях вам может понадобиться \A а также \Z якоря вместо. Например, в многострочном режиме, ^ а также $ сопоставьте начало и конец каждой строки на входе.

И последнее: в регулярном выражении.NET вы МОЖЕТЕ получить все промежуточные записи, сделанные группой повторных захватов. В большинстве ароматов вы не можете: все промежуточные захваты потеряны, и вы можете сохранить только последний.

Смежные вопросы

Бонусный материал: используя регулярные выражения, чтобы найти силу двойки!!!

С очень незначительной модификацией вы можете использовать те же методы, которые представлены здесь, чтобы найти силу двойок.

Вот основное математическое свойство, которым вы хотите воспользоваться:

  • 1 = 1
  • 2 = (1) + 1
  • 4 = (1 + 2) + 1
  • 8 = (1 + 2 + 4) + 1
  • 16 = (1 + 2 + 4 + 8) + 1
  • 32 = (1 + 2 + 4 + 8 + 16) + 1

Решение приведено ниже (но попробуйте сначала решить его самостоятельно!!!!)

(см. на ideone.com в PHP, Java и C#):

^(\1\1|^.)*.$

Источник
Другие вопросы по тегам