Chương trình kiểm tra ngoặc tròn, vuông, nhọn cân bằng và đúng dạng trong Python

Cho chuỗi chỉ chứa các ngoặc tròn, vuông, nhọn. Kiểm tra xem chuỗi có cân bằng (well-formed) không.

Ví dụ

Đầu vào: "([()()]{[]})()".
Đầu ra: True.

Thuật toán

1. Khởi tạo stack rỗng và từ điển d = {'}':'{', ')':'(', ']':'['}.
2. Duyệt từng ký tự c:
   • Nếu c là ngoặc đóng: nếu stack rỗng hoặc đỉnh stack != d[c] -> False; else pop.
   • Ngược lại (ngoặc mở): push c vào stack.
3. Trả về True nếu stack rỗng, ngược lại False.

Mã nguồ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("([()()]{[]})()"))

Đầu vào / Đầu ra

Input: "([()()]{[]})()"
Output: True