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

Объяснение

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

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)

Ноты вкуса

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

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

Java немного отличается тем, что _ 16_, _ 17_ и _ 18_ пытается сопоставить шаблон с целым строка ввода. Вот почему якоря можно не указывать в приведенном выше фрагменте.

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

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

Связанные вопросы

• (Java) методы не работают хорошо - с примерами того, как сделать префикс / суффикс / infix соответствие
• Является есть аромат регулярного выражения, который позволяет мне подсчитывать количество повторений, соответствующих * и + (.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|^.)*.$}