150. Evaluate Reverse Polish Notation

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/evaluate-reverse-polish-notation
• topics: Stack

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

• The valid operators are '+', '-', '*', and '/'.
• Each operand may be an integer or another expression.
• The division between two integers always truncates toward zero.
• There will not be any division by zero.
• The input represents a valid arithmetic expression in a reverse polish notation.
• The answer and all the intermediate calculations can be represented in a 32-bit integer.

Idea:

Use stack (deque in Python)

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = deque()
        for t in tokens:
            if t == '+':
                stack.append(stack.pop() + stack.pop())
            elif t == '-':
                stack.append(-stack.pop() + stack.pop())
            elif t == '*':
                stack.append(stack.pop() * stack.pop())
            elif t == '/':
                b = stack.pop()
                a = stack.pop()
                stack.append(int(a / b))
            else:
                stack.append(int(t))
        return stack.pop()