Evaluate Reverse Polish Notation: stack như implicit expression tree

Reverse Polish Notation có tuổi đời khá cao — nó là kiểu nhập mặc định trên các máy tính khoa học HP suốt nhiều thập kỷ, và hầu hết các compiler backend vẫn rút gọn biểu thức toán học về dạng này trong quá trình xử lý nội bộ. Lý do nó tồn tại dai dẳng là vì nó loại bỏ hoàn toàn các quy tắc operator precedence. Không cần theo dõi ngoặc, không cần nhớ * có độ ưu tiên cao hơn +. Thứ tự tính toán được mã hóa ngay trong thứ tự của các token.

Cho tokens = ["2","1","+","3","*"], kết quả là 9. Kiểm tra nhanh: (2 + 1) * 3. Toán tử + xuất hiện ngay sau hai toán hạng của nó; toán tử * xuất hiện sau cả hai toán hạng của nó (một trong số đó là kết quả của phép cộng). Thứ tự tính toán được gắn sẵn trong thứ tự các token.

Constraints và những gì chúng thực sự buộc bạn làm

Độ dài input tối đa là 10,000 token. Mỗi token hoặc là một trong bốn toán tử ("+", "-", "*", "/") hoặc là số nguyên trong khoảng [-200, 200]. Đề bài đảm bảo biểu thức luôn hợp lệ và không có phép chia cho 0.

Hai điều suy ra trực tiếp từ đây. Thứ nhất, đáp án và tất cả các phép tính trung gian đều nằm trong 32-bit integer — toán hạng trong [-200, 200] qua các phép tính cho phép không bao giờ overflow int. Không cần lo overflow. Thứ hai, không có sự mơ hồ nào khi phân biệt toán tử với số: một token số có thể bắt đầu bằng dấu trừ theo sau là chữ số (ví dụ "-11"), nhưng "-" đứng một mình luôn là toán tử trừ. Kiểm tra membership đơn giản với bốn chuỗi toán tử là đủ — không cần regex, không cần try/except khi parse int().

Giới hạn 10,000 có nghĩa O(n) hoàn toàn ổn. Nhưng constraint này gần như không liên quan vì chỉ có một thuật toán có ý nghĩa cho bài này, và nó O(n) theo mặc định.

Tại sao chỉ dùng stack, và không có gì khác

Insight cốt lõi là RPN là một post-order traversal được serialize của expression tree. ["2","1","+","3","*"] tương ứng với cây này:

Post-order traversal duyệt: left child, right child, root. Tức là: 2, 1, +, 3, * — đúng thứ tự token. Mỗi số là leaf; mỗi toán tử là internal node tiêu thụ hai con của nó.

Khi bạn evaluate một post-order traversal, bạn cần chỗ để giữ các kết quả subtree đã hoàn chỉnh trong khi chờ phần còn lại của biểu thức. Đó là stack. Mỗi lần gặp toán tử, bạn gộp hai con thành một kết quả duy nhất và push trở lại. Stack chính là expression tree được thu gọn thành một cấu trúc tuyến tính — bạn không bao giờ cần xây dựng cây tường minh. Stack là cái cây đó, chỉ được biểu diễn theo cách khác.

Không có cách brute force nào khả thi. Bất kỳ approach nào cố quét tìm toán tử và giải quyết tại chỗ đều là tái cài đặt một stack với bookkeeping tệ hơn. Thuật toán dùng stack vừa là giải pháp rõ ràng nhất, vừa là giải pháp tối ưu nhất. Khi cấu trúc bài toán là một dãy post-order, stack không phải là lựa chọn — nó là hình dạng của bài toán.

Thuật toán

Một lần duyệt. Một quy tắc.

• Token là số -> push vào stack.
• Token là toán tử -> pop hai cái, áp dụng toán tử, push kết quả.

Khi kết thúc, stack có đúng một phần tử. Đó là đáp án.

Thứ tự pop rất quan trọng. Pop đầu tiên cho bạn toán hạng bên phải; pop thứ hai cho bạn toán hạng bên trái. Điều này chỉ ảnh hưởng đến phép trừ và phép chia — left - right và right - left là hai thứ khác nhau — nhưng đây là loại lỗi âm thầm trôi qua với các ví dụ giao hoán rồi phá vỡ với ["4","3","-"].

from typing import List
 
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token in ('+', '-', '*', '/'):
                right = stack.pop()
                left = stack.pop()
                if token == '+':
                    stack.append(left + right)
                elif token == '-':
                    stack.append(left - right)
                elif token == '*':
                    stack.append(left * right)
                elif token == '/':
                    stack.append(int(left / right))
            else:
                stack.append(int(token))
        return stack[0]

public class Solution {
    public int EvalRPN(string[] tokens) {
        var stack = new Stack<int>();
        foreach (var token in tokens) {
            if (token is "+" or "-" or "*" or "/") {
                int right = stack.Pop();
                int left = stack.Pop();
                int result = token switch {
                    "+" => left + right,
                    "-" => left - right,
                    "*" => left * right,
                    "/" => left / right,
                    _ => throw new InvalidOperationException()
                };
                stack.Push(result);
            } else {
                stack.Push(int.Parse(token));
            }
        }
        return stack.Peek();
    }
}

Cả hai đều O(n) time và O(n) space. Stack giữ tối đa khoảng nửa số token tại bất kỳ thời điểm nào — worst case là khi tất cả số xuất hiện trước tất cả toán tử, cho bạn n/2 phần tử trong stack trước khi các toán tử bắt đầu hoạt động. Bạn không thể làm tốt hơn O(n) time vì buộc phải đọc từng token ít nhất một lần.

Độ phức tạp

Không có approach nào khác. Bất kỳ cách nào cố "duyệt token và giải quyết toán tử" đều chỉ là stack được ngụy trang với bookkeeping phức tạp hơn.

Bẫy phép chia trong Python

Đây là điểm khó thực sự duy nhất của bài, và nó cắn riêng Python.

Toán tử // của Python là floor division: nó làm tròn về phía negative infinity. -7 // 2 cho -4 trong Python, không phải -3. Đề bài yêu cầu truncation toward zero, tức là những gì integer division làm mặc định trong C, C++, Java, và C#.

Cách khắc phục là int(left / right). int() trên một float truncates toward zero vô điều kiện. int(-7 / 2) cho -3. Đây không phải điều kỳ lạ của Python — đó là hướng truncation của IEEE 754, và đây là thứ bạn cần ở bài này.

Bạn cũng có thể viết math.trunc(left / right), tường minh hơn. Tôi dùng int() vì ngắn gọn và ý định rõ ràng trong context. Cả hai đều được. Chỉ đừng dùng //.

C# thực hiện truncation toward zero tự nhiên cho integer division, nên không cần xử lý gì thêm.

Trace từng bước qua ví dụ đơn giản

tokens = ["2","1","+","3","*"]

token "2":  push 2              stack = [2]
token "1":  push 1              stack = [2, 1]
token "+":  right=1, left=2
            2 + 1 = 3, push 3   stack = [3]
token "3":  push 3              stack = [3, 3]
token "*":  right=3, left=3
            3 * 3 = 9, push 9   stack = [9]

return stack[0] = 9

Toán tử + kích hoạt và thu gọn cả hai toán hạng của nó thành một số 3 duy nhất. Số 3 đó nằm trong stack cho đến khi * cần nó như toán hạng trái cùng với số 3 tiếp theo. Stack phản ánh cái cây: nó giữ kết quả subtree + đang chờ (3) trong khi chờ right child của * đến.

Ví dụ thứ hai, ["4","13","5","/","+"], tương ứng với 4 + (13 / 5). Phép chia kích hoạt trước, cho int(13/5) = 2 (truncation toward zero). Sau đó cộng: 4 + 2 = 6.

Trace qua ví dụ khó

tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

Nhìn đáng sợ. Đi từng bước:

token "10":  push 10                           stack = [10]
token "6":   push 6                            stack = [10, 6]
token "9":   push 9                            stack = [10, 6, 9]
token "3":   push 3                            stack = [10, 6, 9, 3]
token "+":   right=3, left=9, 9+3=12          stack = [10, 6, 12]
token "-11": push -11                          stack = [10, 6, 12, -11]
token "*":   right=-11, left=12, 12*-11=-132  stack = [10, 6, -132]
token "/":   right=-132, left=6, int(6/-132)=0  stack = [10, 0]
token "*":   right=0, left=10, 10*0=0         stack = [0]
token "17":  push 17                           stack = [0, 17]
token "+":   right=17, left=0, 0+17=17        stack = [17]
token "5":   push 5                            stack = [17, 5]
token "+":   right=5, left=17, 17+5=22        stack = [22]

return 22

Khoảnh khắc then chốt là int(6 / -132). 6 / -132 xấp xỉ -0.0454, và int() truncates xuống 0 — không phải -1. Floor division sẽ cho -1 ở đây. Số 0 đó sau đó xóa sạch tất cả những gì nhân với 10, giải thích tại sao phần lớn biểu thức sụp đổ về không trước khi cộng +17 và +5 ở cuối.

Edge cases cần nhớ

Input một token ["42"]. Số được push vào stack, không có toán tử nào kích hoạt, và stack[0] trả về trực tiếp. Thuật toán xử lý điều này mà không cần special case nào — không có yêu cầu số token tối thiểu trước khi vòng lặp hoạt động đúng.

Token số âm như "-11". Chúng bắt đầu bằng dấu trừ nhưng không phải toán tử "-". Kiểm tra token in ('+', '-', '*', '/') nhận dạng đúng rằng "-11" không phải toán tử (nó có năm ký tự, không phải một), nên nó rơi vào int(token) và parse số nguyên âm đúng cách. Đây là lý do kiểm tra operator-set sạch hơn cách try: int(token) — cả hai đều parse được số âm, nhưng operator-set check tường minh và rõ ràng hơn.

Thứ tự toán hạng trong phép trừ. ["4","3","-"] phải cho 1, không phải -1. Luôn nhớ: pop đầu tiên là right, pop thứ hai là left. Đây là lỗi phổ biến nhất khi làm bài trong contest vì thứ tự pop có vẻ ngược.

Phép chia với toán hạng âm. ["6","-132","/"] phải cho 0, không phải -1. Python's // sẽ sai ở đây; int(left / right) mới đúng. Đáng test tường minh trước khi submit.

Nhận dạng pattern

Dùng stack khi bạn thấy:

• "evaluate expression" với format không tiêu chuẩn
• toán tử giải quyết hai toán hạng gần nhất vừa thấy
• ngoặc hay grouping mà context trước đó cần "chờ"
• bất kỳ cấu trúc tuần tự nào mà LIFO order khớp với thứ tự tính toán

RPN là ví dụ điển hình của cả bốn. Nếu bạn thấy "postfix expression" hay "Reverse Polish Notation" trong đề bài, giải pháp dùng stack là ngay lập tức. Cùng mental model áp dụng cho Valid Parentheses, Basic Calculator, và bất kỳ grammar nào có cấu trúc tính toán post-order. Tôi sẽ ship đúng đoạn code này — đó đã là implementation đơn giản nhất và đúng nhất của quy tắc evaluation, không có version khéo hơn nào để tìm.

Các bài liên quan

Valid Parentheses (20) — bài stack đơn giản nhất. Mỗi dấu mở ngoặc push vào; mỗi dấu đóng kiểm tra đỉnh và pop. Nếu bạn đã làm rồi, bạn đã dùng đúng mental model đó: stack theo dõi context cần được giải quyết, và một sự kiện (toán tử / dấu đóng ngoặc) giải quyết item gần nhất chưa được xử lý.

Basic Calculator (224) — hướng ngược lại. Cho một biểu thức infix tiêu chuẩn với ngoặc và +/-, evaluate nó. Một approach chuyển các token infix sang RPN bằng thuật toán shunting-yard theo operator precedence, rồi evaluate kết quả bằng đúng thuật toán trên. Stack xuất hiện ở cả hai giai đoạn.

Basic Calculator II (227) — infix không có ngoặc nhưng đủ bốn toán tử. Precedence quan trọng ở đây (* trước +), và stack được dùng để defer các toán tử có độ ưu tiên thấp hơn trong khi các toán tử độ ưu tiên cao hơn giải quyết trước. Twist ở đây: bạn không thể xử lý mỗi toán tử ngay lúc nhìn thấy nó nữa.

Basic Calculator III (772) — kết hợp cả hai: ngoặc và đầy đủ operator precedence. Phức tạp nhất trong series. RPN evaluation vẫn là cốt lõi, nhưng phần chuyển đổi shunting-yard không đơn giản. Nếu bạn có thể làm 150 gọn gàng và giải thích được cấu trúc post-order, bạn đã có nền tảng cho cả ba bài còn lại.