Basic Calculator III - Solution & Explanation

Problem Overview: You need to evaluate a string arithmetic expression containing integers, operators +, -, *, /, and nested parentheses. The expression may include spaces, and operator precedence must be respected while correctly handling parentheses.

Approach 1: Recursive Expression Evaluation (O(n) time, O(n) space)

This approach processes the string using recursion to evaluate sub-expressions inside parentheses. Iterate through the characters, build numbers digit by digit, and apply operators when encountered. When you see (, recursively evaluate until the matching ). A stack tracks intermediate values so multiplication and division can be applied immediately while addition and subtraction defer until summation. Each character is processed once, giving O(n) time and recursion/stack usage of O(n) space.

Approach 2: Two-Stack Expression Parsing (O(n) time, O(n) space)

This classic expression evaluator uses one stack for numbers and another for operators. Iterate through the string, push numbers to the value stack, and push operators while respecting precedence rules. Before pushing a new operator, resolve any operators with higher or equal precedence already on the stack. Parentheses trigger evaluation until the matching opening bracket. This mirrors the Shunting Yard technique and handles precedence cleanly using explicit operator comparisons.

Approach 3: Single Stack with Precedence Handling (O(n) time, O(n) space)

The optimized solution scans the string once and uses a single stack to manage numbers. Track the previous operator and apply logic when a new operator or closing parenthesis appears. Push numbers for + and -, but immediately compute * or / with the stack top. When encountering (, recursively evaluate the inner expression and treat the returned value as the current number. This approach combines operator precedence and parenthesis handling efficiently while keeping the code concise.

These solutions rely heavily on concepts from stack-based parsing and recursive expression evaluation from recursion. Since the problem operates on characters and tokens inside an expression string, familiarity with string traversal is essential.

Recommended for interviews: The single-stack recursive evaluation is what interviewers typically expect. It shows you understand operator precedence, expression parsing, and stack-based evaluation in linear time. Mentioning the two-stack parsing method first demonstrates foundational understanding, but implementing the optimized single-pass approach proves stronger problem-solving ability.