โปรแกรมค้นหาการแทรกขั้นต่ำเพื่อปรับสมดุลสตริงในวงเล็บโดยใช้ Python

สมมติว่าเรามีสตริง s ที่มีวงเล็บเปิดและปิด '(' และ ')' เราสามารถพูดได้ว่าสตริงวงเล็บมีความสมดุลเมื่อ −

วงเล็บซ้าย '(' มีวงเล็บ 2 วงเล็บขวาติดกัน '))'
วงเล็บซ้าย '(' ต้องอยู่ข้างหน้าวงเล็บขวาสองอันที่ต่อเนื่องกัน '))'

ตัวอย่างเช่น "())", "())(())))" มีความสมดุล แต่ ")()", "()))" ไม่สมดุล ถ้าเรามีสตริงดังกล่าว เราต้องนับจำนวนวงเล็บ (เปิดหรือปิด) เพื่อให้สตริงมีความสมดุล

ดังนั้น หากอินพุตเป็น s ="(()))))" ผลลัพธ์จะเป็น 1 เพราะถ้าเราแยกมันออกมา เราจะได้ "( ()) )) ))" ดังนั้นเราจึงต้องการ วงเล็บซ้ายหนึ่งอันเพื่อสร้างสตริง "( ()) ()) ))" เพื่อให้สมดุล

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

:=0, n :=ขนาดของ s
ret :=0, ผม :=0
ในขณะที่ฉัน
- ถ้า s[i] เหมือนกับ '(' แล้ว
:=o + 1
- มิฉะนั้น
  - ถ้า i + 1
    - ถ้า o เป็น 0 แล้ว
      - ret :=ret + 1
    - มิฉะนั้น
:=o - 1
- ผม :=ผม + 1
- มิฉะนั้น
  - ret :=ret + 1
  - ถ้า o เป็น 0 แล้ว
    - ret :=ret + 1
  - มิฉะนั้น
:=o - 1
- ผม :=ผม + 1
รีเทิร์น + 2 * o

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

def solve(s):
   o = 0
   n = len(s)
   ret = 0
   i = 0
   while i < n:
      if s[i] == '(':
         o += 1
      else:
         if i + 1 < n and s[i + 1] == ')':
            if not o:
               ret += 1
            else:
               o -= 1
               i += 1
         else:
            ret += 1
            if not o:
               ret += 1
            else:
               o -= 1
      i += 1
   return ret + 2 * o
s = "(())))))"
print(solve(s))

อินพุต

"(())))))"