カッコの妥当性｜コードで実践

カッコの妥当性

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

開きカッコは スタック に積み、閉じカッコが来たら スタックの top と対応するかチェックする

validateParen(s) を実装してください

文字列に含まれる ()、{}、[] の 3 種類の カッコ が 正しくネスト されているか判定する問題は、スタック のもっとも有名な応用です

カッコの妥当性とは

スタック を使って (){} [] 混在の文字列が 正しいネスト になっているか判定する。

文字列に含まれる ()、{}、[] の 3 種類の カッコ が 正しくネスト されているか判定する問題は、スタック のもっとも有名な応用です。コンパイラ の 構文解析、JSON の パーサ、正規表現エンジン などで実際に使われています。本レッスンで スタック思考 を体得しましょう。

開きカッコは スタック に積み、閉じカッコが来たら スタックの top と対応するかチェックする。これだけで全てが解ける。

スタックを使う理由

カッコ の対応は 最後に開いたものが最初に閉じる (LIFO, Last-In-First-Out) という構造を持ちます。これは スタック のデータ構造そのものです。先に開いたもの を 後で閉じる という入れ子のルールを スタック の push / pop でそのままモデル化できる、というのが本質です。

diagram (will load when visible)

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

図で表すと、開きカッコ のたびに スタック を高くし、閉じカッコ のたびに 1 段下げます

図で表すと、開きカッコ のたびに スタック を高くし、閉じカッコ のたびに 1 段下げます。最後に スタック が空ならネストが完全に閉じられたので valid です。

Python での実装

Python

def validateParen(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 not stack

pairs は 閉じ → 開き の 対応マップ。閉じカッコ が来たら stack.pop() で top を取り出し、対応関係に合うかをチェックします。top が合わなければその場で False。

JavaScript での実装

JavaScript

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

pop() は空配列だと undefined を返すので、!== pairs[ch] のチェックで自動的に false になります。便利。

Java での実装

Java

import java.util.*;
public class Solution {
    public static boolean validateParen(String s) {
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.pop() != pairs.get(ch)) return false;
            }
        }
        return stack.isEmpty();
    }
}

Java では Deque を スタック として使うのが定石です (Stack クラスより速い)。push / pop がそのまま使えます。

3 つのケースで `false`

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

閉じカッコ の 相方 が top と違う (例: (])

文字列を読み終えても スタック に 開きカッコ が残っている (例: (()

この 3 つのいずれかに該当しなければ true です。

よくある間違い

スタック が空のときに pop() を呼んで例外を出す。空チェックを忘れない。
閉じカッコ 以外の文字 (アルファベット等) が来たときの扱いを定義しない。今回は カッコ以外無視 する仕様。
相方の対応 を (': ')' の向きで書いてしまう。閉じ → 開き の向きが楽。

やってみよう

validateParen(s) を実装してください。s には (), [], {} の 6 種類の カッコ だけが含まれます (空文字も可)。正しくネストされているとき true、そうでないとき false を返します。スタック を使い、O(n) で判定してください。

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. 計算量はどう求めれば良いですか？

A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

Q. 覚えるべき定番アルゴリズムは何ですか？

A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

次のレッスン

次は ローマ数字を整数に で、I・V・X などの記号を左から走査し、次の記号より小さい値は減算するルールで整数へ変換する方法を学びます。

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

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

理解度チェック (30 秒)

Q. カッコの妥当性とは何か、1 文で説明してください。

この章のポイント

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

関連レッスン

カッコの妥当性