perlでの括弧対応チェック

perlで括弧の対応の妥当性を知りたいのですが
どの様にすればよろしいでしょうか？
ex).
(X1+X2)+X3 -> OK
((X1+X2)+X3 -> NG
((X1+X2))+X3 -> OK
)(X1+X2)+X3 -> NG
などチェックを行いたいと思っています

No.3 ベストアンサー 回答者： ryu_chan 回答日時： 2009/12/11 15:56

Perl 5.10から正規表現に(?PARNO)という再帰する構文が加わりました。

その説明文に、まさに括弧対応の正規表現の例文があります。

http://fleur.hio.jp/perldoc/mix/pod/perl5100delt …

これをそのまま流用すれば、以下のようなコードが書けます。

my @expressions = qw{
(X1+X2)+X3
((X1+X2)+X3
((X1+X2))+X3
)(X1+X2)+X3
};

for my $exp (@expressions) {
print "$exp -> ", has_balanced_brackets($exp) ? 'OK' : 'NG', "\n";
}

sub has_balanced_brackets {
my $exp = shift;

my $re = qr{
^[^()]* # start of line
( # start capture buffer 1
\( # match an opening round bracket
(?: # match one of:
(?> # don't backtrack over the inside of this group
[^()]+ # one or more non round brackets
) # end non backtracking group
| # ... or ...
(?1) # recurse to bracket 1 and try it again
)* # 0 or more times.
\) # match a closing round bracket
) # end capture buffer one
}x;

$exp =~ $re ? 1 : return;
}


あるいは、文字列の先頭から1文字ずつ括弧を探し、開き括弧と閉じ括弧の数が同じかをチェックする方法はどうでしょうか？

とりあえず、質問者さん提示の例ではうまく動作しているようです。

sub has_balanced_brackets {
my $exp = shift;
my $bracket_count = 0;

for my $pos ( 0 .. length($exp)-1 ) {
my $char = substr $exp, $pos, 1;

if ( $char eq '(' ) { $bracket_count++ }
elsif ( $char eq ')' ) { $bracket_count-- }

last if $bracket_count < 0;
}

$bracket_count == 0 ? 1 : return;
}

この回答へのお礼

大変参考になりました。
親切なご回答ありがとうございます。

お礼日時：2010/01/09 05:49

No.2 回答者： zxcv0000 回答日時： 2009/12/11 12:30

CPU負荷(処理時間)を気にするとかなり難しいテーマになます。

「\(」や "" で囲まれた括弧は括弧で無いなんていう規則を付けても、やはり難しいテーマになります。

そうで無ければ、例えば、最も内側の () の組を可能な限り繰り返し削除した結果に 「(」か「)」を含めば NG 無ければ OK とすれば良いです。

最も内側の () の組を 1個削除するのは s/\([^\(\)]*\)//s で良いでしょう。 これをヒントにやってみてください。


禁止事項である課題の丸投げの疑いがあるので、完成コードは書きません。 追加質問は、どこまでできていて何が分らないのかを詳しく書いてください。

この回答へのお礼

大変参考になりました。
ありがとうございました。

お礼日時：2010/01/09 05:50

No.1 回答者： Tacosan 回答日時： 2009/12/11 12:29

Perl のバージョンにもよるけど, かっこの対応だけなら例えば

my $reg;
$reg = qr/([^()] # not parentheses
| # or
\((??{$reg})\) # proper parentheses
)+/x;
のような「正規表現」でチェックできると思う. 「連続しちゃだめ」とかいうことだともっと工夫しないといけません.

この回答へのお礼

ありがとうございます。
おかげさまで何とかなりました。

お礼日時：2010/01/09 05:52