括弧の対応をチェックしよう(スタックの応用)

このレッスンでは、スタックを応用して括弧の対応をチェックするアルゴリズムを学び、データ構造の実践的な使い方を理解することを目標にします。「Ruby 括弧 対応チェック」で調べている方向けです。

スタック(後入れ先出し)を使うと、(や[のような開き括弧を積んでおき、閉じ括弧が来るたびに一番上と対応しているか確認する、という方法で括弧の対応チェックができます。

サンプルコードでは、stackという配列をスタックとして使い、str.each_charで文字列を1文字ずつ処理しながら、開き括弧のときはpush、閉じ括弧のときはpopで取り出した値が正しいペアかどうかをpairsというハッシュで確認しています。

初心者がよくつまずくのが、対応する括弧の種類が違う場合(閉じ括弧の種類が合わない場合)の判定です。単に開き括弧と閉じ括弧の数が一致しているだけでは不十分で、それぞれの種類が正しいペアになっているかまで確認する必要がある点が、このアルゴリズムのポイントです。

エディタの入力補完やコードのシンタックスチェックの裏側でも、似た考え方が使われています。HTMLタグの開閉タグが正しく対応しているかをチェックする、似た仕組みのツールもたくさん存在します。