Watch 10 video solutions for Basic Calculator, a hard level problem involving Math, String, Stack. This walkthrough by Cracking FAANG has 34,883 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = "1 + 1" Output: 2
Example 2:
Input: s = " 2-1 + 2 " Output: 3
Example 3:
Input: s = "(1+(4+5+2)-3)+(6+8)" Output: 23
Constraints:
1 <= s.length <= 3 * 105s consists of digits, '+', '-', '(', ')', and ' '.s represents a valid expression.'+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).'-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).Problem Overview: Evaluate a string expression containing integers, +, -, parentheses, and spaces. You must correctly handle nested parentheses and operator precedence while scanning the string.
Approach 1: Iterative Stack Evaluation (O(n) time, O(n) space)
This approach scans the expression from left to right while maintaining the current number, current sign, and a running result. When encountering digits, you build the number. When encountering + or -, you finalize the previous number by applying the stored sign. Parentheses introduce a new evaluation scope, so you push the current result and sign onto a stack. When a closing parenthesis appears, compute the inner expression and combine it with the previous state popped from the stack. Each character is processed once, giving O(n) time complexity and O(n) auxiliary space for nested parentheses.
Approach 2: Recursive Expression Parsing (O(n) time, O(n) space)
The recursive method treats each parenthesized expression as a subproblem. While iterating through the string, digits build numbers and signs update the running result. When an opening parenthesis appears, recursively evaluate the substring until the matching closing parenthesis. The returned value becomes the current number in the outer expression. This mirrors how compilers parse arithmetic expressions and is a natural fit for problems involving nested structures in a string. The recursion stack may grow up to the depth of parentheses, so space complexity is O(n) in the worst case.
Recommended for interviews: The iterative stack solution is usually expected because it demonstrates strong control over expression parsing and stack-based state management. Interviewers often look for the insight that each parenthesis creates a new evaluation frame that can be saved and restored with a stack. The recursive approach is equally valid and sometimes easier to reason about, especially if you already think of the expression as nested subproblems. Both rely on concepts from math, stack, and recursion, and both achieve optimal O(n) time complexity since every character in the expression is processed exactly once.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Stack Evaluation | O(n) | O(n) | General case with nested parentheses. Preferred interview solution. |
| Recursive Expression Parsing | O(n) | O(n) | When recursive parsing feels more natural for nested expressions. |