150. Evaluate Reverse Polish Notation

🟠   🔖  栈 数组 数学  🔗 LeetCode

题目

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. 基本计算器
• 282. 给表达式添加运算符

- [224. 基本计算器](./0224.md)
- [282. 给表达式添加运算符](https://leetcode.com/problems/expression-add-operators)