Evaluate Reverse Polish Notation - Leetcode Solution

The idea of the Evaluate Reverse Polish Notation problem is to evaluate an arithmetic expression in Reverse Polish Notation (RPN), which can be done using a stack data structure. In RPN, operators come after their operands, so for example, the expression "3 + 4" in infix notation becomes "3 4 +" in RPN.

Here's a step-by-step solution to the problem:

1. Initialize an empty stack.
2. For each element in the input string:
   1. If the element is a number, push it onto the stack.
   2. If the element is an operator (+, -, *, /), pop two elements from the stack, apply the operator to them in postfix order (the second element popped is the right operand), and push the result onto the stack.
3. After processing all elements in the input string, the top of the stack should contain the final result. Pop it from the stack and return it.

Here's the implementation of this algorithm in Python:

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token.isdigit() or (token[0] == "-" and token[1:].isdigit()):
                stack.append(int(token))
            else:
                op2 = stack.pop()
                op1 = stack.pop()
                if token == "+":
                    stack.append(op1 + op2)
                elif token == "-":
                    stack.append(op1 - op2)
                elif token == "*":
                    stack.append(op1 * op2)
                else:
                    stack.append(int(op1 / op2))
        return stack.pop()

In this implementation, we first check whether each token is a number (positive or negative) by checking its first character. If so, we convert it to an integer and push it onto the stack. Otherwise, we assume it's an operator and pop two operands from the stack to apply the operator to. We use int(op1 / op2) instead of just op1 / op2 to handle integer division properly (e.g., 1 / -1 should be -1, not -1.0). Finally, we return the result by popping it from the stack.

This solution has a time complexity of O(n), where n is the length of the input string. We iterate over each element once and perform constant-time operations on the stack. It also has a space complexity of O(n) in the worst case if all elements are numbers and they're all pushed onto the stack.

1