0%

### 题目描述

Evaluate the value of an arithmetic expression in `Reverse Polish Notation`.

Valid operators are `+`, `-`, `*`, and `/`. Each operand may be an integer or another expression.

### 例子

#### 例子 1

Input: `tokens = ["2","1","+","3","*"]`
Output: `9`
Explanation: `((2 + 1) * 3) = 9`

#### 例子 2

Input: `tokens = ["4","13","5","/","+"]`
Output: `6`
Explanation: `(4 + (13 / 5)) = 6`

#### 例子 3

Input:`tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]`
Output: `22`
Explanation:
`((10 * (6 / ((9 + 3) * -11))) + 17) + 5`
`= ((10 * (6 / (12 * -11))) + 17) + 5`
`= ((10 * (6 / -132)) + 17) + 5`
`= ((10 * 0) + 17) + 5`
`= (0 + 17) + 5`
`= 17 + 5`
`= 22`

### Note

• Division between two integers should truncate toward zero.
• It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

### Constraints

• `1 <= tokens.length <= 10^4`
• `tokens[i]` is either an operator: `"+"`, `"-"`, `"*"`, or `"/"`, or an integer in the range `[-200, 200]`.

### 解题思路

• 时间复杂度: `O(n)`
• 空间复杂度: `O(n)`

GitHub 代码同步地址： 150.EvaluateReversePolishNotation.cpp

GitHub: Leetcode-C++-Solution