0%

[Leetcode]150. Evaluate Reverse Polish Notation(C++)

题目描述

题目链接:150. Evaluate Reverse Polish Notation

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

Follow Up

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].

解题思路

从例子中可以看出,求解思路是:遍历 vector,遇到数字不用管,遇到符号,则取前两个数字进行相应操作,然后将得出来的结果放入数组中继续遍历。符合这种操作的数据结构是栈。需要注意一点是做除法运算时,弹出的第一个数实际上是除数,然后才是被除数。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stack>
#include <string>
#include <vector>

class Solution {
public:
int evalRPN(std::vector<std::string>& tokens) {
std::stack<int> nums;
int result = 0;
for (auto c : tokens) {
if (c == "+" || c == "-" || c == "/" || c == "*") {
performOperate(nums, c[0]);
} else {
nums.push(std::stoi(c));
}
}
return nums.top();
}

private:
void performOperate(std::stack<int>& nums, char op) {
int val1 = nums.top();
nums.pop();
int val2 = nums.top();
nums.pop();
int res = val2;
switch (op) {
case '+':
res += val1;
break;
case '-':
res -= val1;
break;
case '*':
res *= val1;
break;
case '/':
res /= val1;
break;
default:
break;
}
nums.push(res);
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

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

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions