Como posso combinar colchetes nesteds usando regex?

Como o título diz, aqui está um exemplo de input:

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

Naturalmente, as strings correspondentes serão processadas por recursion.

Quero que a primeira recursion corresponda:

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

E os processos depois é desnecessário dizer …

Muitas implementações regex não permitem que você corresponda a uma quantidade arbitrária de aninhamento. No entanto, Perl, PHP e .NET suportam padrões recursivos.

Uma demonstração em 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"); } 

qual imprimirá:

  ----------
 (exterior
    (Centro
      (interior)
      (interior)
    Centro)
  ouer)
 ----------
 (exterior
    (interior)
  ouer)
 ----------
 (exterior
  ouer) 

Ou o equivalente em PHP:

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

que produz:

  Matriz
 (
     [0] => Matriz
         (
             [0] => (exterior
    (Centro
      (interior)
      (interior)
    Centro)
  ouer)
             [1] => (exterior
    (interior)
  ouer)
             [2] => (exterior
  ouer)
         )

 ... 

Uma explicação:

 (# início do grupo 1
   \ (# corresponde a um literal '('
   (# grupo 2
     [^ ()] # qualquer caractere diferente de '(' e ')'
     |  # OR
     (? R) # corresponde recursivamente ao padrão inteiro
   ) * # grupo final 2 e repetir zero ou mais vezes
   \) # combina um literal ')'
 ) # grupo final 1 

EDITAR

Nota @ Comentário do Goozak:

Um padrão melhor pode ser \(((?>[^()]+)|(?R))*\) (do PHP: Padrões recursivos ). Para meus dados, o padrão de Bart estava travando o PHP quando encontrou uma (string longa) sem aninhar. Esse padrão passou por todos os meus dados sem problema.

Não use regex.

Em vez disso, uma function recursiva simples será suficiente:

 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 

Eu encontrei este regex simple que extrai todos os grupos balanceados nesteds usando recursion, embora a solução resultante não é bastante simples como você pode esperar:

Padrão de regex: (1(?:\1??[^1]*?2))+

Exemplo de input: 1ab1cd1ef2221ab1cd1ef222

Para simplificar, coloquei 1 para abrir e 2 para colchete fechado. Caracteres alfabéticos representam alguns dados internos. Vou rewrite a input para que seja fácil de explicar.

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

Na primeira iteração, a regex corresponderá ao subgrupo mais interno 1ef2 do primeiro grupo irmão 1ab1cd1ef222 . Se nos lembrarmos disso e de sua posição, e removermos esse grupo, permanecerá 1ab1cd22 . Se continuarmos com regex, ele retornará 1cd2 e, finalmente, 1ab2 . Então, continuará a analisar o segundo grupo de irmãos da mesma maneira.

Como podemos ver neste exemplo, o regex extrairá adequadamente substrings conforme aparecem na hierarquia definida por colchetes. A posição de substring particular na hierarquia será determinada durante a segunda iteração, se a posição na string estiver entre a subseqüência da segunda iteração, então é um nó filho, senão é um nó irmão.

Do nosso exemplo:

  1. 1ab1cd1ef222 1ab1cd1ef222 , iteração match 1ef2 , com índice 6 ,

  2. 1ab1cd22 1ab1cd1ef222 , correspondência de iteração 1cd2 , com índice 3 , terminando com 6 . Como 3 < 6 < = 6 , a primeira subseqüência é filha da segunda subseqüência.

  3. 1ab2 1ab1cd1ef222 , correspondência de iteração 1ab2 , com índice 0 , terminando com 3 . Como 0 < 3 < = 3 , a primeira subseqüência é filha da segunda substring.

  4. 1ab1cd1ef222 , iteração match 1ef2 , com índice 6 , porque não é 3 < 0 < = 6 , é ramo de outro irmão, etc …

Precisamos fazer uma iteração e remover todos os irmãos antes de podermos nos mudar para os pais. Assim, devemos nos lembrar de todos os irmãos na ordem em que aparecem na iteração.

Código Delphi Pascal baseado na postagem acima de nneonneo :

Você precisa de um formulário com um botão, chamado btnRun. No código-fonte, substitua “arnolduss” pelo seu nome na pasta DownLoads. Observe o nível da pilha na saída criada pelo ParseList. Obviamente, colchetes do mesmo tipo devem abrir e fechar no mesmo nível de pilha. Agora você poderá extrair os chamados grupos por nível de pilha.

 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.