solution

Trong giai đoạn sinh mã, một biểu thức số học thường được dịch sang dạng hậu tố (postfix) rồi thực thi bởi một máy ảo ngăn xếp (stack machine): khi gặp toán hạng, máy đẩy (PUSH) giá trị vào ngăn xếp; khi gặp toán tử hai ngôi, máy lấy ra (POP) hai giá trị trên đỉnh, tính toán rồi đẩy kết quả trở lại.

Cho một biểu thức hậu tố hợp lệ gồm các số nguyên và các toán tử $+, -, \times, \div$ (ký hiệu + - * /), hãy mô phỏng máy ảo ngăn xếp để tính giá trị cuối cùng.

Quy ước: với toán tử OP, nếu hai giá trị lấy ra theo thứ tự POP là $b$ rồi $a$ (tức $a$ được đẩy vào trước $b$), kết quả đẩy lại là $a \; OP \; b$. Phép chia / luôn là phép chia hết (đề bảo đảm $a$ chia hết cho $b$, $b \neq 0$), lấy thương đúng theo nghĩa toán học.

Ví dụ: với biểu thức hậu tố 5 1 2 + 4 * + 3 -, máy ảo thực hiện lần lượt: đẩy 5, 1, 2; gặp + tính $1+2=3$; đẩy 4; gặp * tính $3 \times 4 = 12$; gặp + tính $5+12=17$; đẩy 3; gặp - tính $17-3=14$. Kết quả cuối cùng là $14$.