カッコの妥当性

数を数えるだけでは (] が通ってしまう

開きカッコと閉じカッコの個数が同じなら正しい、と考えると (] も )( も合格になります。前者は種類が食い違っていて、後者は閉じるほうが先に来ています。個数だけでは、この 2 つの壊れ方をどちらも捕まえられません。

判定に必要なのは総数ではありません。いま閉じようとしているカッコの相方が誰なのか、という情報です。

覚えておくのは「直前に開いたもの」だけ

{[()]} を左から読んでいくと、) が現れた時点で開いたままのものは { と [ と ( の 3 つです。このうち相方になれるのは、いちばん最後に開いた ( だけです。カッコの入れ子は、後に開いたものが先に閉じるという順序に必ず従います。

この「後に入れたものが先に出る」順序をそのまま扱える入れ物が、第 5 章で作ったスタックです。別の題材で動きだけ見ておきます。

HTML のタグでも、直前に開いたものしか閉じられないのは同じです。そして文字列を最後まで読み終えたとき、この入れ物が空でなければ、閉じ忘れが残っているということになります。

不正になる場面は 3 通りある

落とす条件は、種類の食い違いだけではありません。閉じカッコが来たのに開いたものが 1 つも残っていない場合と、読み終えたのに開いたままのものが残っている場合を合わせて、全部で 3 通りです。)( は前者で、(( は後者で落ちます。この 3 つを漏れなく書けているかが、そのまま正答率になります。

とくに、空の状態から取り出そうとする経路は言語ごとに挙動が分かれます。Python なら例外になり、JavaScript なら undefined が返ってきて、比較が静かに失敗するだけです。後者は一見うまく動いているように見えるので、意図してその挙動に乗っているのか、たまたま助かっているだけなのかを区別しておいてください。取り出す前に残っているかを確かめるか、取り出した結果が期待どおりかを確かめるか、どちらの順で書くかを先に決めておくと事故が減ります。

もう 1 つ、相方の対応をどちら向きで持つかも先に決めます。閉じカッコから開きカッコを引く向きにしておくと、読んでいる文字がそのまま手がかりになります。逆向きにすると、対応表を引くために余計な変換が挟まります。

やってみよう

validateParen(s) を実装してください。s には () [] {} の 6 種類の文字だけが入っています（空文字もあり得ます）。正しく入れ子になっていれば true、そうでなければ false を返します。スタックを使い、文字列を 1 回なめるだけの O(n) で判定してください。

1. 関数 validateParen(s) を実装し、boolean を返す
2. スタック データ構造を使い、O(n) で判定すること
3. 閉じカッコの種類が スタックの top と一致しないとき、または スタック が途中で空になったときに false を返す