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

Ответ 1

Многие реализации регулярных выражений не позволят вам сопоставить произвольное количество вложенности. Тем не менее, 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");
}

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

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

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

$text = '(outer
   (center
     (inner)
     (inner)
   center)
 ouer)
 (outer
   (inner)
 ouer)
 (outer
 ouer)';

preg_match_all('/(\(([^()]|(?R))*\))/', $text, $matches);

print_r($matches);

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

Array
(
    [0] => Array
        (
            [0] => (outer
   (center
     (inner)
     (inner)
   center)
 ouer)
            [1] => (outer
   (inner)
 ouer)
            [2] => (outer
 ouer)
        )

...

Объяснение:

(          # start group 1
  \(       #   match a literal '('
  (        #   group 2
    [^()]  #     any char other than '(' and ')'
    |      #     OR
    (?R)   #     recursively match the entir pattern
  )*       #   end group 2 and repeat zero or more times
  \)       #   match a literal ')'
)          # end group 1

ИЗМЕНИТЬ

Примечание @Goozak:

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

Ответ 2

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

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

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

Ответ 3

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

Шаблон регулярного выражения: (1(?:\1??[^1]*?2))+

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

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

1  ab  1 cd 1ef2 2  2     1  ab  1 cd 1ef2 2  2

            |_1|
       |______2__|
|_____________3_____|

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

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

В нашем примере:

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

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

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

• 1ab1cd1ef222, итерация соответствует 1ef2, с индексом 6, Поскольку это не 3 < 0 <= 6, это ветвь от другого брата и т.д.

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

Ответ 4

Код 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/info/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.