Можно ли сопоставить вложенные скобки с регулярным выражением без использования рекурсии или балансировки?

Stackru поощряет вопросы с автоответчиком, поэтому я решил создать этот пост, чтобы поделиться тем, что я недавно обнаружил.

Проблема: сопоставить произвольно вложенную группу скобок в разновидности регулярных выражений, такой как Java java.util.regex, которая не поддерживает ни рекурсию, ни балансировочные группы. То есть, сопоставьте 3 внешние группы в:

(Первый второй третий)))))))

Это упражнение носит чисто академический характер, поскольку все мы знаем, что регулярные выражения не должны использоваться для соответствия этим вещам, так же как Q-подсказки не должны использоваться для чистки ушей.

Источник

2 ответа

Решение

В самом деле! Это возможно, используя прямые ссылки:

(?=\()(?:(?=.*?\((?!.*?\1)(.*\)(?!.*\2).*))(?=.*?\)(?!.*?\2)(.*)).)+?.*?(?=\1)[^(]*(?=\2$)

доказательство

Et Voila; вот оно Это прямо там соответствует полной группе вложенных скобок от начала до конца. Две подстроки на совпадение обязательно фиксируются и сохраняются; это бесполезно для вас. Просто сфокусируйтесь на результатах основного матча.

Нет, нет ограничений по глубине. Нет, там нет скрытых конструкций. Просто старые взгляды, со всплеском прямой ссылки. Если ваш аромат не поддерживает прямые ссылки (я смотрю на вас, JavaScript), то извините. Я действительно. Хотел бы я помочь тебе, но я не чудак.

Это здорово и все такое, но я тоже хочу соответствовать внутренним группам!

Хорошо, вот сделка Причина, по которой мы смогли сопоставить эти внешние группы, заключается в том, что они не перекрываются. Как только матчи, которые мы желаем, начинают перекрываться, мы должны несколько изменить нашу стратегию. Мы все еще можем исследовать предмет для правильно сбалансированных групп скобок. Однако вместо того, чтобы напрямую сопоставлять их, нам нужно сохранить их с группой захвата, например:

(?=\()(?=((?:(?=.*?\((?!.*?\2)(.*\)(?!.*\3).*))(?=.*?\)(?!.*?\3)(.*)).)+?.*?(?=\2)[^(]*(?=\3$)))

Точно так же, как и в предыдущем выражении, за исключением того, что я обернул большую часть его в просмотр, чтобы избежать потребления символов, добавил группу захвата и настроил индексы обратных ссылок, чтобы они хорошо играли со своим новым другом. Теперь выражение совпадает в позиции непосредственно перед следующей группой в скобках, и интересующая подстрока сохраняется как \1.

Итак... как, черт возьми, это на самом деле работает?

Я рад, что ты спросил. Общий метод довольно прост: перебирайте символы по одному за раз, одновременно сопоставляя следующие вхождения '(' и ')', захватывая оставшуюся часть строки в каждом случае, чтобы установить позиции, с которых можно продолжить поиск в Следующая итерация. Позвольте мне разбить его по частям:

разбивка регулярных выражений

Заключение

Итак, вот оно. Способ сопоставления сбалансированных вложенных структур с использованием прямых ссылок в сочетании со стандартными (расширенными) функциями регулярных выражений - без рекурсии или сбалансированных групп. Это не эффективно, и это, конечно, не красиво, но это возможно. И это никогда не было сделано раньше. Для меня это довольно захватывающе.

Я знаю, что многие из вас используют регулярные выражения, чтобы выполнять и помогать другим пользователям выполнять более простые и более практичные задачи, но если есть кто-то, кто разделяет моё воодушевление от расширения пределов возможностей с помощью регулярных выражений, то я бы хотел услышать от вас, Если есть интерес, у меня есть другие подобные материалы для публикации.

Источник

краткое

Входные поправки

Прежде всего, ваш ввод неверен, так как есть лишние скобки (как показано ниже)

(F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third)))))))
                                ^

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

Лишние скобки удалены

(F(i(r(s)t))) ((S)(e)((c)(o))n)d (((((((Third)))))))
                                ^

Добавлены дополнительные скобки для соответствия дополнительным закрывающим скобкам

((F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third)))))))
^

Regex Capabilities

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

Это означает, что для разновидностей регулярных выражений, которые в настоящее время не поддерживают рекурсию (Java, Python, JavaScript и т. Д.), Рекурсия (или попытки имитации рекурсии) в регулярных выражениях невозможна.

вход

Учитывая, что исходные данные на самом деле недействительны, мы будем использовать следующие входные данные для проверки.

(F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third)))))))
(F(i(r(s)t))) ((S)(e)((c)(o))n)d (((((((Third)))))))
((F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third)))))))

Тестирование этих входных данных должно дать следующие результаты:

  1. НЕВЕРНЫЙ (не соответствует)
  2. ДЕЙСТВИТЕЛЬНО (матч)
  3. ДЕЙСТВИТЕЛЬНО (матч)

Код

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

Смотрите регулярное выражение в использовании здесь

Использование блока DEFINE 

(?(DEFINE)
  (?<value>[^()\r\n]+)
  (?<groupVal>(?&group)|(?&value))
  (?<group>(?&value)*\((?&groupVal)\)(?&groupVal)*)
)
^(?&group)$

Примечание: это регулярное выражение использует флаги gmx

Без блока DEFINE

Смотрите регулярное выражение в использовании здесь

^(?<group>
  (?<value>[^()\r\n]+)*
  \((?<groupVal>(?&group)|(?&value))\)
  (?&groupVal)*
)$

Примечание: это регулярное выражение использует флаги gmx

Без модификатора x (однострочный)

Смотрите регулярное выражение в использовании здесь

^(?<group>(?<value>[^()\r\n]+)*\((?<groupVal>(?&group)|(?&value))\)(?&groupVal)*)$

Без имени (группы и ссылки)

Смотрите регулярное выражение в использовании здесь

^(([^()\r\n]+)*\(((?1)|(?2))\)(?3)*)$

Примечание: это самый короткий метод, который я мог придумать.

объяснение

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

  • ^ Утвердить позицию в начале линии
  • (([^()\r\n]+)*\(((?1)|(?2))\)(?3)*) Запишите следующее в группу захвата 1
    • ([^()\r\n]+)* Запишите следующее в группу захвата 2 любое количество раз
      • [^()\r\n]+ Совпадение с любым персонажем, которого нет в наборе ()\r\n один или несколько раз
    • \( Совпадение с левой / открывающей скобкой ( в прямом смысле
    • ((?1)|(?2)) Захватить одно из следующего в группу захвата 3
      • (?1) Рекурсировать первый подшаблон (1)
      • (?2) Рекурсировать второй подшаблон (2)
    • \) Соответствует символу правой / закрывающей скобки ) в прямом смысле
    • (?3)* Рекурсировать третий подшаблон (3) любое количество раз
  • $ Утвердить позицию в конце строки
Источник
Другие вопросы по тегам