Tính Biểu Thức Hậu TốEvaluate Reverse Polish Notation
Hiểu bài
Cho mảng tokens là một biểu thức ở dạng hậu tố (Reverse Polish Notation): toán hạng đứng trước, toán tử đứng sau. Tính giá trị biểu thức. Toán tử gồm +, -, *, /; phép chia làm tròn về 0.
Ví dụ:
tokens = ["2", "1", "+", "3", "*"]
// nghĩa là (2 + 1) * 3 = 9
output = 9Hậu tố không cần dấu ngoặc: thứ tự token đã quy định thứ tự tính.
Lời giải tối ưu
O(n) time, O(n) spacefunction evalRPN(tokens: string[]): number {
const stack: number[] = []
const ops: Record<string, (a: number, b: number) => number> = {
'+': (a, b) => a + b,
'-': (a, b) => a - b,
'*': (a, b) => a * b,
'/': (a, b) => Math.trunc(a / b),
}
for (const t of tokens) {
if (t in ops) {
const b = stack.pop()!
const a = stack.pop()!
stack.push(ops[t](a, b))
} else {
stack.push(Number(t))
}
}
return stack[0]
}- Stack lưu các toán hạng đang chờ.
- Gặp số thì đẩy vào; gặp toán tử thì lấy ra 2 số gần nhất, tính, đẩy kết quả lại.
- Lưu ý thứ tự: số lấy ra sau (a) là toán hạng trái, lấy ra trước (b) là toán hạng phải — quan trọng với phép
-và/.
Chạy thử từng bước
- 1
tokens = ["2","1","+","3","*"]. "2" là số → đẩy vào. "1" là số → đẩy vào. stack = [2, 1].
token:"1"stack:[2,1] - 2
"+" là toán tử → lấy b=1 rồi a=2, tính a+b=3, đẩy 3 vào. stack = [3].
token:"+"a:2b:1pushed:3stack:[3] - 3
"3" là số → đẩy vào. stack = [3, 3].
token:"3"stack:[3,3] - 4
"" → lấy b=3 rồi a=3, tính 33=9, đẩy vào.
Hết token, đáp án là phần tử duy nhất còn lại: 9.
token:"*"a:3b:3pushed:9stack:[9]result:9
Trường hợp biên phải nhớ
Phép chia làm tròn về 0, KHÔNG về âm vô cực:
6 / -132 = 0,7 / -2 = -3(không phải -4).Dùng
Math.truncchứ khôngMath.floor.Số âm trong token ("-11") — phải parse bằng
Number(t), đừng nhầm dấu trừ của số âm với toán tử trừ (toán tử luôn là token riêng một ký tự).Thứ tự toán hạng: với "a b -" kết quả là a−b chứ không phải b−a; lấy phần tử pop sau làm vế trái.
Biểu thức chỉ có 1 số ["42"] → trả về 42, vòng lặp không gặp toán tử nào.