Evaluate Reverse Polish Notation medium

Problem Statement

Evaluate the value of an arithmetic expression in Reverse Polish Notation (RPN).

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

• Division between two integers should truncate toward zero.
• The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.

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)) = 4 + 2 = 6

Steps

1. Initialize a stack: We'll use a stack to store operands.
2. Iterate through tokens: For each token:
   • If it's an operand (integer), push it onto the stack.
   • If it's an operator (+, -, *, /):
     • Pop the top two operands from the stack (let's call them operand2 and operand1, where operand1 is the topmost).
     • Perform the operation (operand1 operator operand2).
     • Push the result back onto the stack.
3. Return the final result: After processing all tokens, the only element left in the stack will be the final result.

Explanation

Reverse Polish Notation (RPN), also known as postfix notation, is a way of writing arithmetic expressions where the operators follow their operands. Instead of 2 + 3, you write 2 3 +. This eliminates the need for parentheses and operator precedence rules. The algorithm uses a stack because it naturally handles the order of operations in RPN. When an operator is encountered, the stack provides the operands in the correct order to perform the operation.

Code

def evalRPN(tokens):
    """
    Evaluates a Reverse Polish Notation (RPN) expression.

    Args:
        tokens: A list of strings representing the RPN expression.

    Returns:
        The integer result of the expression.
    """
    stack = []
    for token in tokens:
        if token.isdigit() or (token.startswith('-') and token[1:].isdigit()):  # Check for negative numbers
            stack.append(int(token))
        else:
            operand2 = stack.pop()
            operand1 = stack.pop()
            if token == '+':
                stack.append(operand1 + operand2)
            elif token == '-':
                stack.append(operand1 - operand2)
            elif token == '*':
                stack.append(operand1 * operand2)
            elif token == '/':
                # Handle integer division
                stack.append(int(operand1 / operand2))
    return stack[0]

Complexity

• Time Complexity: O(n), where n is the number of tokens. We iterate through the tokens once.
• Space Complexity: O(n) in the worst case, where n is the number of tokens. This is because the stack could potentially hold all the operands if the expression consists only of operands. In the best case (e.g., all operators), the space complexity would be O(1).