Problem Description

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.

Example 1:

  • Input: tokens = ["2","1","+","3","*"]
  • Output: 9
  • Explanation: ((2 + 1) * 3) = 9

Example 2:

  • Input: tokens = ["4","13","5","/","+"]
  • Output: 6
  • Explanation: (4 + (13 / 5)) = 6

My Idea

The idea here is to implement a stack that evaluates the expression. We read the tokens one by one and if it’s a number, we just add it to the stack. If it’s an operator, we pop the last two elements, perform the operation and add the result to the stack. In the end there is exactly one element left in the stack, which represents the result.

My solution

# Time Complexity: O(n)
def evalRPN(tokens: list[str]) -> int:
    s=[]
    for t in tokens:
        if t=='+':
            b=s.pop()
            a=s.pop()
            s.append(str(int(a)+int(b)))
        elif t=="-":
            b=s.pop()
            a=s.pop()
            s.append(str(int(a)-int(b)))
        elif t=="*":
            b=s.pop()
            a=s.pop()
            s.append(str(int(a)*int(b)))
        elif t=="/":
            b=s.pop()
            a=s.pop()
            s.append(str(int(float(a)/float(b))))
        else:
            s.append(t)
    return int(s[0])

print(evalRPN(["4","13","5","/","+"])) # 6