LeetCode: 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

---

We can use a stack to help do the calculation. If current token is an operator, we can pop two operands from the stack and calculate the result and push it back to the stack.

C++ Code:

/*
 * func: evaluate_RPN
 * goal: calculate the result of the input reverse polish notation
 * @param tokens: input tokens list
 * return: the result
 */
int evaluate_RPN(vector<string> &tokens){
    stack<int> evaluation_helper;
    for(const string &str : tokens){
        if(str == "+"){
            int operand_1 = evaluation_helper.top();
            evaluation_helper.pop();
            int operand_2 = evaluation_helper.top();
            evaluation_helper.pop();
            evaluation_helper.emplace(operand_1 + operand_2);
        }else if(str == "-"){
            int operand_1 = evaluation_helper.top();
            evaluation_helper.pop();
            int operand_2 = evaluation_helper.top();
            evaluation_helper.pop();
            evaluation_helper.emplace(operand_2 - operand_1);
        }else if(str == "*"){
            int operand_1 = evaluation_helper.top();
            evaluation_helper.pop();
            int operand_2 = evaluation_helper.top();
            evaluation_helper.pop();
            evaluation_helper.emplace(operand_2 * operand_1);
        }else if(str == "/"){
            int operand_1 = evaluation_helper.top();
            evaluation_helper.pop();
            int operand_2 = evaluation_helper.top();
            evaluation_helper.pop();
            evaluation_helper.emplace(operand_2 / operand_1);
        }else{
            evaluation_helper.emplace(atoi(str.c_str()));
        }
    }
    if(evaluation_helper.size() == 1){
        return evaluation_helper.top();
    }else{
        return 0;
    }
}

Python Code:

# func: calculate the result of input reverse polish notation
# @param tokens: input token list
# @return: result
def evaluate_RPN(tokens):
    stack = []
    for token in tokens:
        if token == "+":
            operand_1 = stack.pop(-1)
            operand_2 = stack.pop(-1)
            stack.append(operand_1 + operand_2)
        elif token == "-":
            operand_1 = stack.pop(-1)
            operand_2 = stack.pop(-1)
            stack.append(operand_2 - operand_1)
        elif token == "*":
            operand_1 = stack.pop(-1)
            operand_2 = stack.pop(-1)
            stack.append(operand_1 * operand_2)
        elif token == "/":
            operand_1 = stack.pop(-1)
            operand_2 = stack.pop(-1)
            if operand_2 * operand_1 < 0:
                stack.append(abs(operand_2) / abs(operand_1) * -1)
            else:
                stack.append(operand_2 / operand_1)
        else:
            stack.append(int(token))
    if len(stack) == 1:
        return stack[0]
    else:
        return 0