150. Evaluate Reverse Polish Notation
150. Evaluate Reverse Polish Notation
题目
You are given an array of strings tokens
that represents an arithmetic expression in a Reverse Polish Notation.
Evaluate the expression. Return an integer that represents the value of the expression.
Note that:
- The valid operators are
'+'
,'-'
,'*'
, and'/'
. - Each operand may be an integer or another expression.
- The division between two integers always truncates toward zero.
- There will not be any division by zero.
- The input represents a valid arithmetic expression in a reverse polish notation.
- The answer and all the intermediate calculations can be represented in a 32-bit integer.
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)) = 6
Example 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
Constraints:
1 <= tokens.length <= 10^4
tokens[i]
is either an operator:"+"
,"-"
,"*"
, or"/"
, or an integer in the range[-200, 200]
.
题目大意
给你一个字符串数组 tokens
,表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意:
- 有效的算符为
'+'
、'-'
、'*'
和'/'
。 - 每个操作数(运算对象)都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
解题思路
逆波兰表达式发明出来就是为了方便计算机运用「栈」进行表达式运算的,其运算规则如下:
按顺序遍历逆波兰表达式中的字符,如果是数字,则放入栈;如果是运算符,则将栈顶的两个元素拿出来进行运算,再将结果放入栈。对于减法和除法,运算顺序别搞反了,栈顶第二个数是被除(减)数。
所以这题很简单,直接按照运算规则借助栈计算表达式结果即可。
代码
/**
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function (tokens) {
let stack = [];
for (let i of tokens) {
if (i == "+") {
stack.push(stack.pop() + stack.pop());
} else if (i == "-") {
stack.push(-1 * stack.pop() + stack.pop());
} else if (i == "*") {
stack.push(stack.pop() * stack.pop());
} else if (i == "/") {
const temp = stack.pop();
stack.push((stack.pop() / temp) | 0);
} else {
stack.push(Number(i));
}
}
return stack.pop();
};
相关题目
- [224. 基本计算器](./0224.md)
- [282. 给表达式添加运算符](https://leetcode.com/problems/expression-add-operators)