Evaluate Reverse Polish Notation

Bài toán

Tính giá trị của một biểu thức số học viết dưới dạng Ký pháp Ba Lan ngược (Reverse Polish Notation - RPN). Các toán tử hợp lệ: +, -, *, /. Phép chia phải bỏ phần thập phân (truncate toward zero).

Ví dụ:

text:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Giải thích: ((2 + 1) * 3) = 9

text:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Giải thích: (4 + (13 / 5)) = 6

Phân Tích & Tiếp Cận

Tại sao lại là RPN?

RPN là cách viết biểu thức mà toán tử nằm SAU các toán hạng (Postfix). Ví dụ bình thường (Infix): 1 + 2. RPN: 1 2 +. Lợi ích của RPN là không cần dấu ngoặc để xác định độ ưu tiên. Máy tính rất thích điều này.

Logic Stack

Duyệt qua danh sách tokens.
Nếu là Số: Push vào Stack.
Nếu là Toán tử (vd +):
- Pop 2 số trên đỉnh Stack ra (b là số vừa pop, a là số pop tiếp theo).
- Lưu ý thứ tự: a (trước), b (sau). Phép tính là a + b, a - b...
- Thực hiện phép tính.
- Push kết quả ngược lại vào Stack.
Cuối cùng, Stack sẽ còn lại duy nhất 1 số -> Đó là kết quả.

typescript:

function evalRPN(tokens: string[]): number {
    const stack: number[] = [];

    for (const token of tokens) {
        if (token === "+") {
            const b = stack.pop()!;
            const a = stack.pop()!;
            stack.push(a + b);
        } else if (token === "-") {
            const b = stack.pop()!;
            const a = stack.pop()!;
            stack.push(a - b);
        } else if (token === "*") {
            const b = stack.pop()!;
            const a = stack.pop()!;
            stack.push(a * b);
        } else if (token === "/") {
            const b = stack.pop()!;
            const a = stack.pop()!;
            // Math.trunc để cắt phần thập phân về 0 (đúng với yêu cầu, khác Math.floor với số âm)
            // vd: -1.5 -> trunc: -1, floor: -2
            stack.push(Math.trunc(a / b));
        } else {
            // Toán hạng (Số)
            stack.push(Number(token));
        }
    }

    return stack[0];
}

Time Complexity: $O(n)$.
Space Complexity: $O(n)$.

Ứng Dụng Thực Tế

Đây chính là cách các trình biên dịch (Compiler) và máy tính bỏ túi hoạt động. Hầu hết các ngôn ngữ lập trình đều convert biểu thức a + b * c sang dạng cây hoặc Postfix (RPN) trước khi thực thi.