algoadvance

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

Valid operators are +, -, *, and /. 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 will not be any division by zero operation.

Examples:

1. Input: ["2","1","+","3","*"], Output: 9
   • Explanation: ((2 + 1) * 3) = 9
2. Input: ["4","13","5","/","+"], Output: 6
   • Explanation: (4 + (13 / 5)) = 6
3. Input: ["10","6","9","3","+","-11","*","/","*","17","+","5","+"], Output: 22

---

Clarifying Questions:

1. Can the RPN expression contain invalid characters or operators?
   • No, the problem states the expression is always valid.
2. Do we need to handle floating-point division?
   • No, the problem specifies integer division that truncates toward zero.
3. Will the input size be reasonable to compute within a standard execution environment?
   • Yes.

---

Strategy:

1. Use a stack to process the RPN expression.
2. Iterate through each token in the input list:
   • If the token is an operand (integer), push it onto the stack.
   • If the token is an operator, pop the necessary number of operands from the stack, perform the operation, and push the result back onto the stack.
3. The final result will be the only element left in the stack.

Detailed Steps:

1. Initialize an empty stack.
2. Iterate through each element in the input list:
   • If the element is an integer, convert it to an integer and push it onto the stack.
   • If it is an operator, pop the top two elements from the stack, perform the corresponding operation, and push the result back onto the stack.
3. After processing all elements, the stack will have one element, which is the result of the RPN expression.

---

Code:

def evalRPN(tokens):
    stack = []
    
    for token in tokens:
        if token in "+-*/":
            # Pop the top two elements from the stack
            b = stack.pop()
            a = stack.pop()
            
            # Perform the operation
            if token == "+":
                result = a + b
            elif token == "-":
                result = a - b
            elif token == "*":
                result = a * b
            elif token == "/":
                # Python's division needs to be truncated towards zero
                result = int(a / b)
            
            # Push the result back onto the stack
            stack.append(result)
        else:
            # Push the number onto the stack
            stack.append(int(token))
    
    # The result is the last element in the stack
    return stack[0]

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

---

Time Complexity:

• Time Complexity: (O(n))
  • Each token is processed exactly once. Pushing and popping from the stack are (O(1)) operations.
• Space Complexity: (O(n))
  • The space used by the stack is proportional to the size of the input tokens.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?