Basic Calculator II

Start dumb: evaluate left to right

The tempting first idea is to just walk the expression and apply each operator as you meet it. But 3 + 2 * 2 becomes (3 + 2) * 2 = 10, not 7 — left-to-right ignores that * and / bind tighter. The next fix is two passes: first sweep through resolving every * and /, then add and subtract what’s left. It’s correct but clumsy, rewriting the sequence as it goes.

Find the bottleneck

The only reason * and / need special handling is precedence: they bind to the number right next to them, so they can’t wait. + and -, on the other hand, can wait — their contribution never overrides anything earlier. So you don’t need a second pass; you need to defer the additions.

The optimal shape

Track the number you’re reading and op, the operator sitting in front of it (it starts as an implicit +). Each time you reach the next operator — or the end of the string — apply op to the number you just finished:

1. + → push number.
2. - → push -number.
3. * → push pop() * number.
4. / → push pop() / number, truncated toward zero.

Then remember the new operator and reset the number. Sum the stack to finish. O(n) time, O(n) space. In the player, * and / visibly reach back and rewrite the top of the stack, while + and - just drop a term on top.

Watch it think

Run the default 3+2*2 and watch 2*2 pop the 2 and drop 4 in its place. Then try 14-3/2 (truncation toward zero), 100/10/2 (left-associative division), and 3+5 / 2 (spaces around a number change nothing).

1fun calculate(s: String): Int {
2    val stack = ArrayDeque<Int>()
3    var number = 0
4    var op = '+'
5    for ((i, c) in s.withIndex()) {
6        if (c.isDigit()) number = number * 10 + (c - '0')
7        if (!c.isDigit() && c != ' ' || i == s.lastIndex) {
8            when (op) {
9                '+' -> stack.addLast(number)
10                '-' -> stack.addLast(-number)
11                '*' -> stack.addLast(stack.removeLast() * number)
12                '/' -> stack.addLast(stack.removeLast() / number)
13            }
14            op = c
15            number = 0
16        }
17    }
18    return stack.sum()
19}