Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Máy tính biểu thức hậu tố (RPN)

    Cho một biểu thức số học viết dưới dạng hậu tố (Reverse Polish Notation - RPN), trong đó các toán hạng là số nguyên và các toán tử là +, -, *, /. Hãy viết một trình thông dịch (interpreter) sử dụng ngăn xếp (stack) để tính giá trị của biểu thức — đây là kỹ thuật kinh điển để thực thi mã trung gian dạng hậu tố trong một trình biên dịch.

    Duyệt các token từ trái sang phải theo đúng thứ tự xuất hiện:

    • Nếu token là một số nguyên (có thể có dấu - ở đầu để chỉ số âm), đẩy nó vào ngăn xếp.
    • Nếu token là một trong bốn toán tử, lấy ra hai giá trị trên đỉnh ngăn xếp — gọi bbb là giá trị lấy ra trước (đỉnh), aaa là giá trị lấy ra ngay sau đó — rồi tính a op ba \text{ op } ba op b và đẩy kết quả trở lại ngăn xếp.

    Phép chia / là phép chia lấy phần nguyên làm tròn về 0 (ví dụ 7/2=37/2=37/2=3, −7/2=−3-7/2=-3−7/2=−3). Dữ liệu vào đảm bảo không có phép chia cho 0, biểu thức luôn hợp lệ (đủ toán hạng cho mọi toán tử) và sau khi xử lý hết token, ngăn xếp chỉ còn đúng một giá trị — đó là kết quả cần in ra.

    • Định dạng đầu vào:

      Dòng đầu tiên chứa số nguyên TTT (1≤T≤1001 \le T \le 1001≤T≤100) — số biểu thức. Mỗi dòng trong TTT dòng tiếp theo là một biểu thức RPN, gồm các token cách nhau bởi đúng một khoảng trắng.

    • Định dạng đầu ra:

      In ra TTT dòng, mỗi dòng là kết quả (số nguyên) của biểu thức tương ứng theo đúng thứ tự.

      Ví dụ:

      Input:

      3
3 4 + 2 *
5 1 2 + 4 * + 3 -
6 2 /

      Output:

      14
14
3

    Ví dụ:

    Đầu vào:

    1
3 4 + 2 *

    Đầu ra:

    14

    Đầu vào:

    1
5 1 2 + 4 * + 3 -

    Đầu ra:

    14

    Đang tải editor...