Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are + , – , * and /. 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 Easy question, just use a stack to store numbers. When it comes to a expression, pop 2 numbers and calculate them then push the result back.

C++ solution, 20ms


class Solution {
public:
        int numStack[10000];
        int numPtr = -1;

        int evalRPN(vector<string>& tokens) {
                for(int i = 0; i < tokens.size(); ++i)
                {
                        if((tokens[i][0] >= '0' && tokens[i][0] <= '9') || tokens[i].length() > 1)
                         numStack[++numPtr] = stoi(tokens[i]);
                        else
                        {
                                if(tokens[i] == "+")
                                    numStack[numPtr - 1] = numStack[numPtr - 1] + numStack[numPtr];
                                else if(tokens[i] == "-")
                                    numStack[numPtr - 1] = numStack[numPtr - 1] - numStack[numPtr];
                                else if(tokens[i] == "*")
                                    numStack[numPtr - 1] = numStack[numPtr - 1] * numStack[numPtr];
                                else numStack[numPtr - 1] = numStack[numPtr - 1] / numStack[numPtr];
                                --numPtr;
                        }
                    }
                return numStack[0];
        }
};

Leave a Reply

Your email address will not be published. Required fields are marked *