Evaluate Reverse Polish Notation

Clarify the problem:

• The problem requires us to evaluate an arithmetic expression in Reverse Polish Notation (RPN).
• Reverse Polish Notation is a mathematical notation in which every operator follows all of its operands.
• We need to implement a function that takes an RPN expression as input and returns the result of evaluating that expression.

Analyze the problem:

• Input: A list of strings representing the RPN expression.
• Output: The result of evaluating the RPN expression.
• Constraints:
  • The given RPN expression is always valid and contains only integers and operators.
  • The operators include "+", "-", "*", and "/".
  • Division between two integers should truncate toward zero.

Design an algorithm:

• We can use a stack to evaluate the RPN expression.
• Iterate through each element in the input list:
  • If the element is an operator, pop the last two operands from the stack, perform the operation, and push the result back to the stack.
  • If the element is an operand, convert it to an integer and push it to the stack.
• At the end, the stack should contain only one element, which is the final result of the RPN expression.

Explain your approach:

• We will implement a function called evalRPN to solve the problem.
• The function will take a list of strings representing the RPN expression as input.
• We will use a stack to store the intermediate results.
• We iterate through each element in the input list and handle operators and operands accordingly.
• After iterating through all elements, the stack should contain the final result, which we will return.

Write clean and readable code:

python

def evalRPN(tokens):
    stack = []
    operators = {"+", "-", "*", "/"}

    for token in tokens:
        if token in operators:
            operand2 = stack.pop()
            operand1 = stack.pop()

            if token == "+":
                result = operand1 + operand2
            elif token == "-":
                result = operand1 - operand2
            elif token == "*":
                result = operand1 * operand2
            elif token == "/":
                result = int(operand1 / operand2)

            stack.append(result)
        else:
            stack.append(int(token))

    return stack[0]

Test your code:

python

print(evalRPN(["2", "1", "+", "3", "*"]))            # Output: 9
print(evalRPN(["4", "13", "5", "/", "+"]))           # Output: 6
print(evalRPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]))  # Output: 22

Explanation:

• We test the solution with different RPN expressions to verify its correctness.
• In the first test case, the RPN expression is "2 1 + 3 *", which can be evaluated as (2 + 1) * 3 = 9.
• In the second test case, the RPN expression is "4 13 5 / +", which can be evaluated as 4 + (13 / 5) = 6.
• In the third test case, the RPN expression is "10 6 9 3 + -11 * / * 17 + 5 +", which can be evaluated as 10 * ((6 / (9 + 3)) * -11) + 17 + 5 = 22.

Optimize if necessary:

• The solution does not require further optimization as it already solves the problem efficiently.

Handle error cases:

• The code assumes that the input follows the problem constraints and does not explicitly handle invalid input cases, such as empty input or invalid RPN expressions. Handling such cases can be added to the code as needed.

Discuss complexity analysis:

• Let N be the length of the input list (number of tokens).
• The algorithm iterates through each token in the input list, resulting in a time complexity of O(N).
• The space complexity is O(N) as well since we use a stack to store the intermediate results.