โปรแกรมหาจำนวนการแทรก Parentheses น้อยที่สุดเพื่อให้สมดุลด้วย Python

Parentheses string สมดุลถ้า: '(' ต้องมี '))' ติดกัน 2 ตัวตรงข้าม และ '(' ต้องอยู่ก่อน '))' นับจำนวน parentheses ต้องแทรกเพื่อให้สมดุล ใช้ตัวนับ o (pending '(') และ ret (insertions) scan ซ้าย-ขวา จัดการกรณี ')' เดี่ยวและ '))' คู่

อัลกอริทึม

1. o = 0 (pending open), ret = 0, i = 0
2. while i < n:
3. ถ้า s[i] == '(': o++
4. ถ้า s[i] == ')':
5. ถ้า i+1 < n และ s[i+1] == ')': // พบ '))'
6. ถ้า o == 0: ret++ (ต้องแทรก '(') มิฉะนั้น o--
7. i += 2 (ข้าม '))')
8. มิฉะนั้น: // ')' เดี่ยว
9. ret++ (ต้องแทรก ')') ถ้า o==0: ret++ (ต้องแทรก '(') มิฉะนั้น o--
10. i++
11. คืน ret + 2*o (ปิด '(' ที่เหลือด้วย '))' แต่ละอันต้องการ 2)

ตัวอย่างโค้ด

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))  # Output: 3

อินพุต/เอาต์พุต

Input: "(())))))"
Output: 3

ต้องแทรก 1 '(' และ 2 ')' เพื่อให้เป็น "(()))(()))" หรือรูปแบบสมดุลอื่น