Problem statement

Given a string s holding a valid arithmetic expression, evaluate it and return the result.

The expression contains non-negative integers, the operators + - * /, and spaces. There are no parentheses. Integer division truncates toward zero.

Example 1

Input: s = "3+2*2"
Output: 7

Example 2

Input: s = " 3/2 "
Output: 1

Example 3

Input: s = " 3+5 / 2 "
Output: 5

Constraints

• 1 <= s.length <= 64
• s consists of digits, '+', '-', '*', '/' and ' '.
• Every operand is a non-negative integer below 100.
• Division by zero never occurs.
• Every intermediate value and the answer fit in a signed 32-bit integer.

Hints for Basic Calculator II

1. Hint 1

   Push each term onto a stack, negating it after a -; the final answer is the sum of the stack.

2. Hint 2

   * and / bind tighter, so apply them immediately to the value on top of the stack.

3. Hint 3

   Careful with /: the top of the stack may be negative, and the truncation must go toward zero, not downward.

How to solve Basic Calculator II

Push each term onto a stack — negated after -, multiplied or divided into the previous top after * / / — and sum the stack at the end.

Approach

1. Accumulate digits into num; on an operator (or the end), apply the previous operator: push ±num, or replace the top with top * num / top / num truncated toward zero.
2. Reset num, remember the operator, and finally return sum(stack).

Why it works

Multiplication and division bind tighter, so applying them immediately to the last term respects precedence; addition and subtraction are deferred to the final sum.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Python's // floors, so a negative top needs abs(a) // num with the sign restored.

Reference solution

Python

def calculate(s: str) -> int:
    stack = []
    num = 0
    sign = "+"
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if (ch != " " and not ch.isdigit()) or i == len(s) - 1:
            if sign == "+":
                stack.append(num)
            elif sign == "-":
                stack.append(-num)
            elif sign == "*":
                stack.append(stack.pop() * num)
            else:
                a = stack.pop()
                q = abs(a) // num
                stack.append(q if a >= 0 else -q)
            sign = ch
            num = 0
    return sum(stack)

Java

public static int calculate(String s) {
    List<Integer> stack = new ArrayList<>();
    int num = 0;
    char sign = '+';
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        boolean isDigit = c >= '0' && c <= '9';
        if (isDigit) num = num * 10 + (c - '0');
        if ((c != ' ' && !isDigit) || i == s.length() - 1) {
            if (sign == '+') {
                stack.add(num);
            } else if (sign == '-') {
                stack.add(-num);
            } else if (sign == '*') {
                stack.set(stack.size() - 1, stack.get(stack.size() - 1) * num);
            } else {
                stack.set(stack.size() - 1, stack.get(stack.size() - 1) / num);
            }
            sign = c;
            num = 0;
        }
    }
    int total = 0;
    for (int x : stack) total += x;
    return total;
}

C++

int calculate(string s) {
    vector<int> stack;
    int num = 0;
    char sign = '+';
    for (int i = 0; i < (int) s.size(); i++) {
        char c = s[i];
        bool isDigit = c >= '0' && c <= '9';
        if (isDigit) num = num * 10 + (c - '0');
        if ((c != ' ' && !isDigit) || i == (int) s.size() - 1) {
            if (sign == '+') stack.push_back(num);
            else if (sign == '-') stack.push_back(-num);
            else if (sign == '*') stack.back() = stack.back() * num;
            else stack.back() = stack.back() / num;
            sign = c;
            num = 0;
        }
    }
    int total = 0;
    for (int x : stack) total += x;
    return total;
}

JavaScript

var calculate = function(s) {
    const stack = [];
    let num = 0;
    let sign = "+";
    for (let i = 0; i < s.length; i++) {
        const c = s.charAt(i);
        const isDigit = c >= "0" && c <= "9";
        if (isDigit) num = num * 10 + (c.charCodeAt(0) - 48);
        if ((c !== " " && !isDigit) || i === s.length - 1) {
            if (sign === "+") {
                stack.push(num);
            } else if (sign === "-") {
                stack.push(-num);
            } else if (sign === "*") {
                stack.push(stack.pop() * num);
            } else {
                const q = stack.pop() / num;
                stack.push(q < 0 ? Math.ceil(q) : Math.floor(q));
            }
            sign = c;
            num = 0;
        }
    }
    let total = 0;
    for (let i = 0; i < stack.length; i++) total += stack[i];
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Product of the Last K Numbers Medium
• Add 1 to a Number Represented as Linked List Medium
• Double a Number Represented as a Linked List Medium
• Insert Greatest Common Divisors in Linked List Medium
• Add Two Numbers II Medium
• Add Two Numbers Medium