Just use a stack to record the numbers. And evey time you encounter a operator, pop two numbers, calucate it and push it back.
Do not disorder the numbers. Otherwise you will get wrong answer when the operators are "-" and "/".
More harder part is how you get these incoming vector of strings from keyboard input, when it has parethesis involved.
1 class Solution { 2 public: 3 int getValue(int num1, int num2, string op) { 4 if (op == "+") { 5 return num1 + num2; 6 } else if (op == "-") { 7 return num1 - num2; 8 } else if (op == "*") { 9 return num1 * num2; 10 } 11 return num1 / num2; 12 } 13 int evalRPN(vector<string> &tokens) { 14 int len = tokens.size(); 15 if (len == 0) return 0; 16 stack<int> s; 17 for (int i = 0; i < len; i++) { 18 if (tokens[i] == "+" || 19 tokens[i] == "-" || 20 tokens[i] == "/" || 21 tokens[i] == "*") { 22 int num2 = s.top(); 23 s.pop(); 24 int num1 = s.top(); 25 s.pop(); 26 s.push(getValue(num1, num2, tokens[i])); 27 } else { 28 s.push(stoi(tokens[i])); 29 } 30 } 31 return s.top(); 32 } 33 };
LeetCode – Refresh – Evaluate Reverse Polish Notation
原文：http://www.cnblogs.com/shuashuashua/p/4349431.html