25

正如标题所说，这是一个示例输入：

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

当然，匹配的字符串会被递归处理。

我希望第一个递归匹配：

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

后面的流程就不用说了...

4

4 回答 4

36

许多正则表达式实现不允许您匹配任意数量的嵌套。但是，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");
}

这将打印：

----------
（外
   （中央
     （内）
     （内）
   中央）
 欧尔）
----------
（外
   （内）
 欧尔）
----------
（外
 欧尔）

或者，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 组
  \( # 匹配一个文字 '('
  (#第二组
    [^()] # 除 '(' 和 ')' 以外的任何字符
    | ＃ 或者
    (?R) # 递归匹配整个模式
  )* # 结束第 2 组并重复零次或多次
  \) # 匹配文字 ')'
) # 结束组 1

编辑

注意@Goozak 的评论：

更好的模式可能是\(((?>[^()]+)|(?R))*\)（来自PHP:Recursive patterns）。对于我的数据，Bart 的模式在遇到没有嵌套的（长字符串）时使 PHP 崩溃。这种模式毫无问题地遍历了我的所有数据。

于 2013-02-19T08:12:33.450 回答
25

不要使用正则表达式。

相反，一个简单的递归函数就足够了。这是一般结构：

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

例如，这是一个将输入解析为嵌套列表结构的函数：

def parse_to_list(s, i=0):
    result = []
    while i < len(s):
        if s[i] == '(':
            i, r = parse_to_list(s, i+1)
            result.append(r)
        elif s[i] == ')':
            return i+1, result
        else:
            result.append(s[i])
            i += 1
    return i, result

像这样调用parse_to_list('((a) ((b)) ((c)(d)))efg')会产生结果[[['a'], ' ', [['b']], ' ', [['c'], ['d']]], 'e', 'f', 'g']。

于 2013-02-19T07:58:53.517 回答
8

我发现了这个简单的正则表达式，它使用递归提取所有嵌套的平衡组，尽管得到的解决方案并不像您期望的那样简单：

正则表达式模式：(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, 它是另一个兄弟的分支, 等等...

我们必须在移动到父节点之前迭代并删除所有兄弟节点。因此，我们必须按照它们在迭代中出现的顺序记住所有兄弟姐妹。

于 2014-08-25T16:05:01.507 回答
0

基于nneonneo上面发布的 Delphi Pascal 代码：

您需要一个带有按钮的表单，名为 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.
于 2017-04-04T11:48:26.017 回答