Pythonで2つの括弧列の連結がバランスしているかどうかを判定する方法

問題の概要

「(」と「)」のみで構成された2つの括弧列 s と t が与えられたとき、それらを連結した文字列(s | t または t | s)がバランスの取れた括弧列になっているかどうかを判定します。

例えば、s = "()()))"、t = "()(()(" の場合、t | s の順序で連結すると "()(()(()()))" となり、これは正しく対応の取れた括弧列であるため、出力は True になります。

解決のアプローチ

この問題は、スタック(stack)を使った標準的な括弧チェックのアルゴリズムで解くことができます。手順は以下の通りです。

• is_balanced_parenthesis() 関数を定義します。この関数は文字列を引数として受け取ります。
• stack を空のリストとして初期化します。
• 文字列の先頭から末尾まで各文字を順に走査します。
  • 現在の文字が「(」の場合、スタックにプッシュします。
  • それ以外の場合(「)」の場合):
    • スタックが空であれば False を返します(対応する開き括弧が存在しないため)。
    • そうでなければ、スタックからポップします。
• 走査終了後、スタックが空でなければ False を返します。
• スタックが空であれば True を返します。

メインの処理では以下のように判定を行います。

• is_balanced_parenthesis(s + t) が True であれば、True を返します。
• そうでなければ、is_balanced_parenthesis(t + s) の結果を返します。

実装例

以下のコードで実際の動作を確認してみましょう。

def is_balanced_parenthesis(string):
    stack = []
    for i in range(len(string)):
        if string[i] == '(':
            stack.append(string[i])
        else:
            if len(stack) == 0:
                return False
            else:
                stack.pop()
    if len(stack) > 0:
        return False
    return True

def solve(s, t):
    if is_balanced_parenthesis(s + t):
        return True
    return is_balanced_parenthesis(t + s)

s = "()()))"
t = "()(()("
print(solve(s, t))

入力

"()()))", "()(()("

出力

True

まとめ

このように、2つの連結順序(s + t と t + s)のどちらか一方でもバランスが取れていれば True を返すことで、問題を解決できます。スタックを用いることで、各文字列のチェックは O(n) の計算量で効率的に処理でき、ネストの深い括弧列にも正確に対応できます。