โปรแกรมประเมินค่า S-Expression เป็นสตริงใน Python

ได้รับสตริง s ที่เป็น S-Expression (นิพจน์แบบ Lisp) ต้องประเมินค่าและคืนผลลัพธ์เป็นจำนวนเต็ม ตัวดำเนินการที่รองรับ: +, -, *, /

ตัวอย่าง

อินพุต: "(- (+ 3 2) 2)"

ผลลัพธ์: 3 เพราะ ((3 + 2) - 2) = 3

แนวทางแก้ปัญหา

ใช้ Stack ประมวลผลจากขวาไปซ้าย (Reverse Polish Notation style):

1. ลบวงเล็บออก แล้วแยกทอเคนด้วยช่องว่าง
2. วนลูปทอเคนจากท้ายไปหัว:
   • ถ้าเป็นตัวเลข (รวมลบ) → push เข้า stack
   • ถ้าเป็นตัวดำเนินการ → pop 2 ตัว คำนวณ แล้ว push ผลลัพธ์กลับ
3. ค่าสุดท้ายใน stack คือคำตอบ

การใช้งาน (Python)

class Solution:
    def solve(self, s):
        stack = []
        s = s.replace("(", "").replace(")", "")
        tokens = s.split()
        
        for token in reversed(tokens):
            if token.lstrip('-').isdigit():  # รองรับเลขลบ
                stack.append(int(token))
            else:
                if len(stack) >= 2:
                    a, b = stack.pop(), stack.pop()
                    if token == '+': stack.append(a + b)
                    elif token == '-': stack.append(a - b)
                    elif token == '*': stack.append(a * b)
                    elif token == '/': stack.append(int(a / b))
        
        return stack.pop()

# ทดสอบ
ob = Solution()
print(ob.solve("(- (+ 3 2) 2)"))  # Output: 3

หมายเหตุ

รุ่นต้นฉบับมีบั๊กเล็กน้อยในการจัดการตัวเลขหลายหลักและเลขลบ รุ่นนี้แก้ไขแล้วโดยใช้ lstrip('-').isdigit()