Chương trình đánh giá biểu thức S-expression dưới dạng chuỗi trong Python

Cho chuỗi s đại diện cho một S-expression. Cần tính giá trị của biểu thức và trả về kết quả dạng số nguyên. S-expression là biểu thức đệ quy bao gồm số hoặc phép toán trong ngoặc, ví dụ: (+ (- 3 2) (* 3 3)) tương ứng (3 - 2) + (3 * 3) = 10. Các phép toán hợp lệ: +, -, *, /.

Ví dụ: s = "(- (+ 3 2) 2)" → kết quả 3 vì ((3 + 2) - 2) = 3.

Giải thuật (Stack + Duyệt ngược)

1. Loại bỏ ngoặc đơn ( và ) khỏi chuỗi.
2. Tách chuỗi theo khoảng trắng thành danh sách token.
3. Duyệt token từ phải sang trái:
   • Nếu token là số (có thể âm) → push vào stack.
   • Nếu token là toán tử → pop 2 số num1, num2, thực hiện phép toán, push kết quả.
4. Phần tử cuối cùng trong stack là kết quả.

Ví dụ minh họa

class Solution:
    def solve(self, s):
        stack = []
        s = s.replace("(", "").replace(")", "")
        tokens = s.split()
        
        for token in reversed(tokens):
            if token.lstrip('-').isdigit():  # số (có thể âm)
                stack.append(int(token))
            else:  # toán tử
                num1 = stack.pop()
                num2 = stack.pop()
                if token == '+':
                    stack.append(num1 + num2)
                elif token == '-':
                    stack.append(num1 - num2)
                elif token == '*':
                    stack.append(num1 * num2)
                elif token == '/':
                    stack.append(int(num1 / num2))  # chia nguyên
        return stack.pop()

ob = Solution()
s = "(- (+ 3 2) 2)"
print(ob.solve(s))  # Output: 3

Đầu vào / Đầu ra

Input: "(- (+ 3 2) 2)"

Output: 3