ตรวจสอบว่าการต่อกันของสองสตริงนั้นสมดุลหรือไม่ในPython

สมมติว่าเรามีวงเล็บสองลำดับ s และ t โดยมีเฉพาะอักขระเหล่านี้ '(' และ ')' เราต้องตรวจสอบว่าสตริงที่ต่อกันของ s และ t มีความสมดุลหรือไม่ การต่อข้อมูลสามารถทำได้โดย s | t or t | ส.

ดังนั้น หากอินพุตเป็น s ="()()))", t ="()(()(" ผลลัพธ์จะเป็น True เพราะถ้าเราเชื่อม t | s เข้าด้วยกัน เราจะได้ "() (()(()()))" ซึ่งมีความสมดุล

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน is_balanced_parenthesis() สิ่งนี้จะใช้สตริง
• stack :=รายการใหม่
• สำหรับ i ในช่วง 0 ถึงขนาดของสตริง ให้ทำ
  • ถ้า string[i] เหมือนกับ '(' แล้ว
    • ดันสตริง[i] ลงในสแต็ก
  • มิฉะนั้น
    • ถ้า stack ว่างเปล่า
      • คืนค่าเท็จ
    • มิฉะนั้น
      • ป๊อปจากสแต็ก
• ถ้า stack ไม่ว่างก็
  • คืนค่าเท็จ
• คืนค่า True
• จากวิธีหลัก ให้ทำดังนี้ -
• ถ้า is_balanced_parenthesis(s + t) เป็นจริง แล้ว
  • คืนค่า 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