Basic Calculator II

Medium · Stack · Explanation and code example

Without Stack

How it works

We can avoid using a stack by realizing that we only need to track two values: the running total of all fully computed terms, and the prev term that might still be involved in a multiplication or division. When we see + or -, we can add the prev term to our total and start a new term. When we see * or /, we update the prev term directly. This reduces space complexity to O(1).

Steps

Initialize total, prev, and num to 0, and set the initial operator to +.
Iterate through the string (plus one extra iteration to process the last number).
Skip spaces. Build up multi-digit numbers.
When we hit an operator or the end:
- For +: add prev to total, set prev to num.
- For -: add prev to total, set prev to -num.
- For *: multiply prev by num.
- For /: divide prev by num (truncate toward zero).
- Update the operator and reset num.
Add the final prev to total and return it.

Complexity

Time complexity: O(n)
Space complexity: O(1)

Things to watch for

Incorrect Integer Division with Negative Numbers

Division in this problem truncates toward zero, but some languages (like Python) use floor division by default, which truncates toward negative infinity. This gives wrong results for negative numbers.

Forgetting to Process the Last Number

The algorithm typically processes a number when it encounters an operator. However, the last number in the expression has no operator after it, so it might never get processed unless you handle this edge case explicitly.

Not Handling Spaces Correctly

The expression can contain spaces between numbers and operators. Failing to skip or remove spaces causes parsing errors or treats spaces as invalid characters.

Python code example

class Solution:
    def calculate(self, s: str) -> int:
        total = prev = num = 0
        op = '+'
        n = len(s)
        i = 0

        while i <= n:
            ch = s[i] if i < n else '+'
            if ch == ' ':
                i += 1
                continue

            if '0' <= ch <= '9':
                num = num * 10 + (ord(ch) - ord('0'))
            else:
                if op == '+':
                    total += prev
                    prev = num
                elif op == '-':
                    total += prev
                    prev = -num
                elif op == '*':
                    prev = prev * num
                else:
                    if prev < 0:
                        prev = -(-prev // num)
                    else:
                        prev = prev // num

                op = ch
                num = 0

            i += 1

        total += prev
        return total

C++ code example

class Solution {
public:
    int calculate(string s) {
        int total = 0, prev = 0, num = 0;
        char op = '+';
        int n = s.size(), i = 0;
        while (i <= n) {
            char ch = i < n ? s[i] : '+';
            if (ch == ' ') {
                i++;
                continue;
            }
            if (isdigit(ch)) {
                num = num * 10 + (ch - '0');
            } else {
                if (op == '+') {
                    total += prev;
                    prev = num;
                } else if (op == '-') {
                    total += prev;
                    prev = -num;
                } else if (op == '*') {
                    prev = prev * num;
                } else {
                    prev = prev / num;
                }
                op = ch;
                num = 0;
            }
            i++;
        }
        total += prev;
        return total;
    }
};

Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations