题目描述
题目链接: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
,遇到数字不用管,遇到符号,则取前两个数字进行相应操作,然后将得出来的结果放入数组中继续遍历。符合这种操作的数据结构是栈。需要注意一点是做除法运算时,弹出的第一个数实际上是除数,然后才是被除数。代码如下:
#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