Kiểm tra xem nối hai chuỗi có cân bằng hay không trong Python

Giả sử chúng ta có hai chuỗi ngoặc s và t chỉ có các ký tự này '(' và ')'. Chúng ta phải kiểm tra xem chuỗi liên kết của s và t có cân bằng hay không. Việc nối có thể được thực hiện bởi s | t hoặc t | s.

Vì vậy, nếu đầu vào giống như s ="() ()))", t ="() (() (", thì đầu ra sẽ là True vì nếu chúng ta nối t | s, thì chúng ta sẽ nhận được "() (() (() ())) ", được cân bằng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm is_balanced_parenthesis (). Điều này sẽ có chuỗi
• stack:=một danh sách mới
• đối với tôi trong phạm vi từ 0 đến kích thước của chuỗi, thực hiện
  • nếu chuỗi [i] giống với '(', thì
    • đẩy chuỗi [i] vào ngăn xếp
  • nếu không,
    • nếu ngăn xếp trống, thì
      • trả về Sai
    • nếu không,
      • bật ra từ ngăn xếp
• nếu ngăn xếp không trống, thì
  • trả về Sai
• trả về True
• Từ phương thức chính, hãy làm như sau -
• nếu is_balanced_parenthesis (s + t) là true, thì
  • trả về True
• return is_balanced_parenthesis (t + s)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

True