โปรแกรมขยายสตริงรูปแบบ n(t) ใน Python

คำอธิบายโจทย์

สตริง s เข้ารหัสเป็น n(t) แทน t ซ้ำ n ครั้ง t อาจเป็นสตริงธรรมดาหรือ n(t) ซ้อนกัน (recursive) หา decoded string

ตัวอย่าง

s = "3(pi)2(3(am))0(f)1(u)" → "pipipiamamamamamamu"

วิธีแก้ปัญหา

Recursive Descent Parsing:

1. Global index i เดินตามสตริง
2. parse(): อ่านจนกว่าจะเจอ ')' หรือจบสตริง
3. เจอตัวเลข: อ่านเลข d, ข้าม '(', เรียก parse() ได้ segment, ข้าม ')', append segment d ครั้ง
4. เจอตัวอักษร: append ตรงๆ
5. คืนค่า join ของ ans

โค้ด Python

class Solution:
    def solve(self, s):
        i = 0
        
        def parse():
            nonlocal i
            ans = []
            while i < len(s) and s[i] != ")":
                if s[i].isdigit():
                    d = 0
                    while s[i].isdigit():
                        d = 10 * d + int(s[i])
                        i += 1
                    i += 1  # skip '('
                    segment = parse()
                    i += 1  # skip ')'
                    ans.extend(segment for _ in range(d))
                else:
                    ans.append(s[i])
                    i += 1
            return "".join(ans)
        
        return parse()

ob = Solution()
s = "3(pi)2(3(am))0(f)1(u)"
print(ob.solve(s))

อินพุต

"3(pi)2(3(am))0(f)1(u)"

เอาต์พุต

pipipiamamamamamamu