[今週の問題]カッコをつける[解説]
http://vipprog.tumblr.com/post/48288901/quiz-add-parenthese の答えです。
解説は明日とか言いつつ 何日目だよｗｗ
と言うことで解説です。
この問題の解法（アルゴリズム）は前回書いたとおり、大体二つあります。
先頭から調べていくぜベイベ
一応もっとも高速（O(N)）で、最初に思いつく方法でしょう。
頭から調べていって、(と)の数をカウントしていくという方法です。
ポイントは、(が今までないのに、)で閉じたと勘違いしないようにすることです。
たとえば
)(
の場合。
()()
としなければいけませんよね。
ということは、
int right=0; // ) を追加する数、マイナスなら (
for(int i=0; i < str.length(); i++) {
if(str[i] == '(')
right++;
elseif(str[i] == ')')
right--;
}
の様に単純にカウントしていってはダメです。
上の場合だと、最初にright=-1となってその後、right=0になってしまいますね。
きちんとleftも用意してあげましょう。
int right= 0; // ) を追加する数
int left = 0; // ( を追加する数
for(int i=0; i < str.length(); i++) {
if(str[i] == '(')
right++;
elseif(str[i] == ')'){
if(right>0) // ちゃんと今までに(があるかチェック
right--;
else
left++;
}
}
// 表示
for(int i=0; i<left.length(); i++)
print( "(" );
print( str );
for(int i=0; i<right.length(); i++)
print( ")" );
これでおkです。
()を再帰的に削除していく。
()がなくなるまで、消していって、残った)(に対応するカッコを付け加えるといった方法です。
この方法は上の方法に比べ時間はかかりますが（O(N(N-2)/4);n>2）、直感的に分かりやすく、
関数型的な発想です。Jやsedなど特殊な言語はこっちじゃないとキツいかと思います。
(lamda (f)
(lamda (s)
(= m
(tr "()" ")(" ((Y (lambda (f) ; ()を消していって残った()
(lambda (s) ; を反転
(if (substring? "()" s)
(f (string-replace s "()") ; true
s ))))) ; false
s )))
(string-append (match #/\(*/ m)
s
(match #/\)*/ m))))
ちなみ上も下もコードは動きません、擬似言語です。
- 9/6 最後Yコンビネータ忘れてた
