LeetCode 227 Basic Calculator II - Example and Complexity Analysis

Trace "3+2*2".

Start: prevOp = '+', currNum = 0, stack = [].

Read '3': currNum = 3.

Read '+': prevOp is '+', push 3. Stack: [3]. Update prevOp = '+', currNum = 0.

Read '2': currNum = 2.

Read '*': prevOp is '+', push 2. Stack: [3, 2]. Update prevOp = '*', currNum = 0.

Read '2': currNum = 2.

End of string: prevOp is '*', pop 2, compute 2 * 2 = 4, push 4. Stack: [3, 4].

Sum stack: 3 + 4 = 7.

Single pass through the string. $O(n)$ time. Stack holds at most $O(n)$ numbers. $O(n)$ space.