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

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

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

サンプルコードでは、stackという配列をスタックとして使い、開き括弧のときは.push()、閉じ括弧のときは.pop()で取り出した値が正しいペアかどうかをpairsというオブジェクトで確認しています。最終的にstack.length === 0であれば、すべての括弧が正しく対応していると判定できます。

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

プログラムのコードの構文チェックや、数式の妥当性検証などにも応用される、スタックというデータ構造の実用的な使用例です。エディタの入力補完やコードのシンタックスチェックの裏側でも、似た考え方が使われています。