Evaluate Reverse Polish Notation（逆波兰表达式求值）

题目 / Problem

中文： 给定一个字符串数组 tokens，它表示一个使用逆波兰表示法书写的算术表达式。计算该表达式并返回整数结果。

English: You are given an array of strings tokens representing an arithmetic expression in Reverse Polish Notation. Evaluate the expression and return its integer value.

规则 / Notes

有效运算符为 '+'、'-'、'*' 和 '/'。
The valid operators are '+', '-', '*', and '/'.
每个操作数可以是一个整数，也可以是另一个子表达式的结果。
Each operand may be an integer or the result of another expression.
两个整数相除时，结果始终向零截断。
Integer division always truncates toward zero.
不会发生除以零。
There will be no division by zero.
输入一定是合法的逆波兰表达式。
The input is guaranteed to be a valid Reverse Polish expression.
最终答案和所有中间结果都可以用 32 位整数表示。
The answer and every intermediate result fit in a 32-bit integer.

什么是逆波兰表示法？ / What Is Reverse Polish Notation?

普通的中缀表达式将运算符写在两个操作数之间：
An ordinary infix expression places an operator between its operands:

(2 + 1) × 3

逆波兰表达式也叫后缀表达式，将运算符写在操作数之后：
Reverse Polish Notation, also called postfix notation, places each operator after its operands:

2 1 + 3 *

因为操作顺序由排列位置唯一确定，所以不需要括号，也不需要考虑运算符优先级。
The token order uniquely determines evaluation order, so parentheses and operator-precedence rules are unnecessary.

示例 / Examples

Example 1

Input:  tokens = ["2","1","+","3","*"]
Output: 9

解释 / Explanation:
((2 + 1) * 3) = 9

Example 2

Input:  tokens = ["4","13","5","/","+"]
Output: 6

解释 / Explanation:
4 + (13 / 5) = 4 + 2 = 6

13 / 5 = 2.6，向零截断后为 2。
13 / 5 = 2.6, which truncates toward zero to 2.

Example 3

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

Output: 22

((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= 22

6 / -132 接近 -0.045，向零截断后是 0，不是 -1。
6 / -132 is approximately -0.045; truncation toward zero produces 0, not -1.

约束 / Constraints

1 <= tokens.length <= 10⁴
tokens[i] 是运算符 "+"、"-"、"*"、"/" 之一，或者是范围 [-200, 200] 内整数的字符串表示。
tokens[i] is one of "+", "-", "*", "/", or a string representing an integer in [-200, 200].

解题思路：栈 / Approach: Stack

从左到右遍历 tokens，使用栈保存暂时还没有被运算符使用的数值：
Traverse tokens from left to right and use a stack to store values not yet consumed by an operator:

如果当前 token 是数字，将它转换为数值并压入栈中。
If the current token is a number, convert it and push it onto the stack.
如果当前 token 是运算符，从栈中弹出两个操作数。
If the token is an operator, pop two operands from the stack.
对两个操作数执行运算，并将结果压回栈中。
Apply the operator and push the result back onto the stack.
遍历结束后，栈中唯一剩余的数就是表达式结果。
After traversal, the single remaining value is the expression result.

每个数字或子表达式的结果都会等待后续运算符消费，因此栈的后进先出顺序正好符合后缀表达式的计算方式。
Each number or subexpression result waits for a later operator, so the stack's last-in, first-out order exactly matches postfix evaluation.

操作数顺序 / Operand Order

遇到运算符时，先弹出的是右操作数，后弹出的是左操作数：
When an operator is encountered, the first popped value is the right operand and the second is the left operand:

const right = stack.pop();
const left = stack.pop();
const result = left operator right;

对于加法和乘法，顺序不会改变结果；但对于减法和除法，顺序非常重要：
Order does not affect addition or multiplication, but it is essential for subtraction and division:

["5", "2", "-"] → 5 - 2 = 3
["5", "2", "/"] → 5 / 2 = 2

JavaScript 实现 / JavaScript Implementation

/**
 * @param {string[]} tokens
 * @return {number}
 */
function evalRPN(tokens) {
  const stack = [];
  const operators = new Set(['+', '-', '*', '/']);

  for (const token of tokens) {
    if (!operators.has(token)) {
      stack.push(Number(token));
      continue;
    }

    const right = stack.pop();
    const left = stack.pop();

    switch (token) {
      case '+':
        stack.push(left + right);
        break;
      case '-':
        stack.push(left - right);
        break;
      case '*':
        stack.push(left * right);
        break;
      case '/':
        stack.push(Math.trunc(left / right));
        break;
    }
  }

  return stack.pop();
}

执行过程 / Walkthrough

以 tokens = ["4","13","5","/","+"] 为例：
For tokens = ["4","13","5","/","+"]:

Token	操作 / Action	栈 / Stack
`"4"`	压入 `4` / Push `4`	`[4]`
`"13"`	压入 `13` / Push `13`	`[4, 13]`
`"5"`	压入 `5` / Push `5`	`[4, 13, 5]`
`"/"`	`13 / 5 = 2`，压回 / Push result	`[4, 2]`
`"+"`	`4 + 2 = 6`，压回 / Push result	`[6]`

最终栈中只剩 6，因此返回 6。
Only 6 remains on the stack, so return 6.

Example 1 的栈变化 / Stack Changes for Example 1

token 2  → [2]
token 1  → [2, 1]
token +  → [3]
token 3  → [3, 3]
token *  → [9]

为什么使用 `Math.trunc()`？ / Why Use `Math.trunc()`?

题目要求除法向零截断：
The problem requires division to truncate toward zero:

 7 / 3 =  2.333... →  2
-7 / 3 = -2.333... → -2

JavaScript 的 Math.trunc() 会直接移除小数部分，正好符合要求。
JavaScript's Math.trunc() removes the fractional part and exactly matches this rule.

不能使用 Math.floor()，因为它会向负无穷方向取整：
Do not use Math.floor(), because it rounds toward negative infinity:

Math.trunc(-7 / 3) = -2  // 正确 / Correct
Math.floor(-7 / 3) = -3  // 错误 / Incorrect

复杂度 / Complexity

设 token 数量为 n。
Let n be the number of tokens.

时间复杂度：O(n)，每个 token 只处理一次。
Time: O(n), because every token is processed once.
空间复杂度：O(n)，最坏情况下栈中可能暂存大量操作数。
Space: O(n), because the stack may temporarily hold many operands.

递归结构与栈 / Expression Structure and the Stack

每遇到一个运算符，栈顶两个值就组成一个完整子表达式，并被一个结果替代：
Every operator combines the top two stack values into one complete subexpression and replaces them with its result:

left right operator → result

因此每处理一个二元运算符，栈大小净减少 1。合法表达式最终必然只留下一个结果。
Each binary operator reduces the stack size by one. A valid expression necessarily leaves exactly one result.

易错点 / Common Pitfalls

先弹出的是右操作数，后弹出的是左操作数。
The first popped value is the right operand; the second is the left operand.
减法必须计算 left - right，除法必须计算 left / right。
Subtraction must use left - right, and division must use left / right.
除法使用 Math.trunc()，不能使用 Math.floor()。
Use Math.trunc() for division, not Math.floor().
负数 token（例如 "-11"）是操作数，不是减法运算符。应通过完整字符串是否等于 "-" 来识别运算符。
A negative token such as "-11" is an operand, not the subtraction operator. Recognize operators by exact token equality.
token 是字符串，压栈前需要使用 Number(token) 转换为数值。
Tokens are strings and must be converted with Number(token) before being pushed.
逆波兰表达式不需要处理括号或运算符优先级。
Reverse Polish expressions require no parentheses or operator-precedence handling.

Evaluate Reverse Polish Notation