Pythonで括弧の対応が取れているか（整形式か）を判定するプログラムの書き方

文字列処理の定番問題として、丸括弧「()」・波括弧「{}」・角括弧「[]」といった複数種類の括弧が混在する文字列が与えられ、その括弧がすべて正しく対応しているかどうか（バランスが取れている＝整形式であるか）を判定する方法を解説します。

問題の概要

たとえば、入力が s = "([()()]{[]})()" のような文字列だった場合、開き括弧と閉じ括弧が正しい順序で対応しているため、出力は True になります。逆に、閉じ括弧が先に現れたり、種類の異なる括弧が交差していたりすると False を返す必要があります。

アルゴリズムの考え方：スタックを使う

この問題はスタック（Stack）というデータ構造を使うことで効率的に解けます。手順は以下の通りです。

• 空のリストをスタックとして用意します。
• 閉じ括弧に対応する開き括弧をハッシュマップ（辞書）で定義します。「}」→「{」、「)」→「(」、「]」→「[」というペアです。
• 文字列 s の各文字 c を先頭から順に走査します。
  • c が閉じ括弧（'}])' のいずれか）の場合：
    • スタックが空、またはスタックの先頭要素が d[c]（対応する開き括弧）と一致しなければ False を返します。
    • 一致していれば、スタックから要素を取り出します（pop）。
  • それ以外（開き括弧）の場合：
    • その文字をスタックに積みます（push）。
• 最後に、スタックが空なら True、残りがあれば False を返します。

この方法により、括弧の入れ子構造や対応関係を O(n) の計算量で一度の走査でチェックできます。

実装例

実際のPythonコードを見てみましょう。

class Solution:
    def solve(self, s):
        stack = []
        d = {'}': '{', ')': '(', ']': '['}
        for c in s:
            if c in '}])':
                if not stack or stack[-1] != d[c]:
                    return False
                stack.pop()
            else:
                stack.append(c)
        return not stack

ob = Solution()
print(ob.solve("([()()]{[]})()"))

入力

"([()()]{[]})()"

出力

True

コードのポイント

• 辞書 d：閉じ括弧をキー、対応する開き括弧を値とすることで、対応確認を1行で行えます。
• stack[-1]：Pythonでは負のインデックスで末尾要素にアクセスできるため、スタックの先頭参照が簡単です。
• return not stack：スタックが空のリストなら not により True になります。開き括弧が余っていれば False を返せます。

この手法は、コンパイラの構文解析やエディタのコード補完機能など、実際のソフトウェア開発でも広く応用されている基本的なテクニックです。ぜひ理解しておきましょう。