leetcode: Evaluate Reverse Polish Notation

leetcode Evaluate Reverse Polish Notation Problem Description:

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

leetcode Evaluate Reverse Polish Notation Algorithm and Source Code:

Well, the common algorithm for evaluating reverse polish notation is by using a stack to keep all those operands: one pass scan all the tokens, if it is an operand, just push it into the stack, if it is an operator, then we need to pop put the top 2 operands in the stack and do calculating, r = a op b where a is the second popped out operand and b is the first on and op is the current operator, we then push the result r into the stack. For all the valid reverse polish notation, there would be only one number left in the stack after we finish scanning the input and that is the final result of the reverse polish notation we want. The accepted source code is as follows:

class Solution {
    public:
        bool isOperator(const string &str) {
            if (str.size() != 1) return false;

            char c = str[0];
            return '/' == c ||
                   '+' == c ||
                   '-' == c ||
                   '*' == c;
        }
        int calc(int a, int b, char c) {
            switch (c) {
                case '+':
                    return a + b;
                case '-':
                    return a - b;
                case '*':
                    return a * b;
                case '/':
                    if (0 == b)
                        throw overflow_error("divided by zero!");
                    return a / b;
                default:
                   throw invalid_argument("invalid operator!");
            }
        }

        int evalRPN(vector<string> &tokens) {
            stack<int> stk;
            int a, b;
            int operand;
            for (auto it = tokens.begin(); it != tokens.end(); ++it) {
                if (isOperator(*it)) {
                    if (stk.empty())
                        throw length_error("stack is already empty before popping out elements!");
                    a = stk.top(); stk.pop();

                    if (stk.empty())
                        throw length_error("stack is already empty before popping out elements!");
                    b = stk.top(); stk.pop();
                    stk.push(calc(b, a, (*it)[0]));
                }
                else {
                    operand = std::stoi(*it);
                    stk.push(operand);
                }
            }

            if (stk.size() != 1)
                throw length_error("stack size is not equal to one for getting the final result!");

            return stk.top();
        }
};

leetcode Evaluate Reverse Polish Notation Keys and Remarks:

Making the source code just accepted by the leetcode OJ is not that difficult for this problem.  But there are several key points worth noting in my code which I specifically designed to make the code more robust and this is more important to show during an coding interview in my opinion:

(1) when popping out the top 2 operands in the stack, don’t forget to check whether this stack is empty or not, since we are not sure about whether the reverse polish notation is a valid one or not.

(2) after finishing scanning the whole reverse polish notation, there could be only one number left in the stack if the reverse polish expression is a valid one, so don’t forget to check the size of the final stack, we get the correct result only when the size is one, in other cases, we need to report (e.g., throw an exception) that the input reverse polish notation might be invalid.

(3) don’t be mistaken on the order of the top 2 operands popped out from the stack to do the calculation: for example, if we want to do a / b, a should be second popped out operand, the result is obviously different if we mistakenly change the order.

(4) when calculation division like a /b, never forget to check if b is zero or not

(5) when converting from string to int, the atoi function is unsafe to use since it will not handle the invalid string correctly, use std::stoi instead which will throw an exception if the input string is an invalid string to be converted into a number. - never assume all the input would be valid. 

Written on July 17, 2014