Basic Calculator II

mediumAmazon-tagged: Mixed64 stepsJava · Python · C++

Evaluate an expression with + − × ÷ and spaces, respecting precedence. Read numbers left to right, remembering the operator before each one. + and − push the number (or its negative) on a stack; × and ÷ combine immediately with the stack's top. The answer is the stack's sum.

▶ Watch the animated trace

Traced input: s = "3+2*2-8/3" → 5. Original problem: neetcode.io/problems/basic-calculator-ii

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(n)

Can be done in O(1) space by keeping only the last term.

Key idea

× and ÷ bind tighter, so apply them right away to the previous term.
+ and − are deferred: push signed terms and add them at the end.
Process the pending operator when you hit the next operator or the end of the string.
Division truncates toward zero.

Common mistakes

Forgetting to process the last number.
Treating spaces as operators.
Applying + immediately breaks precedence: "3+2*2" must be 7.

Solution

Java

int calculate(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    int 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) {
            switch (op) {
                case '+' -> stack.push(num);
                case '-' -> stack.push(-num);
                case '*' -> stack.push(stack.pop() * num);
                case '/' -> stack.push(stack.pop() / num);
            }
            op = c;
            num = 0;
        }
    }
    int sum = 0;
    for (int v : stack) sum += v;
    return sum;
}

Python

def calculate(s: str) -> int:
    stack, num, op = [], 0, '+'
    for i, c in enumerate(s):
        if c.isdigit(): num = num * 10 + int(c)
        if (not c.isdigit() and c != ' ') or i == len(s) - 1:
            if op == '+': stack.append(num)
            elif op == '-': stack.append(-num)
            elif op == '*': stack.append(stack.pop() * num)
            else: stack.append(int(stack.pop() / num))  # truncate toward zero
            op, num = c, 0
    return sum(stack)

C++

int calculate(string s) {
    vector<int> st;
    int num = 0;
    char op = '+';
    for (int i = 0; i < (int)s.size(); i++) {
        char c = s[i];
        if (isdigit(c)) num = num * 10 + (c - '0');
        if ((!isdigit(c) && c != ' ') || i == (int)s.size() - 1) {
            switch (op) {
                case '+': st.push_back(num); break;
                case '-': st.push_back(-num); break;
                case '*': st.back() *= num; break;
                case '/': st.back() /= num; break;
            }
            op = c;
            num = 0;
        }
    }
    return accumulate(st.begin(), st.end(), 0);
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Spaces Spaces are skipped; 3/2 truncates to 1.	`s = " 3/2 "`	`1`
Multi-digit numbers 14 − 12.	`s = "14-3*4"`	`2`
Single number Processed at the end of the string.	`s = "42"`	`42`