Basic Calculator II

MediumStack · String Parsing🧩 Stack LeetCode #227 ↗Updated Oct 30, 2026

Problem

You are given a valid arithmetic expression s built from non-negative integers, the operators + - * / and arbitrary spaces (no parentheses). Evaluate it with the usual precedence (* and / before + and -, left to right within a level), where division truncates toward zero. Library expression evaluators are not allowed.

Inputs = "3+2*2"Output7

Inputs = " 3/2 "Output1

Inputs = " 3+5 / 2 "Output5

1 ≤ s.length ≤ 3·10⁵ · numbers fit in [0, 2³¹-1] · every intermediate and final result fits in a 32-bit int · expression is valid

Try it yourself

Java

class Solution {
    public int calculate(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Read the expression as a sum of signed terms: + and - start a new term, while * and / only modify the current term. So you only ever need the latest term, not the whole history.

PatternStack

Instinct Things resolve in reverse order of arrival (brackets, adjacent pairs, nested expressions) - push now, pop when its partner shows up.

Memory hack Last in, first out - like a pile of plates, you only ever touch the one on top; every closer pops its opener.

Open the Stack guide →

Approaches

Brute ForceTokenize, then Collapse Operators in a List

Time O(n²)Space O(n)

Split the string into number and operator tokens. Sweep the list and, whenever a * or / appears, replace a op b by its value; the list then holds only +/-, which a final left-to-right pass sums. Each in-list removal shifts the tail, hence quadratic time.

Java

public int calculate(String s) {
    List<String> t = new ArrayList<>();
    int n = s.length(), i = 0;
    while (i < n) {
        char c = s.charAt(i);
        if (c == ' ') { i++; continue; }
        if (Character.isDigit(c)) {
            int j = i;
            while (j < n && Character.isDigit(s.charAt(j))) j++;
            t.add(s.substring(i, j));
            i = j;
        } else {
            t.add(String.valueOf(c));
            i++;
        }
    }
    // Pass 1: fold every * and / into a single number
    int k = 1;
    while (k < t.size()) {
        String op = t.get(k);
        if (op.equals("*") || op.equals("/")) {
            int a = Integer.parseInt(t.get(k - 1)), b = Integer.parseInt(t.get(k + 1));
            t.set(k - 1, String.valueOf(op.equals("*") ? a * b : a / b));
            t.remove(k); // drop operator ...
            t.remove(k); // ... and right operand (O(n) shifts each)
        } else {
            k += 2;
        }
    }
    // Pass 2: only + and - remain
    int result = Integer.parseInt(t.get(0));
    for (k = 1; k < t.size(); k += 2) {
        int v = Integer.parseInt(t.get(k + 1));
        result = t.get(k).equals("+") ? result + v : result - v;
    }
    return result;
}

Mirrors how you'd do it on paper, but list removals make it O(n²).

BetterStack of Signed Terms

Time O(n)Space O(n)

Scan once, building the current number and remembering the operator that came before it. On the next operator (or the end) apply the remembered one: +/- push ±num as a fresh term, *// pop the last term, combine and push it back. The answer is the sum of the stack.

Java

public int calculate(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    int num = 0;
    char op = '+'; // operator that precedes num
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)) num = num * 10 + (c - '0');
        if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
            if (op == '+') stack.push(num);
            else if (op == '-') stack.push(-num);
            else if (op == '*') stack.push(stack.pop() * num);
            else stack.push(stack.pop() / num);
            op = c;
            num = 0;
        }
    }
    int sum = 0;
    for (int term : stack) sum += term;
    return sum;
}

Linear and the standard interview answer, but the stack can hold n/2 terms.

OptimalRunning Total + Last Term (No Stack)

Time O(n)Space O(1)

Only the top of the stack is ever touched, so replace it with a variable last. Everything below it is already final, so fold it into result the moment a new +/- term starts. At the end the answer is result + last.

Java

public int calculate(String s) {
    int result = 0, last = 0, num = 0;
    char op = '+';
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)) num = num * 10 + (c - '0');
        if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
            if (op == '+' || op == '-') {
                result += last;                 // previous term is complete
                last = op == '+' ? num : -num;
            } else if (op == '*') {
                last = last * num;
            } else {
                last = last / num;              // truncates toward zero
            }
            op = c;
            num = 0;
        }
    }
    return result + last;
}

Dry run"3+2*2-4/3"

i flush point (applies previous op) changed

at '+'
3

+
i
2

*

2

-

4

/

3

res=0, last=3
at '*'
3

+

2

*
i
2

-

4

/

3

res=3, last=2
at '-'
3

+

2

*

2

-
i
4

/

3

last=2*2=4
at '/'
3

+

2

*

2

-

4

/
i
3

res=7, last=-4
end
3

+

2

*

2

-

4

/

3
i
last=-4/3=-1
return
3

+

2

*

2

-

4

/

3

7 + (-1) = 6 ✔

Single pass, constant memory — the best possible.

Pro tip

The trick is applying the previous operator when you meet the next one — remember to also flush at the last character.

At a glance

Level	Approach	Time	Space
Brute Force	Tokenize, then Collapse Operators in a List	`O(n²)`	`O(n)`
Better	Stack of Signed Terms	`O(n)`	`O(n)`
Optimal	Running Total + Last Term (No Stack)	`O(n)`	`O(1)`

Common pitfalls

Forgetting to flush the final number (the i == n-1 check).
Treating spaces as operators — they must be skipped, not trigger a flush.
Computing -(a/b) vs (-a)/b differently in languages that floor; Java truncates, so both agree.

Interview tips

Clarify: no parentheses, no unary minus, integer division toward zero.
Explain the “sum of terms” view before coding the stack.
Then point out only the top is used and drop the stack for O(1) space.

Pattern

Stack for operator precedence → evaluate expressions where some operators bind tighter than others.

My notes saved in this browser