Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation

 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

------------------------ thinking ---------------------------------------------------

using stack. The main thinking is right. But there are a lot of bugs during the implementation!!!

1. stack.back() and stack.pop_back() should be call in sequential!!

2. the tokens[i]'s size should be considered!! we have chances to get "+2" or "-4"

3. after if for size() > 1 checking, we should break!

--------------------------- codes ----------------------------------------------------

 class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        vector<int> stack;
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i].size() > 1) {
                //bug here
                stack.push_back(stoi(tokens[i]));
            } else {//bug here
                switch (tokens[i][0]) {
                    case '+':
                    {
                        int a = stack.back();
                        stack.pop_back();
                        int b = stack.back();
                        stack.pop_back();
                        stack.push_back(a + b);
                        break;
                    }
                    case '-':
                    {
                        int a = stack.back();
                        stack.pop_back();
                        int b = stack.back();
                        stack.pop_back();
                        stack.push_back(b - a);
                        break;
                    }
                    case '*':
                    {
                        int a = stack.back();
                        stack.pop_back();
                        int b = stack.back();
                        stack.pop_back();
                        stack.push_back(a * b);
                        break;
                    }
                    case '/':
                    {
                        int a = stack.back();
                        stack.pop_back();
                        int b = stack.back();
                        stack.pop_back();
                        stack.push_back(b / a);
                        break;
                    }
                    default:
                    {
                        int a = stoi(tokens[i]);
                        stack.push_back(a);
                        break;
                    }
                }
            }
        }
        return stack.back();
    }
};