
スタックを使った括弧の対応を追う
解き方
括弧の対応を調べるとき、開き括弧をスタックに積み、閉じ括弧に出会ったら直近の開き括弧と照合します。最後に開いた括弧を最初に閉じるため、後入れ先出しの順序が合います。
手順を追う例
丸括弧と角括弧を対象にします。文字列「([])」では、(、[の順に積み、]で[を、)で(を取り出します。途中で型の不一致がなく、読み終わりにスタックが空なら対応しています。閉じ括弧が来たときにスタックが空でも不正です。
確認問題【オリジナル】
文字列「([)]」を左から読みます。どの位置で不一致に気付きますか。また「(()」が不正と分かるタイミングはいつですか。
答えと解説
「([)]」は3文字目の)で不一致です。その時点のスタックの一番上は[なので、)とは対応しません。「(()」では最後まで型の不一致は起きませんが、読み終わった後に(が1つ残るため不正です。途中の照合と、最後に空かどうかの確認の両方が必要です。