我如何使用正则expression式匹配嵌套括号?

正如标题所示,以下是一个示例input:

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

当然,匹配的string将被recursion处理。

我想要第一个recursion匹配:

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

后续stream程不用说…

许多正则expression式实现将不允许您匹配任意数量的嵌套。 但是,Perl,PHP和.NET支持recursion模式。

在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"); } 

这将打印:

  ----------
 (外
    (中央
      (内)
      (内)
   中央)
 欧尔)
 ----------
 (外
    (内)
 欧尔)
 ----------
 (外
 欧尔) 

或者,PHP的等价物:

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

这产生:

 排列
 (
     [0] =>数组
         (
             [0] =>(外部
    (中央
      (内)
      (内)
   中央)
 欧尔)
             [1] =>(外部
    (内)
 欧尔)
             [2] =>(外部
 欧尔)
         )

 ... 

一个解释:

 (#开始组1
   \(#匹配文字'('
   (#组2
     [^()]#除'('和')'之外的任何字符
     |  # 要么
     (?R)#recursion匹配entir模式
   )*#结束组2并重复零次或多次
   \)#匹配一个文字')'
 )#结束组1 

编辑

注意@ Goozak的评论:

更好的模式可能是\(((?>[^()]+)|(?R))*\) (来自PHP:recursion模式 )。 对于我的数据,Bart的模式在碰到一个没有嵌套的(长string)的时候会崩溃。 这种模式经历了我所有的数据没有问题。

不要使用正则expression式。

相反,一个简单的recursion函数就足够了:

 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 

我发现这个简单的正则expression式提取所有使用recursion嵌套平衡组,虽然最终的解决scheme并不像你所期望的那样简单:

正则expression式模式: (1(?:\1??[^1]*?2))+

示例input: 1ab1cd1ef2221ab1cd1ef222

为了简单起见,我把1打开, 2打开closures的支架。 字母表示一些内部数据。 我会重写input,以便于解释。

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

在第一次迭代中,正则expression式将匹配第一个兄弟组1ab1cd1ef222最内部的子组1ab1cd1ef222 。 如果我们记住它的位置,并删除这个组,那么将保持1ab1cd22 。 如果我们继续使用正则expression式,它将返回1cd2 ,最后返回1ab2 。 然后,它将继续以同样的方式parsing第二兄弟组。

正如我们从这个例子看到的那样,正则expression式将正确地提取出现在由括号定义的层次结构中的子string。 在第二次迭代期间,如果在string中的位置在来自第二次迭代的子string之间,那么它是子节点,否则是兄弟节点。

从我们的例子:

  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 ,它是从另一个兄弟等分支…

我们必须迭代并删除所有的兄弟姐妹,然后才能移动到父代。 因此,我们必须按照它们在迭代中出现的顺序来记住所有的兄弟姐妹。

基于nneonneo上面张贴的Delphi Pascal代码:

你需要一个带有button的表单,命名为btnRun。 在源代码中,将“arnolduss”replace为DownLoads文件夹中的名称。 请注意由ParseList创build的输出中的堆栈级别。 显然相同types的括号必须在相同的堆栈级别打开和closures。 现在您将能够提取每个堆栈级别的所谓组。

 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.