20 · String Parsing & Expression Evaluation

#227 Basic Calculator II

frequently reported atMeta ByteDance / TikTok Airbnb Amazon Bloomberg Microsoft

the problem

In plain words

s is a valid arithmetic expression made of non-negative integers, the operators + − /, and spaces — no brackets. Evaluate it: and / come before + and −, operators of equal rank go left to right, and integer division drops the fraction (toward zero). Don't use a built-in expression evaluator.

in s = "3+2*2"

out 7

2*2 first, then 3 + 4.

in s = " 3/2 "

out 1

in s = " 3+5 / 2 "

out 5

5 / 2 = 2, then 3 + 2.

1 ≤ s.length ≤ 3·10⁵
s has digits, '+', '-', '*', '/' and ' '
s is valid; every number is in [0, 2³¹ − 1]
Every intermediate result and the answer fit in a 32-bit 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

+ and − start a new term; * and / only change the current term. Keep the finished terms summed in result and the current one in last.

solutions

From brute force to optimal

Tokenise into a list. Collapse every a * b and a / b in place, then add and subtract what is left.

Tokens: numbers and operators.
Pass 1: at each * or /, replace a, op, b with the result (two ArrayList removals).
Pass 2: left to right over + and −.

timeO(n²)

Each ArrayList removal shifts the rest of the list, and there can be about n/2 of them.

spaceO(n)

The token list.

javajava.util.*

1class Solution {2    public int calculate(String s) {3        List<String> t = new ArrayList<>();                 // tokens: "3", "+", "2", "*", "2"4        for (int i = 0; i < s.length(); i++) {5            char c = s.charAt(i);6            if (c == ' ') continue;7            if (c >= '0' && c <= '9') {8                int j = i;9                while (j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9') j++;10                t.add(s.substring(i, j));11                i = j - 1;12            } else {13                t.add(String.valueOf(c));14            }15        }16        for (int i = 1; i < t.size(); ) {                   // pass 1: * and / bind tighter17            String op = t.get(i);18            if (op.equals("*") || op.equals("/")) {19                int a = Integer.parseInt(t.get(i - 1)), b = Integer.parseInt(t.get(i + 1));20                t.set(i - 1, String.valueOf(op.equals("*") ? a * b : a / b));21                t.remove(i + 1);                            // each remove shifts the rest of the list: O(n)22                t.remove(i);23            } else {24                i += 2;25            }26        }27        int result = Integer.parseInt(t.get(0));           // pass 2: only + and - are left28        for (int i = 1; i < t.size(); i += 2) {29            int b = Integer.parseInt(t.get(i + 1));30            result = t.get(i).equals("+") ? result + b : result - b;31        }32        return result;33    }34}

Push +num or −num for + and −; for * and /, pop the last term, combine it with num, and push it back. Sum the stack.

op = '+'. Build num digit by digit.
At an operator or the last character: + → push num; − → push −num; * → push pop() × num; / → push pop() / num.
op = c, num = 0. Finally add up the stack.

timeO(n)

Each character is read once; each term is pushed and popped at most once.

spaceO(n)

Up to about n/2 terms wait on the stack.

javajava.util.*

1class Solution {2    public int calculate(String s) {3        Deque<Integer> terms = new ArrayDeque<>();          // signed terms still to be added up4        int num = 0;5        char op = '+';                                      // the operator in front of num6        for (int i = 0; i < s.length(); i++) {7            char c = s.charAt(i);8            if (c >= '0' && c <= '9') num = num * 10 + (c - '0');9            if (c == '+' || c == '-' || c == '*' || c == '/' || i == s.length() - 1) {10                switch (op) {11                    case '+' -> terms.push(num);12                    case '-' -> terms.push(-num);13                    case '*' -> terms.push(terms.pop() * num); // * and / grab the previous term14                    default -> terms.push(terms.pop() / num);15                }16                op = c;17                num = 0;18            }19        }20        int result = 0;21        for (int term : terms) result += term;22        return result;23    }24}

Only the top of the stack is ever touched, so keep it in last and add everything below it into result.

op = '+', result = last = num = 0.
At an operator or the last character: if op is + or −, result += last and last = ±num; if , last = num; if /, last /= num.
op = c, num = 0. Return result + last.

timeO(n)

One pass, O(1) work per character.

spaceO(1)

Four variables.

javajava.util.*

1class Solution {2    public int calculate(String s) {3        int result = 0; // the terms that are finished4        int last = 0; // the term that * and / may still change5        int num = 0;6        char op = '+'; // the operator in front of num7        for (int i = 0; i < s.length(); i++) {8            char c = s.charAt(i);9            if (c >= '0' && c <= '9') num = num * 10 + (c - '0');10            if (c == '+' || c == '-' || c == '*' || c == '/' || i == s.length() - 1) {11                if (op == '+' || op == '-') {12                    result += last; // nothing can change last any more: bank it13                    last = op == '+' ? num : -num;14                } else if (op == '*') {15                    last = last * num;16                } else {17                    last = last / num; // int division truncates toward zero, as required18                }19                op = c;20                num = 0;21            }22        }23        return result + last;24    }25}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public int calculate(String s) {3        int result = 0; // the terms that are finished4        int last = 0; // the term that * and / may still change5        int num = 0;6        char op = '+'; // the operator in front of num7        for (int i = 0; i < s.length(); i++) {8            char c = s.charAt(i);9            if (c >= '0' && c <= '9') num = num * 10 + (c - '0');10            if (c == '+' || c == '-' || c == '*' || c == '/' || i == s.length() - 1) {11                if (op == '+' || op == '-') {12                    result += last; // nothing can change last any more: bank it13                    last = op == '+' ? num : -num;14                } else if (op == '*') {15                    last = last * num;16                } else {17                    last = last / num; // int division truncates toward zero, as required18                }19                op = c;20                num = 0;21            }22        }23        return result + last;24    }25}

in the room

How to say it in the interview

talk track

Clarify: no brackets, no unary minus, spaces anywhere, division truncates toward zero.
Describe terms: "3 + 5*2 − 8/3" is +3, +10, −2.
Code the stack of terms, then fold it into one variable last because only the top is ever used.
Mention the end-of-string commit: the last number has no operator after it.

traps

Forgetting the last number: commit when i == n − 1 as well, even if that character is a space.
Applying to `result` instead of `last`: 3+22 becomes 10.
Treating a space as an operator and committing early: only + − * / and the last index commit.

what they ask next

Follow-ups

Add brackets (Basic Calculator III, LC 772, Premium)?

Recurse on '(' with a shared index and use the inner value as num, or use the two-stack shunting-yard from this chapter.

Add unary minus?

Treat a '-' with no number before it as 0 − x (push 0 first), or let factor() read '-' factor in a recursive parser.

before you submit

Edge cases to test

One number with spaces: " 42 " → 42.
Truncation after a minus: in "14-3/2" the term is −1, so the answer is 13.
Chains: "100/10/3" = 3, strictly left to right.

practise next