カッコのバランス判定 (スタック応用)
<div><p></div></p> は、なぜ怒られるのか
HTML でこの形を書くと、エディタが赤い線を引きます。<div> を開き、<p> を開いた。ならば閉じるのは </p> が先で、</div> があとです。あとから開いたものほど、先に閉じなければならない からです。
これは HTML に限った話ではありません。( [ { の入れ子も、JSON も、プログラムのブロックも、全部同じ約束で動いています。だから 1 度この判定を書けるようになると、対応させるものが変わっても同じ手が使えます。
覚えておくのは、いちばん内側の 1 つだけ
一見すると、開いたものを全部覚えて突き合わせる必要がありそうです。実際にはそうではなく、閉じ側が来たときに確かめる相手は いま開いている中でいちばん内側の 1 つ だけです。
<div><ul><li></li></ul></div> を左から読んでいくと、開いたままのものは次のように増減します。
| 読んだところ | 開いたままのもの |
|---|---|
<div> | div |
<ul> | div, ul |
<li> | div, ul, li |
</li> | div, ul |
</ul> | div |
</div> | なし |
閉じ側が来るたび、消えるのは常にいちばん右です。この動きは、前々回に見たスタックそのものです。
Python
opened = ["div", "ul", "li"]
print(opened[-1]) # li いま閉じてよいのはこれだけだからスタックを 1 本用意して、開き側で積み、閉じ側で下ろす。それだけで判定できます。
閉じ側をキーにすると、引くのが 1 回で済む
対応表の向きには、良い向きと悪い向きがあります。判定する瞬間に手元にあるのは 閉じ側 なので、閉じ側から開き側を引ける形にしておくと、そのまま 1 回引くだけで相手が分かります。
Python
pairs = {"</div>": "<div>", "</p>": "<p>", "</li>": "<li>"}
print(pairs["</p>"]) # <p>逆向きに作ると、閉じ側から探すために表を全部なめることになります。どちらをキーにするかで、書く量も速さも変わります。
読み終わったときに、何も残っていないか
不正になる形は 3 つあります。
- 閉じ側が来たのに、開いているものが 1 つも無い
- 閉じ側が来たが、いちばん内側のものと種類が違う
- 最後まで読み終わったのに、開いたままのものが残っている
3 番目を忘れると、<div><div> のように開きっぱなしの文字列を正しいと答えてしまいます。読み終わった時点での確認を、必ず入れてください。
Python
opened = ["div", "div"]
print(len(opened) == 0) # False 残っているので不正どの手順も 1 タグぶんの処理しかしません。文字列を 1 回なめるだけなので、全体で O(n) です。
要件
- boolean を返す関数 isBalanced(s) を実装する
- スタックを使い O(n) で判定する
- 閉じカッコがスタックの top と一致しない、または途中でスタックが空になる、または終端でスタックが残るときは false
入出力例
isBalanced("()") → true
isBalanced("()[]{}") → true
isBalanced("{[()]}") → true
isBalanced("(]") → false
isBalanced(")(") → false
isBalanced("(((") → false
isBalanced("") → true
isBalanced("[({})]({})") → trueヒント
