Q31: Evaluate Reverse Polish Notation. - DSA Patterns (Multi-Lang)

In Simple Words: Operands are pushed onto a stack. When an operator is encountered, pop the top two operands, evaluate the expression (b op a), and push result back.

Time: $O(N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def evalRPN(tokens: list[str]) -> int:
    stack = []
    for t in tokens:
        if t == '+':
            stack.append(stack.pop() + stack.pop())
        elif t == '-':
            a, b = stack.pop(), stack.pop()
            stack.append(b - a)
        elif t == '*':
            stack.append(stack.pop() * stack.pop())
        elif t == '/':
            a, b = stack.pop(), stack.pop()
            stack.append(int(b / a))  # truncate towards zero
        else:
            stack.append(int(t))
    return stack[0]