カッコのバランス判定 (スタック応用)｜コードで実践

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

このレッスンで分かること

どのステップでも O(1) で済むので、全体は O(n) です

前の 2 つのレッスンで スタック と キュー の基本を押さえました

入れ子のカッコは、開いた順と逆の順に閉じる必要があります

カッコのバランス判定とは

スタックを使い、(){} [] 混在の文字列が正しいネスト構造になっているか判定する。本レッスンでは、カッコのバランス判定の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

前の 2 つのレッスンで スタック と キュー の基本を押さえました。ここで一度、実戦で必ず出てくるスタック応用 を経験しましょう。それが「カッコのバランス判定」です。文字列に含まれる ()、{}、[] の 3 種類のカッコが 正しく入れ子になっているか を true / false で返す問題です。コンパイラの構文解析、JSON パーサ、HTML / XML のタグ整合性チェックなど、業務の現場で繰り返し出てくる問題で、スタック のキラーアプリと言ってもよい例です。

「最後に開いたものが最初に閉じる」という入れ子のルールは、まさに LIFO そのもの。スタックで解くと自然な答えが出る。

なぜスタックなのか

入れ子のカッコは、開いた順と逆の順に閉じる必要があります。たとえば ([{}]) を見ると、( → [ → { の順で開き、閉じるときは } → ] → ) の順、つまり 開いた順の逆順 です。これはまさに スタック の LIFO 性質と一致します。「直前に開いたカッコ」をスタックの top に置いておけば、閉じカッコが来たときに top を見るだけで対応関係を判定できます。

アルゴリズム

手順は次のとおりです。

diagram (will load when visible)

図のポイント (テキスト併記)

図で書くと長く見えますが、本質は 3 ステップだけです

図で書くと長く見えますが、本質は 3 ステップだけです。

開きカッコ ( [ { ならスタックに push
閉じカッコ ) ] } なら、スタックが空なら false、そうでなければ pop して相方が一致するか確認
文字列の終端でスタックが空なら true、残っていたら false

どのステップでも O(1) で済むので、全体は O(n) です。

Python での実装

Python

def isBalanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack.pop() != pairs[ch]:
                return False
    return len(stack) == 0

pairs は 閉じ → 開き の対応マップです。閉じカッコが来たときに 1 行で top の正しさを判定できます。先に閉じ側をキーに置いておくと if 文が短くなります。

JavaScript での実装

JavaScript

function isBalanced(s) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else if (ch === ')' || ch === ']' || ch === '}') {
      if (stack.length === 0 || stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

Array.pop() は空配列で undefined を返しますが、!== pairs[ch] で確実に false になります。それでも if (stack.length === 0) を先に書く方が 意図が明確 で読みやすいので、面接やレビューでは前者が推奨です。

3 つの NG パターン

閉じカッコが来たのにスタックが空。例: }

閉じカッコと top の種類が違う。例: (]

全部読み終わってもスタックに開きカッコが残る。例: ((

上の 3 つのいずれかに当てはまれば false、どれも引っかからなければ true です。テストケースもこの 3 パターンの組み合わせを意識して書かれています。

よくある間違い

1 つ目は 対応マップを 開き → 閉じ で作ってしまうケースです。閉じカッコが来た瞬間に対応する開きを引きたいので、閉じ → 開き で持つ方が短く書けます。

2 つ目は 空スタックの pop を考慮しないケース。スタックが空のまま pop を呼ぶと言語によっては例外、JS の場合は undefined が返ってきます。スタックが空のチェックを先に入れます。

3 つ目は 終端でのスタック残り を忘れること。(((( のように開きっぱなしの文字列を true と判定してしまうと、テストの最終ケースで落ちます。

やってみよう

({[]}) を手で追って、スタックがどう変化するか紙に書く。
[(]) のようにネストが交差するケースが false になる理由を、スタックの状態で説明できるようにする。
カッコ以外の文字 (アルファベットなど) を許す仕様に拡張するなら、どこに else: continue を入れるか考える。
JSON や HTML タグの整合性チェックに使うなら、pairs の中身を増やすだけで応用できる。具体例を書いてみる。

よくある質問

Q. スタックの主な用途は何ですか？

A. 「最後に入れたものから取り出す」LIFO 構造で、関数呼び出しの履歴・式の評価・括弧のマッチング・undo 機能などに使います。配列で push / pop すれば実装でき、Java は ArrayDeque、Python は list、JS は配列が事実上のスタックとして使えます。

Q. Java の Stack クラスは使うべきですか？

A. 古い Vector を継承していて非推奨気味です。代わりに ArrayDeque を使ってください。push / pop / peek が同じインターフェースで使え、同期化のオーバーヘッドがない分高速です。並行アクセスが必要なら ConcurrentLinkedDeque を選びます。

Q. スタックオーバーフローはどう防ぐ？

A. 再帰深さを浅くするか、再帰を明示的なスタック（ArrayDeque）に書き換えます。後者は深さ制限がメモリ次第になるため、大規模グラフ探索などで重宝します。tail call 最適化のある言語（Scala/Scheme）なら再帰のままで OK です。

次のレッスン

次は set で重複を除去する に進みましょう。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

カッコのバランスの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. カッコのバランスとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

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