题目描述
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
NOTE
- Division between two integers should truncate toward zero.
- The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.
Example1:
Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9
Example2:
Input: ["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
解题思路
- 栈的应用，四则运算
- 要理解清楚题意
class Solution {
public:
int evalRPN(vector<string>& tokens) {
if(tokens.size() == 0){
return 0;
}
stack<long long> s;
for(int i = 0; i < tokens.size(); i++){
if(isNum(tokens[i])){
s.push(stoll(tokens[i]));
}else if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
long long num1 = s.top();
s.pop();
long long num2 = s.top();
s.pop();
if(tokens[i] == "+"){
s.push(num1 + num2);
}
else if(tokens[i] == "-"){
s.push(num2 - num1);
}else if(tokens[i] == "*"){
s.push(num1 * num2);
}else if(tokens[i] == "/"){
s.push(num2 / num1);
}
}
}
return s.top();
}
bool isNum(string s){
return s != "+" && s != "-" && s != "*" && s != "/";
}
};
