Mô phỏng thuật toán Tính biểu thức hậu tố (RPN)

Evaluate RPN · Nhóm: Ngăn xếp & Hàng đợi

Tính giá trị biểu thức viết ở dạng hậu tố bằng ngăn xếp chứa toán hạng.

Ý tưởng

Quét dãy token từ trái sang phải.

Gặp số thì đẩy vào ngăn xếp.

Gặp toán tử thì lấy ra hai số ở đỉnh, áp phép toán rồi đẩy kết quả trở lại.

Vì sao đúng

Dạng hậu tố đã mã hóa sẵn thứ tự ưu tiên, ngăn xếp giữ đúng các toán hạng chờ được kết hợp mà không cần dấu ngoặc.

Mã Python

def eval_rpn(tokens):
    stack = []
    for i, tok in enumerate(tokens):
        if tok in "+-*/":            # operator: pop two operands
            b = stack.pop()
            a = stack.pop()
            if tok == "+": stack.append(a + b)
            elif tok == "-": stack.append(a - b)
            elif tok == "*": stack.append(a * b)
            else: stack.append(a // b)
        else:                        # number: push it
            stack.append(int(tok))
    return stack[0]

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.