Trong giai đoạn sinh mã trung gian của một trình biên dịch, biểu thức số học thường được biểu diễn dưới dạng cây cú pháp trừu tượng (AST). Một cách quen thuộc để đánh giá AST là dùng ký pháp hậu tố (postfix / Reverse Polish Notation): duyệt cây theo thứ tự hậu thứ (postorder) sẽ cho ra dãy token hậu tố, và có thể đánh giá dãy này bằng một ngăn xếp (stack) mà không cần dựng cây tường minh.
Cho một biểu thức hậu tố gồm các số nguyên và các toán tử hai ngôi +,−,×,÷ (viết là + - * /), hãy tính giá trị của biểu thức.
Quy ước: phép chia a÷b lấy phần nguyên theo hướng làm tròn về 0 (truncation toward zero) giống C/C++, ví dụ −7÷2=−3 (không phải −4 như Python mặc định). Đề bảo đảm không có phép chia cho 0 và tại mọi bước ngăn xếp luôn đủ toán hạng để thực hiện phép toán.
Một dòng duy nhất chứa biểu thức hậu tố, các token (số nguyên hoặc toán tử) cách nhau bởi đúng một khoảng trắng. Số lượng token không vượt quá 2000.
In ra một số nguyên duy nhất — giá trị của biểu thức.
Ví dụ: với input 3 4 + (tương ứng biểu thức 3+4), output là 7.
Ví dụ:
Đầu vào:
3 4 +
Đầu ra:
7
Đầu vào:
5 1 2 + 4 * + 3 -
Đầu ra:
14
Đang tải editor...