Calculator With Parentheses
HardStack
Problem
Evaluate an arithmetic expression expr containing non-negative integers, +, -, *, /, parentheses and spaces. Multiplication and division bind tighter than addition and subtraction; equal-precedence operators apply left to right; parentheses group as usual.
A - may also be unary, but only at the very start of the expression or directly after ( (for example -(4 - 6) or (-3 + 1)). Integer division truncates toward zero. Return the result without using any built-in expression evaluator.
Example 1
- Input:
- expr = "2*(3+4) - 10/(1+2)"
- Output:
- 11
2 · 7 = 14 and 10 / 3 = 3, so 14 - 3 = 11.
Example 2
- Input:
- expr = "-(4 - 6*2)"
- Output:
- 8
4 - 12 = -8, negated: 8.
Constraints
- 1 ≤ expr.length ≤ 10^5
- The expression is valid, parentheses are balanced and nested at most 10^4 deep
- No division by zero; every intermediate result fits in a 32-bit signed integer
Hint
Show the first hint
Without parentheses, a stack of signed terms plus a pending operator handles precedence. What does '(' do to that state?
Walkthrough
How to approach it
01Clarify before coding
- Where can unary minus appear? Only at the start or right after '('. Not after another operator.
- How does division round? Toward zero.
- How deep can parentheses nest? Up to 10^4, so avoid recursion in languages with small stacks; use an explicit stack.
02Brute force
Find an innermost pair of parentheses, evaluate its contents with a no-parentheses calculator, splice the result back as text, and repeat.
Cost: Each splice rebuilds the string: O(n) per pair, O(n²) overall. Negative spliced results also make re-parsing awkward.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.