LeetCode 150 Evaluate Reverse Polish Notation - Example and Complexity Analysis

Trace ["4", "13", "5", "/", "+"].

Read "4": push 4. Stack: [4].

Read "13": push 13. Stack: [4, 13].

Read "5": push 5. Stack: [4, 13, 5].

Read "/": pop 5 and 13. Compute 13 / 5 = 2. Push 2. Stack: [4, 2].

Read "+": pop 2 and 4. Compute 4 + 2 = 6. Push 6. Stack: [6].

Return 6.

Single pass through tokens. $O(n)$ time. Stack holds at most $n/2$ numbers. $O(n)$ space.