Chương trình đánh giá biểu thức toán học không dùng hàm built-in trong Python

Cho chuỗi biểu thức toán học với (+, -, *, /), trong đó / là phép chia nguyên (integer division). Đánh giá và trả về kết quả không dùng hàm built-in (như eval).

Ví dụ: s = "2+3*5/7" → output 4 (vì 2 + ((3*5)/7) = 2 + 2 = 4).

Thuật toán Recursive Descent Parser (Parser đệ quy xuống):

• Đảo ngược chuỗi để xử lý từ trái sang phải dễ dàng (pop từ cuối)
• get_value(): đọc số (có thể có dấu -), trả về int
• get_term(): xử lý * và / (độ ưu tiên cao)
• Main loop: xử lý + và - (độ ưu tiên thấp)

Triển khai

from math import floor

class Solution:
    def solve(self, s):
        s = list(s[::-1])  # Đảo ngược, pop() lấy từ cuối = đọc trái→phải
        
        def get_value():
            sign = 1
            if s and s[-1] == "-":
                s.pop()
                sign = -1
            value = 0
            while s and s[-1].isdigit():
                value *= 10
                value += int(s.pop())
            return sign * value
        
        def get_term():
            term = get_value()
            while s and s[-1] in "*/":
                op = s.pop()
                value = get_value()
                if op == "*":
                    term *= value
                else:
                    term = floor(1.0 * term / value)  # Chia nguyên
            return term
        
        ans = get_term()
        while s:
            op, term = s.pop(), get_term()
            if op == "+":
                ans += term
            else:
                ans -= term
        return ans

ob = Solution()
s = "2+3*5/7"
print(ob.solve(s))

Đầu vào

"2+3*5/7"

Đầu ra

4

Giải thích: Parser xử lý thứ tự ưu tiên: * / trước, + - sau. floor(1.0 * term / value) thực hiện chia nguyên làm tròn xuống (floor division) cho cả số âm. Python // cũng làm floor division. Không hỗ trợ dấu ngoặc đơn.

Mở rộng: Để hỗ trợ dấu ngoặc, thêm get_factor() xử lý ( ... ) gọi đệ quy get_expr().