カッコのバランス判定 (スタック応用)

タグを開いた順と、閉じる順

HTML のタグで div を開き、その内側で p を開いたとします。内側の p を閉じてから、外側の div を閉じます。エディタで入れ子の崩れを調べるときも、この順序を見ます。あとから開いたものほど、先に閉じるという約束です。

丸括弧、角括弧、波括弧にも同じ約束があります。この回では括弧だけの文字列を左から読み、対応が正しいかを確かめます。HTML 全体の解析には別の規則もありますが、入れ子の考え方は共通です。

確かめる相手は、いちばん内側

開いたままの括弧はすべてスタックに残します。ただし閉じ括弧が来た瞬間に照合する相手は、いちばん上の1つです。これが現在のいちばん内側に当たります。

開き括弧が来たら積み、閉じ括弧が来たら上の種類を確かめ、一致したときだけ取り出します。外側を先に取り出すと、入れ子が交差してしまいます。

opened = ["(", "["]
print(opened[-1])    # [

添字 -1 は末尾です。この状態で次に閉じてよいのは角括弧で、丸括弧ではありません。上を見るだけでは、スタックの内容は変わりません。

閉じ側から、必要な開き側を引く

対応表は、いま読んだ閉じ括弧から必要な開き括弧が分かる向きにします。Python の辞書はキーに対応する値を取り出せる表です。

pairs = {")": "(", "]": "[", "}": "{"}
print(pairs["]"])    # [

この表で必要な種類を調べ、スタックの上と比べます。括弧の種類は3つだけなので、1文字ごとの処理時間は一定です。n文字を1回ずつ読む判定全体は O(n) になります。

最後の空も確かめる

不正になるのは、空のスタックに閉じ括弧が来る場合、上と種類が違う場合、読み終わって開き括弧が残る場合です。開き括弧だけの文字列も、途中で種類の不一致は起きませんが不正です。

例題で確かめる

文字列 ([{}]) を読みます。左を底、右を上として、スタックの変化を追います。

6文字すべてで対応が合い、最後も空なので正しい入れ子です。開き3個、閉じ3個という個数だけで判断せず、閉じる順まで確かめています。