Basic calculator II

In this post we will discuss https://leetcode.com/problems/basic-calculator-ii/

There are 3 apporaches :

2 stack
1 stack
0 stack

We will go over each 1 by 1.

Evaluating Arithmetic Expressions with +, -, *, / Using Two Stacks

We want to solve an arithmetic expression that includes operators like +, -, *, and /, without parentheses.

A simple and intuitive approach is to use two stacks:

• Values stack: stores the numbers
• Operators stack: stores the operators

This mimics how we mentally process infix expressions.

Operator Precedence

• * and / have higher precedence than + and -

Whenever we encounter a new operator:

• We apply operators from the stack if they have higher or equal precedence
• Otherwise, we defer evaluation and push the current operator

Walkthrough: 1 + 2 * 3 + 4

Step 1:
values: 1
ops   : 

Step 2:
values: 1
ops   : +

Step 3:
values: 1 2
ops   : +

Step 4:
values: 1 2
ops   : + *

* has higher precedence than +, so we wait for another number.

Step 5:
values: 1 2 3
ops   : + *

Step 6:
Encounter '+'. Since * has higher precedence, we apply * first:
2 * 3 = 6

Now:
values: 1 6
ops   : +

Apply +:
1 + 6 = 7

Then push new '+':
values: 7
ops   : +

Step 7:
values: 7 4
ops   : +

Step 8:
End of expression. Apply +:
7 + 4 = 11

Final Answer: 11

Important Points

• Always apply the operator to the top two numbers: second = top, first = next
• Operator order matters for - and /
• a -b != b -a
• a / b != b / a
• Ignore whitespace, and construct multi-digit numbers correctly

Complete C++ Code

class Solution {
public:
    int precedence(char op) {
        return (op == '+' || op == '-') ? 0 : 1;
    }

    int applyOp(int a, int b, char op) {
        if (op == '+') return a + b;
        if (op == '-') return a - b;
        if (op == '*') return a * b;
        if (op == '/') return a / b;
        return -1;
    }

    void applyTopOp(stack<int>& values, stack<char>& ops) {
        int b = values.top(); values.pop();
        int a = values.top(); values.pop();
        char op = ops.top(); ops.pop();
        values.push(applyOp(a, b, op));
    }

    bool isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

    int calculate2Pass(string s) {
        stack<int> values;
        stack<char> ops;

        for (int i = 0; i < s.length(); ++i) {
            if (isspace(s[i])) continue;

            if (isdigit(s[i])) {
                int num = 0;
                while (i < s.length() && isdigit(s[i])) {
                    num = num * 10 + (s[i] - '0');
                    ++i;
                }
                values.push(num);
                --i;
            }
            else if (isOperator(s[i])) {
                while (!ops.empty() && precedence(s[i]) <= precedence(ops.top())) {
                    applyTopOp(values, ops);
                }
                ops.push(s[i]);
            }
        }

        while (!ops.empty()) {
            applyTopOp(values, ops);
        }

        return values.top();
    }
};

Can we do without 2 stacks ?

Some Key Observations :

1. + and - start new terms

These operators do not need to know anything about what follows.
Every + or - simply contributes a new number to the final result.

Example:
3 - 7 + 5 → the final evaluation is just 3 + (-7) + 5.

So for + and -, we can safely push numbers onto a stack and combine them at the end.

2. * and / modify the most recent term

These operators only act on the previous number and the next number.
They never interact with anything earlier in the expression.

Example:
2 * 4 affects only the value immediately before it.

This means the stack does not need to remember all earlier operations; it only needs to expose the most recent term.
So when we see a * or /, we:

push the result back
pop the last value from the stack
combine it with the current number

So, following this idea,
we need a sign bit , number and a stack which will hold (pos, negs)
we start from beginning :
if it is a digit form a number
skip the spaces
if it is a operator or end of string
for +, – simply push to stack
for *, / simply apply the operation and push to stack.
In the end, sum up the stack.

 int calculate(string s) {
        if(s.empty()) return 0;
        char sign = '+';
        int num = 0;

        stack<int> st;
        for (int i =0; i < s.size(); i++) {
            if (isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
            } 
            
            if ((!isdigit(s[i]) && s[i] != ' ') || i == s.size() -1){
                if (sign == '+') {
                    st.push(num);
                } else if (sign ==  '-') {
                    st.push(-num);
                } else if (sign == '*') {
                    auto first = st.top();
                    st.pop();
                    st.push(first * num);
                } else if (sign == '/') {
                    auto first = st.top();
                    st.pop();
                    st.push(first / num);
                }
                sign = s[i];
                num = 0;
            }
        }

        int res = 0;
        while (!st.empty()) {
            res += st.top();
            st.pop();
        }
        return res;
    }

Can we do better ?
if it had only + and – we might not have needed stack, but because of *, / we need to keep track of last. But, wait if we have to just wait for last, instead of stack, can we simply use a “last” number if we ever need to apply *, / later ?

Introducing the 0-Stack Optimization

The 1-stack method works because + and - push new values onto the stack, while * and / modify the most recent value.
But when we look closely, we realize something interesting:

We never need all values on the stack.
At any moment, we only need:

• the running total of all finalized terms
• and the last unfinalized term (the one that may still be multiplied or divided)

This means:

The entire stack can be replaced by two variables:

• ans → the sum of all completed terms
• last → the most recent term, which might still be affected by * or /

This gives us the 0-stack solution (technically O(1) storage).

3 + 2 * 4 – 5

[3]
[3, 2]
[3, 8]
[3, 8, -5]

But notice:

• Once we have [3], it will never change.
• The moment we push 2, that old 3 is already a final value.
• When we turn 2 → 8, we only needed to touch the top.
• When we push -5, the 3 and 8 are already done; nothing can change them.

At any moment:

ans holds the sum of all terms that will never change again.
last holds the one term whose value might still change (via * or /).

This perfectly mirrors mathematical precedence:

• + and - finalize the previous term
• * and / modify the last pending term

So the logic becomes:

When you see + or -:

• Add last to ans
• Replace last with the new number (positive or negative)

When you see * or /:

• Mutate last = last * num or last = last / num

At the end:

• Return ans + last

This exactly simulates what the stack would compute.

    int calculate(string s) {
        int last = 0, ans = 0;
        int num = 0;
        char sign =  '+';

        for (int i = 0; i < s.size(); i++) {
            char c = s[i];

            if (isdigit(c)) {
                num = (num * 10) + (c - '0');
            }

            if ((i == s.size() -1) || (!isdigit(c) && c != ' ')) {

                if (sign == '+') {
                    ans += last;
                    last = num;
                } else if (sign == '-') {
                    ans += last;
                    last = -num;
                } else if (sign == '*') {
                    last = last * num;
                } else if (sign == '/') {
                    last = last / num;
                }

                sign = c;
                num = 0;
            }
        }
        return ans + last;
    }