Как я могу сопоставить вложенные скобки с помощью regex?

Как гласит название, вот пример ввода:

(outer (center (inner) (inner) center) ouer) (outer (inner) ouer) (outer ouer) 

Конечно, согласованные строки будут обработаны рекурсией.

Я хочу, чтобы первая recursion соответствовала:

  [ (outer (center (inner) (inner) center) ouer), (outer (inner) ouer), (outer ouer)] 

И последующие процессы бесполезно сказать …

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

Демонстрация в Perl:

 #!/usr/bin/perl -w my $text = '(outer (center (inner) (inner) center) ouer) (outer (inner) ouer) (outer ouer)'; while($text =~ /(\(([^()]|(?R))*\))/g) { print("----------\n$1\n"); } 

который будет печатать:

  ----------
 (внешний
    (центр
      (Внутренний)
      (Внутренний)
    центр)
  ouer)
 ----------
 (внешний
    (Внутренний)
  ouer)
 ----------
 (внешний
  ouer) 

Или, эквивалент PHP:

 $text = '(outer (center (inner) (inner) center) ouer) (outer (inner) ouer) (outer ouer)'; preg_match_all('/(\(([^()]|(?R))*\))/', $text, $matches); print_r($matches); 

который производит:

  массив
 (
     [0] => Массив
         (
             [0] => (внешний
    (центр
      (Внутренний)
      (Внутренний)
    центр)
  ouer)
             [1] => (внешний
    (Внутренний)
  ouer)
             [2] => (внешний
  ouer)
         )

 ... 

Объяснение:

 (# стартовая группа 1
   \ (# совместить литерал '('
   (# группа 2
     [^ ()] # любой символ, отличный от '(' и ')'
     |  # ИЛИ
     (? R) # рекурсивно соответствуют шаблону entir
   ) * # end group 2 и повторить ноль или более раз
   \) # соответствует литералу ')'
 ) # конечная группа 1 

РЕДАКТИРОВАТЬ

Примечание @ Комментарий Goozak:

Лучшим шаблоном может быть \(((?>[^()]+)|(?R))*\) (из PHP: рекурсивные шаблоны ). По моим данным, шаблон Барта громил PHP, когда он встречал (длинную строку) без вложенности. Этот шаблон прошел через все мои данные без проблем.

Не используйте регулярное выражение.

Вместо этого достаточно простой рекурсивной функции:

 def recursive_bracket_parser(s, i): while i < len(s): if s[i] == '(': i = recursive_bracket_parser(s, i+1) elif s[i] == ')': return i+1 else: # process whatever is at s[i] i += 1 return i 

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

Образец регрессии: (1(?:\1??[^1]*?2))+

Пример ввода: 1ab1cd1ef2221ab1cd1ef222

Для простоты положим 1 для открытого и 2 для закрытой скобки. Альфа-символы представляют собой некоторые внутренние данные. Я переписал ввод, чтобы его было легко объяснить.

 1 ab 1 cd 1ef2 2 2 1 ab 1 cd 1ef2 2 2 |_1| |______2__| |_____________3_____| 

В первом итерационном регулярном выражении будет соответствовать самая внутренняя подгруппа 1ef2 из первой группы 1ab1cd1ef222 . Если мы запомним это и его положение, и удалим эту группу, останется 1ab1cd22 . Если мы продолжим с регулярным выражением, оно вернет 1cd2 и, наконец, 1ab2 . Затем он будет продолжать разбирать вторую группу братьев.

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

Из нашего примера:

  1. 1ab1cd1ef222 1ab1cd1ef222 , итерационное соответствие 1ef2 , с индексом 6 ,

  2. 1ab1cd22 1ab1cd1ef222 , итерационное соответствие 1cd2 , с индексом 3 , заканчивающееся на 6 . Поскольку 3 < 6 <= 6 , первая подстрока является дочерней для второй подстроки.

  3. 1ab2 1ab1cd1ef222 , итерационное соответствие 1ab2 , с индексом 0 , заканчивающееся на 3 . Поскольку 0 < 3 <= 3 , первая подстрока является дочерней для второй подстроки.

  4. 1ab1cd1ef222 , итерация соответствует 1ef2 , с индексом 6 , потому что это не 3 < 0 <= 6 , это ветка от другого брата и т. Д. …

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

Код Delphi Pascal, основанный на публикации выше от nneonneo :

Вам нужна форма с кнопкой на ней, называемая btnRun. В исходном коде замените «arnolduss» своим именем в папке DownLoads. Обратите внимание на уровень стека в выходе, создаваемом ParseList. Очевидно, скобки того же типа должны открываться и закрываться на одном уровне стека. Теперь вы сможете извлечь так называемые группы на уровне стека.

 unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls; Type TCharPos = record Level: integer; Pos: integer; Char: string; end; type TForm1 = class(TForm) btnRun: TButton; procedure btnRunClick(Sender: TObject); private { Private declarations } procedure FormulaFunctionParser(var CharPos: array of TCharPos; const formula, LBracket, RBracket: string; var itr, iChar, iLevel: integer; var ParseList: TStringList); public { Public declarations } end; var Form1: TForm1; implementation {$R *.dfm} procedure TForm1.btnRunClick(Sender: TObject); var formula: string; CharPos: array of TCharPos; itr, iChar, iLevel: integer; ParseList: TStringList; begin screen.Cursor := crHourGlass; itr := 0; iChar := 1; iLevel := 0; ParseList := TStringList.Create; try formula := Trim('add(mul(a,add(b,c)),d) + e - sub(f,g)'); ParseList.Add(formula); ParseList.Add('1234567890123456789012345678901234567890'); SetLength(CharPos, Length(formula)); FormulaFunctionParser(CharPos[0], formula, '(', ')', itr, iChar, iLevel, ParseList); finally ParseList.SaveToFile('C:\Users\arnolduss\Downloads\ParseList.txt'); FreeAndNil(ParseList); screen.Cursor := crDefault; end; end; //Based on code from nneonneo in: https://stackoverflow.com/questions/14952113/how-can-i-match-nested-brackets-using-regex procedure TForm1.FormulaFunctionParser(var CharPos: array of TCharPos; const formula, LBracket, RBracket: string; var itr, iChar, iLevel: integer; var ParseList: TStringList); procedure UpdateCharPos; begin CharPos[itr-1].Level := iLevel; CharPos[itr-1].Pos := itr; CharPos[itr-1].Char := formula[iChar]; ParseList.Add(IntToStr(iLevel) + ' ' + intToStr(iChar) + ' = ' + formula[iChar]); end; begin while iChar <= length(formula) do begin inc(itr); if formula[iChar] = LBracket then begin inc(iLevel); UpdateCharPos; inc(iChar); FormulaFunctionParser(CharPos, formula, LBracket, RBracket, itr, iChar, iLevel, ParseList); end else if formula[iChar] = RBracket then begin UpdateCharPos; dec(iLevel); inc(iChar); end else begin UpdateCharPos; inc(iChar); end; end; end; end. 
Interesting Posts

Как использовать ProGuard в Android Studio?

Как увеличить пространство между полосками на штриховом участке в ggplot2?

Типы Haskell расстраивают простую «среднюю» функцию

Почему Firefox так плохо при изменении размеров изображений?

Почему Java Double.compare (double, double) реализован так, как есть?

Иллюстрирование использования ключевого слова volatile в C #

Что такое кэширование дискового пространства Btrfs?

Как выбрать (выделить) текст в чате Skype без использования мыши?

Зачем использовать синглтон вместо статических методов?

Начало работы с Android

Будут ли маршрутизаторы «замыкаться» на свой внешний внешний адрес?

Как я могу заставить проект Eclipse-Maven автоматически обновлять свой путь к classам, когда я изменяю зависимость в моем файле pom.xml?

Разница между API AndroidShadowLayer

“Неопределенная ссылка на” конструктор classа шаблона

Использование явно пронумерованного повторения вместо вопросительного знака, звезды и плюс

Давайте будем гением компьютера.