Kiểm tra nối hai chuỗi ngoặc có cân bằng trong Python

Cho hai chuỗi ngoặc s và t chỉ chứa '(' và ')'. Kiểm tra xem chuỗi nối s+t hoặc t+s có cân bằng (balanced parentheses) hay không.

Ví dụ: s = "()()))", t = "()(()(" → nối t+s được "()(()(()()))" cân bằng → True.

Giải thuật

• Hàm is_balanced_parenthesis dùng stack: gặp '(' push, gặp ')' pop; nếu stack rỗng khi pop hoặc cuối không rỗng → không cân bằng.
• Kiểm tra s+t và t+s.

Mã ví dụ

def is_balanced_parenthesis(string):
    stack = []
    for ch in string:
        if ch == '(':
            stack.append(ch)
        else:
            if not stack:
                return False
            stack.pop()
    return len(stack) == 0

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

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

Đầu vào

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

Đầu ra

True