Is it possible to match nested brackets with a regex without using recursion or balancing groups?

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

(F(i(r (s) t))) ((S) (e) ((c) (o))(n) d) ((((((((Третий)))))))

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

_{Stack Overflow поощряет самостоятельные ответы на вопросы, поэтому я решил создать этот пост, чтобы поделиться тем, что я недавно обнаружил.}

Действительно! Это возможно с помощью прямых ссылок:

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

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

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

Нет, нет ограничения на глубину. Нет, там нет скрытых рекурсивных конструкций. Просто старые поисковые решения с большим количеством прямых ссылок. Если ваш вариант не поддерживает прямые ссылки (я смотрю на вас, 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)))))))
^

Возможности регулярных выражений

Во-вторых, это действительно возможно только в вариантах регулярных выражений, которые включают возможность рекурсии, поскольку любой другой метод не будет должным образом сопоставлять открывающие / закрывающие скобки (как видно из решения 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)
  (?<value>[^()\r\n]+)
  (?<groupVal>(?&group)|(?&value))
  (?<group>(?&value)*\((?&groupVal)\)(?&groupVal)*)
)
^(?&group)$

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

Без блока ОПРЕДЕЛЕНИЯ

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

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

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

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

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

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

Without named (groups & references)

See regex in use here

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

Note: This is the shortest possible method that I could come up with.

Explanation

I'll explain the last regex as it's a simplified and minimal example of all the other regular expressions above it.

• ^ Assert position at the start of the line


• (([^()\r\n]+)*\(((?1)|(?2))\)(?3)*) Capture the following into capture group 1
  
  
  
  • ([^()\r\n]+)* Capture the following into capture group 2 any number of times
    
    
    
    
    • [^()\r\n]+ Match any character not present in the set ()\r\n one or more times
    
    
  
  
  • \( Match a left/opening parenthesis character ( literally
  
  
  • ((?1)|(?2)) Capture either of the following into capture group 3
    
    
    
    • (?1) Recurse the first subpattern (1)
    
    
    • (?2) Recurse the second subpattern (2)
    
    
  
  
  • \) Match a right/closing parenthesis character ) literally
  
  
  • (?3)* Recurse the third subpattern (3) any number of times
  
  


• $ Assert position at the end of the line