Evaluate Reverse Polish Notation
Total Accepted: 5898 Total
Submissions: 31322My 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
本题就是考查栈的应用。
注意细节,很容易过。 3星级的题目吧。
1 要push入结果
2 两个数的计算顺序不能错,否则答案错误
class Solution { public: int evalRPN(vector<string> &tokens) { if (tokens.size() < 1) return 0; stack<int> stk; for (int i = 0; i < tokens.size(); i++) { if (!isOperand(tokens[i])) stk.push(stoi(tokens[i])); else { int b = stk.top(); stk.pop(); int a = stk.top(); stk.pop(); int result = evaluate(a, b, tokens[i]); stk.push(result); } } return stk.top(); } bool isOperand(const string &s) const { if (s == "+" || s == "-" || s == "*" || s == "/") return true; return false; } int evaluate(int a, int b, string &op) { if (op == "+") return a+b; if (op == "-") return a-b; if (op == "*") return a*b; return a/b; } };
//2014-2-19 update int evalRPN(vector<string> &tokens) { stack<int> stk; for (int i = 0; i < tokens.size(); i++) { if (isOperand(tokens[i])) { int b = stk.top(); stk.pop(); int a = stk.top(); stk.pop(); int t = evaluate(tokens[i], a, b);//a b 顺序不能搞错!且需要push入结果 stk.push(t); } else stk.push(stoi(tokens[i])); } return stk.top(); } bool isOperand(string &c) { return c == "+" || c == "-" || c == "*" || c == "/"; } int evaluate(string &op, int a, int b) { if (op == "+") return a+b; if (op == "-") return a-b; if (op == "*") return a*b; return a/b; }