正規表現でネストした括弧（）の最短マッチする方法

Question

正規表現でネストした括弧（）の最短マッチする方法考え中です。
/([\s\S]+)/ とか　/([\s\S]+?)/
だとネストされているとうまくいかず、、、
構造をに合わせたマッチする方法があればと思い質問させていただきました。

ああああああああ
(
    いいいいいいいい
    (
        
        うううううううう
        (
            ええええええええ
        )
    )
)

おおおおおおおお

かかかかかかかか
(
    きききききききき
    (
        くくくくくくくく
    )
)
けけけけけけけけ
ここここここここ

↓↓↓この部分を取得したい

(
    いいいいいいいい
    (
        
        うううううううう
        (
            ええええええええ
        )
    )
)

(
    きききききききき
    (
        くくくくくくくく
    )
)

Comments

[KojiDoi]

言語は何ですか?

[helloman]

PHPです。入力するの忘れてました。
修正しました。

[m.ts10806]

「最短マッチ」とはなにでしょうか

Answer 1

こんにちは

XMLに変換してからパースするという方法はいかがでしょうか？

$text = <<<TEXT
ああああああああ
(
    いいいいいいいい
    (

        うううううううう
        (
            ええええええええ
        )
    )
)

おおおおおおおお

かかかかかかかか
(
    きききききききき
    (
        くくくくくくくく
    )
)
けけけけけけけけ
ここここここここ
TEXT;


$text = str_replace('(', '<node>', $text);
$text = str_replace(')', '</node>', $text);

$xmlstr = 
    '<?xml version="1.0" encoding="UTF-8"?>' . 
    '<root>' .
    $text .
    '</root>';


$doc = new SimpleXMLElement($xmlstr);

$count = 0;
foreach ($doc->xpath('/root/node') as $node) {
    $count ++;
    $str = $node->asXML();
    $str = str_replace('<node>', '(', $str);
    $str = str_replace('</node>', ')', $str);
    echo $count . "個目 ==========\n";
    echo $str . "\n";
}

上記を実行すると、以下のような出力が得られます。

1個目 ==========
(
    いいいいいいいい
    (

        うううううううう
        (
            ええええええええ
        )
    )
)
2個目 ==========
(
    きききききききき
    (
        くくくくくくくく
    )
)

• 動作確認用Repl.it: https://repl.it/@jun68ykt/Q237764

補足

以下、参考までに補足します。

使用するプログラミング言語は異なりますが、二週間ほど前に、類似の質問がありました。

• pythonで入れ子上になったテキストの階層構造を取り出す

上記の質問に対する、私の回答 では所与の文字列からJSONを経由しましたが、このご質問では、XMLにして処理するのが手っ取り早いと思ったのでそのようにしました。ちなみに、そちらの回答の補足やコメントにも書きましたが、開くカッコと閉じるカッコがきちんと対応している文字列にマッチする正規表現を書けないことを、理屈として理解するためには、（上記回答のコメントでも書きましたが）、一度、以下のような本で学習されるとよいかと思います。

• 計算理論の基礎 [原著第2版] 1.オートマトンと言語

以上、参考になれば幸いです。

Comments

[helloman]

アイデアに感動です。
「pythonで入れ子上になったテキストの階層構造を取り出す」
も勉強になります。
ご回答ありがとうございました。

[jun68ykt]

どういたしまして。

> 「pythonで入れ子上になったテキストの階層構造を取り出す」
> も勉強になります。

とのことで、よかったです????

Answer 2

最短マッチさせずに最初と最後のカッコをとって
その中にあるカッコをひろうとか・・・

Comments

[yambejp]

並列だったり３重４重となってりいろいろ考えられるので難しいのは確か
PHPのマッチング処理はオフセットをとれるので検索開始位置を
調整することは可能だと思います

[helloman]

ちょっと挑戦してみます。

[helloman]

難しすぎて私にはできそうにありませんでした。

[yambejp]

・カッコの組み合わせはかならず()が１対1で存在する
・３重目のカッコは並列データがない

などの条件がそろえばやりようはあります
以下、とりあえず冗長に処理をかいてみました
$matchを2や3にあげて確認してみてください

[yambejp]

$str=<<<eof
ああああああああ
(
いいいいいいいい
(

うううううううう
(
ええええええええ
)
)
)

おおおおおおおお

かかかかかかかか
(
きききききききき
(
くくくくくくくく
)
)
けけけけけけけけ
ここここここここ
eof;
preg_match_all("/(|)/",$str,$m,PREG_OFFSET_CAPTURE);
$match=1; //ここでレベルを指定する
$level=0;
$m=array_map(function($x) use(&$level){
$ret=[$x[1]];
if($x[0]=="("){
$level++;
$ret[]=$level;
}
if($x[0]==")"){
$ret[]=$level;
$level--;
}
return $ret;
},$m[0]);
$data=[];
$flg=true;
foreach($m as $val){
if($val[1]==$match){
if($flg){
$data[]=[$val[0]];
}else{
$data[count($data)-1][]=$val[0];
}
$flg=!$flg;
}
};
foreach($data as $val){
print substr($str,$val[0],$val[1]-$val[0]+1)."<br>";
}

[helloman]

ありがとうございます。
感動です。勉強になります。

Answer 3

「段数がわからない、左右のバランスが取れたカッコ」とマッチさせるのは、本来の正規表現では行えない操作です。

PHPのPCREなど（参考）、拡張により可能となっている処理系もありますが、記法がややこしい、マッチしないパターンの場合処理時間を浪費してしまう危険があるなど、正規表現で行うのが適切ではないタスクです。

括弧の数を数えつつ文字列を1文字ずつ読んでいくなど、他の方策を考えたほうがいいでしょう。

Comments

[helloman]

違うやり方を考えてみます。
ちなみに「括弧の数を数えつつ文字列を1文字ずつ読んでいくなど」
はそのようにしたらいいでしょうか？

[m.ts10806]

一文字ずつ切り出してくのが良さそうですね。

[helloman]

ご回答ありがとうございます。