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

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

41 голосов
/ 02 сентября 2010

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

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

 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 Ответ

36 голосов
/ 02 сентября 2010

Объяснение

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

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

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

Группа 1 пытается сопоставить this|that альтернатив :

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

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

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

Подобно рекурсии, должен быть «базовый случай» с собственными ссылками. На первой итерации + группа 1 еще ничего не захватила (что означает NOT , что говорит о том, что она начинается с пустой строки). Следовательно, второе чередование вводится как способ «инициализации» группы 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)

Ароматические ноты

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

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

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

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

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

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

Бонусный материал: с помощью регулярных выражений найдите силу двойок !!!

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

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

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

...