Basic Calculator

Start dumb: recurse into every parenthesis

The obvious first idea treats parentheses literally: scan left to right, and whenever you hit a (, find its matching ), cut out that substring, and recursively evaluate it before continuing. It works, but finding each matching ) re-scans the tail, and slicing out substrings copies the string again — so a deeply nested expression is O(n²) and allocates on every level.

Find the bottleneck

That recursion keeps re-discovering something the single scan already knows: where it is. Diving into a group only needs you to remember two things — the running total you had so far, and the sign sitting in front of the group — so you can pick up exactly where you left off when the group closes. That’s a tiny, bounded amount of state per level, not a whole substring.

The optimal shape

One left-to-right pass:

1. Digit → extend the current number (numbers can be multi-digit).
2. + / - → commit sign * number into result, reset number, and set the sign for the number coming next.
3. ( → push result and sign, then reset to result = 0, sign = +1.
4. ) → commit the last number, then result = result * savedSign + savedResult — the inner value, signed, added back onto the outer total.
5. After the scan, commit the final pending number.

Each character is handled once — O(n) time, O(depth) stack. In the player, every ( still waiting for its ) stays highlighted as the open “window”; a closed pair retires to green.

Watch it think

Run the default nested expression, then the tricky ones: -(2+3) (a minus in front of a whole group), 2-(1-(0-(2))) (nested unary minus), and 100 + 1 (a multi-digit number built one digit at a time).

1fun calculate(s: String): Int {
2    val stack = ArrayDeque<Int>()
3    var result = 0
4    var number = 0
5    var sign = 1
6    for (c in s) {
7        when {
8            c.isDigit() -> number = number * 10 + (c - '0')
9            c == '+' -> { result += sign * number; number = 0; sign = 1 }
10            c == '-' -> { result += sign * number; number = 0; sign = -1 }
11            c == '(' -> { stack.addLast(result); stack.addLast(sign); result = 0; sign = 1 }
12            c == ')' -> {
13                result += sign * number; number = 0
14                result *= stack.removeLast()
15                result += stack.removeLast()
16            }
17        }
18    }
19    return result + sign * number
20}