perlでの括弧対応チェック

質問

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

回答No.3

ryu_chan · ベストアンサー

Perl 5.10から正規表現に(?PARNO)という再帰する構文が加わりました。
その説明文に、まさに括弧対応の正規表現の例文があります。

http://fleur.hio.jp/perldoc/mix/pod/perl5100delta.mix.html#Regular_expressions

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

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;
}

お礼

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

回答No.2

zxcv0000

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

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

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

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

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

お礼

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

回答No.1

Tacosan

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

お礼

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