カッコの妥当性

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

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

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

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

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

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

open_tags = []
open_tags.append("div")   # <div> を開いた
open_tags.append("p")     # <p> を開いた
open_tags[-1]             # いま閉じられるのは "p" だけ
open_tags.pop()           # </p> で 1 段下がる

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

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

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

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

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

やってみよう

ひな形の TODO を完成させてください。開き側を積み、閉じ側で空と相方を確認を自分で書きます。入力を受け取る枠と説明つきの準備部分はそのまま使えます。

演習で使う書き方

本文のタグの例では、div の後に p を開くと p を先に閉じます。カッコもこの順です。append は末尾追加、pop は末尾取り出しで、空では取り出せません。対応表と空のスタックは用意しました。演習では開き側の追加と、閉じ側の空確認・取り出し・相方の比較を書きます。二つの if を順に書けば複合条件は不要です。

1. 開き側を積み、閉じ側で空と相方を確認を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える