20 · String Parsing & Expression Evaluation

#224 Basic Calculator

frequently reported atUber Amazon Microsoft Google Meta Bloomberg

the problem

In plain words

s is a valid expression with non-negative integers, '+', '-', brackets and spaces. A '-' can also mean "negative" at the very start or right after '(' — for example "-(2 + 3)" — but '+' is never used that way. Evaluate it without a built-in evaluator. Every number and every running total fits in a 32-bit int.

in s = "1 + 1"

out 2

in s = " 2-1 + 2 "

out 3

in s = "(1+(4+5+2)-3)+(6+8)"

out 23

(1 + 11 − 3) + 14 = 9 + 14.

1 ≤ s.length ≤ 3·10⁵
s has digits, '+', '-', '(', ')' and ' '
s is valid; two operators never touch
Every number and running total fits in an int

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternStack for matching & nesting String parsing

where this runsjavac parses binary operators with an operand stack and an operator stack inside its otherwise recursive-descent parser.

With only + and −, a bracket just keeps or flips the signs inside it. At '(' save the total so far and the sign in front; at ')' glue the group back on: outside + sign × inside.

solutions

From brute force to optimal

The first ')' closes an innermost group. Evaluate that flat group, write its value into the string, and start again.

Remove the spaces.
While there is a ')': find it and the last '(' before it; evaluate the inside (only + and −); splice the value in.
Evaluate what is left. A run of signs like "--" (from "1-(-2)") folds into one sign.

timeO(n²)

Up to about n/2 groups, and each rewrite rebuilds the whole string.

spaceO(n)

The rewritten strings.

javajava.util.*

1class Solution {2    public int calculate(String s) {3        String e = s.replace(" ", "");4        int close;5        while ((close = e.indexOf(')')) >= 0) {        // the first ')' closes an innermost group6            int open = e.lastIndexOf('(', close);7            long inner = evalFlat(e.substring(open + 1, close));8            e = e.substring(0, open) + inner + e.substring(close + 1); // rebuild the whole string9        }10        return (int) evalFlat(e);11    }12 13    /** Only numbers, + and -. A run of signs like "--" (from "1-(-2)" → "1--2") folds into one. */14    private long evalFlat(String e) {15        long total = 0;16        int i = 0;17        while (i < e.length()) {18            int sign = 1;19            while (e.charAt(i) == '+' || e.charAt(i) == '-') {20                if (e.charAt(i) == '-') sign = -sign;21                i++;22            }23            long num = 0;24            while (i < e.length() && e.charAt(i) >= '0' && e.charAt(i) <= '9') num = num * 10 + (e.charAt(i++) - '0');25            total += sign * num;26        }27        return total;28    }29}

Keep result, sign and num for the current level. '(' pushes the outside's result and the sign before the bracket; ')' pops them and combines.

Digit → num = num × 10 + d.
'+' or '-' → result += sign × num; num = 0; sign = ±1.
'(' → push result, push sign; result = 0; sign = 1.
')' → result += sign × num; num = 0; groupSign = pop(); outside = pop(); result = outside + groupSign × result.
Return result + sign × num.

timeO(n)

Each character is handled once; each bracket pushes and pops one pair.

spaceO(depth)

One pair per open bracket — O(n) in the worst case, on the heap.

javajava.util.*

1class Solution {2    public int calculate(String s) {3        Deque<Integer> stack = new ArrayDeque<>(); // saved (result, sign) for every open '('4        int result = 0, sign = 1, num = 0;5        for (int i = 0; i < s.length(); i++) {6            char c = s.charAt(i);7            if (c >= '0' && c <= '9') {8                num = num * 10 + (c - '0');9            } else if (c == '+' || c == '-') {10                result += sign * num; // the number before this operator is complete11                num = 0;12                sign = c == '+' ? 1 : -1;13            } else if (c == '(') {14                stack.push(result); // save the outside: its total so far ...15                stack.push(sign); // ... and the sign in front of this group16                result = 0;17                sign = 1;18            } else if (c == ')') {19                result += sign * num; // finish the inside20                num = 0;21                int groupSign = stack.pop();22                int outside = stack.pop();23                result = outside + groupSign * result; // glue the group onto the outside24            }25        }26        return result + sign * num;27    }28}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public int calculate(String s) {3        Deque<Integer> stack = new ArrayDeque<>(); // saved (result, sign) for every open '('4        int result = 0, sign = 1, num = 0;5        for (int i = 0; i < s.length(); i++) {6            char c = s.charAt(i);7            if (c >= '0' && c <= '9') {8                num = num * 10 + (c - '0');9            } else if (c == '+' || c == '-') {10                result += sign * num; // the number before this operator is complete11                num = 0;12                sign = c == '+' ? 1 : -1;13            } else if (c == '(') {14                stack.push(result); // save the outside: its total so far ...15                stack.push(sign); // ... and the sign in front of this group16                result = 0;17                sign = 1;18            } else if (c == ')') {19                result += sign * num; // finish the inside20                num = 0;21                int groupSign = stack.pop();22                int outside = stack.pop();23                result = outside + groupSign * result; // glue the group onto the outside24            }25        }26        return result + sign * num;27    }28}

A shared cursor; group() reads until its ')' and returns the value. '(' calls group() — the call stack saves result and sign.

Digits → a number added with the current sign.
'+' / '-' → set sign.
'(' → result += sign × group().
')' → return result.

timeO(n)

The cursor only moves forward, so every character is read once.

spaceO(depth)

One stack frame per open bracket; very deep nesting can throw StackOverflowError.

javajava.util.*

1class Solution {2    private String s;3    private int i; // the cursor, shared by every call4 5    public int calculate(String s) {6        this.s = s;7        this.i = 0;8        return group();9    }10 11    /** Reads up to the matching ')' (or the end) and returns the value of that group. */12    private int group() {13        int result = 0, sign = 1;14        while (i < s.length()) {15            char c = s.charAt(i++);16            if (c >= '0' && c <= '9') {17                int num = c - '0';18                while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') num = num * 10 + (s.charAt(i++) - '0');19                result += sign * num;20            } else if (c == '+') {21                sign = 1;22            } else if (c == '-') {23                sign = -1;24            } else if (c == '(') {25                result += sign * group(); // the call stack saves result and sign for us26            } else if (c == ')') {27                return result;28            }29        }30        return result;31    }32}

in the room

How to say it in the interview

talk track

Clarify: only + and −? Where can unary minus appear? Spaces anywhere? (Yes; at the start and after '('; yes.)
Name the state: result, sign and num for the current level.
At '(' push result and sign, then reset; at ')' pop both and combine.
Offer the recursive version and mention its depth risk on deeply nested input.

traps

Forgetting the last number after the loop: return result + sign × num.
Popping in the wrong order: the sign was pushed last, so it comes off first.
Treating "-(" as an error: a unary minus is just sign = −1 with nothing to add before it.

what they ask next

Follow-ups

Add * and / (Basic Calculator III, LC 772, Premium)?

Use the two-stack shunting-yard from this chapter, or recursive descent: expr → term → factor, where factor reads a number or a bracketed expr.

What if the nesting is thousands of levels deep?

The sign-stack version keeps its pairs in an ArrayDeque on the heap, so it is safe. A recursive solution needs one call per level and can overflow the thread's stack.

before you submit

Edge cases to test

Unary minus at the start and after '(': "-(2+3)" → −5, "1-(-2)" → 3.
Brackets around one number: "(((7)))" → 7.
Deep nesting of hundreds of levels: safe for the stack version.

practise next