Evaluate Reverse Polish Notation
Total Accepted: 24595 Total Submissions: 123794My Submissions
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
Have you been asked this question in an interview?
思路：栈的简单应用
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <cstdlib> using namespace std; class Solution {
public:
int evalRPN(vector<string> &tokens) {
stack<int> s;
string str;
int a, b; for (int i = ; i < tokens.size(); i++) {
str = tokens[i];
if (str == "+" || str == "-" || str == "*" ||
a = s.top(); s.pop();
b = s.top(); s.pop();
switch(str[]) {
case '+': s.push(b+a); break;
case '-': s.push(b-a); break;
case '*': s.push(b*a); break;
case '/': s.push(b/a); break;
}
}
else {
s.push(atoi(str.c_str()));
}
}
a = s.top();s.pop();
return a;
}
}; int main(int argc, char *argv[]) {
Solution* solution = new Solution();
vector<string> tokens;
tokens.push_back("");
tokens.push_back("");
tokens.push_back("+");
tokens.push_back("");
tokens.push_back("*"); cout << solution->evalRPN(tokens) << endl; vector<string> tokens2;
tokens2.push_back("");
tokens2.push_back("");
tokens2.push_back("");
tokens2.push_back("/");
tokens2.push_back("+");
cout << solution->evalRPN(tokens2) << endl;
return ;
}