โปรแกรมนับจำนวนตัวอักษรในแต่ละระดับของวงเล็บใน Python

สมมติว่าเรามีสตริง s ประกอบด้วยตัวอักษร 3 ตัวคือ "X", "(", และ ")" สตริงมีวงเล็บสมดุล และระหว่างนั้นมี "X" อยู่ พร้อมกับวงเล็บซ้อนที่อาจเกิดขึ้นซ้ำ เราต้องหาจำนวน "X" ในแต่ละระดับของวงเล็บใน s เริ่มจากระดับตื้นสุดไปสู่ระดับลึกสุด

เช่น ถ้าอินพุตคือ s = "(XXX(X(XX))XX)" ผลลัพธ์จะเป็น [5, 1, 2]

ขั้นตอนการแก้ปัญหา

1. depth := -1
2. out := รายการใหม่
3. สำหรับแต่ละ c ใน s:
   • ถ้า c == "(" ให้ depth := depth + 1
   • มิฉะนั้นถ้า c == ")" ให้ depth := depth - 1
   • ถ้า depth == ขนาดของ out ให้เพิ่ม 0 เข้า out
   • ถ้า c == "X" ให้ out[depth] := out[depth] + 1
4. คืนค่า out

ตัวอย่างการใช้งาน

def solve(s):
    depth = -1
    out = []
    for c in s:
        if c == "(":
            depth += 1
        elif c == ")":
            depth -= 1
        if depth == len(out):
            out.append(0)
        if c == "X":
            out[depth] += 1
    return out

s = "(XXX(X(XX))XX)"
print(solve(s))

อินพุต

"(XXX(X(XX))XX)"

เอาต์พุต

[5, 1, 2]