Intuition

The Reverse Polish Notation is nothing but Postfix expression, where operands are followed by operands in an expression. In a valid postfix expression, whenever an operator is encountered two leading operands are evaluated with the operator and the result is replaced in the expression.

Approach

Here, I have used Monotonic Stack to evaluate the postfix expression. The logic is simple:

Iterate through the expression linearly If a number is encountered, push into the stack If an operator is encountered, pop the top elements from stack and assign the topmost number as RHS and the previous number as LHS Evaluate the expression based on the operator (+, — ,* , /) and push the result into stack Repeat the same process, until the expression is completely traversed. At the end return stack[0] which is the final result after evaluating all the numbers in the expression.

Complexity

Time complexity: O(N)

Space complexity: O(k)

Code

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        if (len(tokens) == 1):
            return int(tokens[0])

        stack = []
        top = -1
        operators = "+-*/"

        for ele in tokens:
            if (ele in operators):
                rhs = int(stack.pop())
                lhs = int(stack.pop())
                res = 0
                if (ele == "+"):
                    res = lhs+rhs
                elif (ele == "-"):
                    res = lhs-rhs
                elif (ele == "*"):
                    res = lhs*rhs
                elif (ele == "/"):
                    res = int(lhs/rhs)
                stack.append(res)
            else:
                top += 1
                stack.append(ele)
        
        return stack[0]