HardNeetCode150StackRecursionMathString
Basic Calculator
Evaluate expression with +, -, parentheses.
Examples
Input
s = "(1+(4+5+2)-3)+(6+8)"
Output
23
Nested evaluation.
Constraints
- •
1 <= s.length <= 3*10^5 - •
s digits, '-', '+', '(', ')'
Approaches
Two stacks for nums and ops.
CodeT: O(n) | S: O(n) stacks
Handle parentheses recursively.
CodeT: O(n) | S: O(n) stack depth
Single pass with sign.
CodeT: O(n) | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Stack | O(n) | O(n) stacks | Two stacks for nums and ops. |
| Recursive | O(n) | O(n) stack depth | Handle parentheses recursively. |
| Stack Optimized | O(n) | O(n) | Single pass with sign. |
Stack
T: O(n)S: O(n) stacks
Two stacks for nums and ops.
Recursive
T: O(n)S: O(n) stack depth
Handle parentheses recursively.
Stack Optimized
T: O(n)S: O(n)
Single pass with sign.
Common Mistakes
Not handling nested parens
Wrong sign handling
Off-by-one