Evaluate Reverse Polish Notation

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given array of expressions evaluate them and return final answer
• Example `[2, 3, +] = 5

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Whenever an operator is found, evaluate the last two values in the stack
• Input has valid expressions
• The division between two integers always truncates toward zero.

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Stack
• Array

Time & Space Complexity

• Time: $O(n)$ → Reason:
• Space: $O(n)$ → Reason:

Code

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

        for t in tokens:
            if t in ["+", "-", "*", "/"]:
                right = stack.pop()
                left = stack.pop()
                value = None
                if t == "+":
                    value = left + right
                elif t == "-":
                    value = left - right
                elif t == "*":
                    value = left * right
                else:
                    value = int(left / right)
                stack.append(value)
            else:
                stack.append(int(t))

        return stack[-1]

Common Mistakes / Things I Got Stuck On

• // floors the division
• int() always truncates towards zero