Pythonで括弧のバランスが取れているかどうかをチェックするプログラム

文字列 s が、開き括弧「(」と閉じ括弧「)」のみで構成されているとします。ここでは、括弧の対応（バランス）が正しく取れているかどうかを判定するプログラムを作成します。

たとえば、入力が s = "(()())(())" の場合、すべての括弧が正しく入れ子になっているため、出力は True になります。一方、「)(」のように閉じ括弧が先に現れたり、開き括弧が余ったりする場合は False となります。

解き方のアプローチ

この問題は、整数型のカウンターを1つ用意するだけで効率的に解けます。手順は次のとおりです。

• カウンター num_open を 0 で初期化する。
• 文字列 s 内の各文字 c について、以下を繰り返す。
  • c が「(」の場合：num_open を +1 する。
  • c が「)」の場合：num_open を −1 し、結果が負になったら、対応する開き括弧がない閉じ括弧が現れたことを意味するため、直ちに False を返す。
• すべての文字を処理した後、num_open が 0 であれば True、そうでなければ False を返す。

つまり、開き括弧を「+1」、閉じ括弧を「−1」としてカウントし、「途中でマイナスにならないこと」と「最後にちょうど 0 に戻ること」の2つを確認するのがポイントです。

実装例

class Solution:
    def solve(self, s):
        num_open = 0
        for c in s:
            if c == '(':
                num_open += 1
            elif c == ')':
                num_open -= 1
                if num_open < 0:
                    return False
        return num_open == 0

ob = Solution()
print(ob.solve("(()())(())"))

入力

"(()())(())"

出力

True

よくある注意点

• 最後にカウンターが 0 かどうかの確認を忘れないこと。「((()」のように開き括弧が余っているケースを見逃してしまいます。
• 閉じ括弧の処理中にカウンターが 0 未満になった時点で、それ以降を調べる必要はありません。早期リターンすることで無駄な処理を省けます。

計算量

文字列を一度だけ走査するため、時間計算量は O(n)。使用するのはカウンター1つだけなので、空間計算量は O(1) です。非常に長い文字列でも高速に判定できる、シンプルかつ実用的なアルゴリズムです。