Basic Calculator

Here we will discuss : https://leetcode.com/problems/basic-calculator

In Last article https://jdecodes.wordpress.com/2025/06/20/basic-calculator-ii/ we solved basic calculator where there was only, +, -, *, /

Let’s make it bit more complicated. Now our problem has

Operators: +, -
Parentheses: nested and balanced
Unary minus: e.g., -2, 1 - (-2), -(-(-3))

We’ll use the two-stack approach: one stack for values, another for operators. This gives us flexibility and clarity, just like how we evaluate expressions manually.

Unary Minus – What’s the Problem?

Unary minus occurs when - doesn’t have a left operand. For example:

-1 → 0 - 1
-(2 + 3) → 0 - (2 + 3)
1 - (-(2)) → valid
-( - ( -3 ) ) → nested negations

How to Detect It?

When - is at the start: index 0
Or after an opening parenthesis: ( -2 )

So whenever we find a - where the previous char is '(' or it’s the start, we can safely inject a 0 before it.

    bool isUnaryMinus(const string& s, int i) {
        int j = i - 1;
        while (j >= 0 && s[j] == ' ') j--;

        // if start of string, or comes after '(' or operator
        return j < 0 || s[j] == '(' ;
    }

Parentheses – What’s the Intuition?

Parentheses help group subexpressions, so we should evaluate them in isolation.

When we see (, we push it to the operator stack and wait.
When we see ), we start applying operators until we hit (.

This ensures correct handling of nested expressions without needing recursion.

`1 - (2 - (3 + 4))`

Step 1:
values: 1
ops   :

Step 2:
ops: -

Step 3:
values: 1 2
ops   : -

Step 4:
ops: - (

Step 5:
values: 1 2 3
ops   : - ( -

Step 6:
values: 1 2 3 4
ops   : - ( - +

Encounter ')':
→ Apply + on 3 and 4 = 7
→ Pop '('

→ Apply - on 2 and 7 = -5
→ Pop '(' again

→ Apply - on 1 and -5 = 6

C++ Code (Two Stack with Parentheses and Unary Minus)

class Solution {
public:
    bool isOperator(char c) {
        return c == '+' || c == '-';
    }

    int precedence(char c) {
        return 0; // '+' and '-' are equal
    }

    int applyOp(int a, int b, char op) {
        return (op == '+') ? a + b : a - b;
    }

    void apply(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));
    }

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

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

            if (isdigit(s[i])) {
                int num = 0;
                while (i < s.size() && isdigit(s[i])) {
                    num = num * 10 + (s[i] - '0');
                    ++i;
                }
                values.push(num);
                --i;
            }
            else if (s[i] == '(') {
                ops.push(s[i]);
            }
            else if (s[i] == ')') {
                while (!ops.empty() && ops.top() != '(') {
                    apply(values, ops);
                }
                if (!ops.empty()) ops.pop(); // pop '('
            }
            else if (isOperator(s[i])) {
                if (s[i] == '-' && (i == 0 || s[i - 1] == '(')) {
                    values.push(0); // handle unary -
                }

                while (!ops.empty() && ops.top() != '(' && precedence(s[i]) <= precedence(ops.top())) {
                    apply(values, ops);
                }
                ops.push(s[i]);
            }
        }

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

        return values.top();
    }
};

Takeaway

Using two stacks gives you full control over precedence, associativity, and unary cases
Parentheses are handled by pausing until we hit a )
Unary minus is transformed to binary 0 - num with a simple rule

Can we do better, if you have followed earlier article, then we can simply extend the solution to add support for “(” and “)”.

As “(” means that there is a need for new calculations in the scope and it will return a new number, but for how long we should search that ? may be until we find “)”.

But wait, how would the new calculation would know in previous code from where to read. This is where recursion comes to rescue us.

lets say we have a helper which calculates the expression,

we will recursively call this function whenever we see a new “(“, and our return condition will be “)”.

But wait, how do we pass index where to read , we can use a global variable or reference to pass .

class Solution {
public:
// ---- global variable to track start position after (
    int i = 0;
// -------------------------------------------------
    int helper(string& s) {
        long num = 0;
        char op = '+';  // last seen operator
        int last = 0;
        int ans = 0;
        for (;i < s.size(); i++) {
            char c = s[i];

            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            }
// ----------  addition to earlier code -------------------
            if (c == '(') {
                i++;
                num = helper(s);
            }
// ----------- addition to earlier code-------------------
            // Apply operation when operator or end of string
            if ((!isdigit(c) && c != ' ') || i == s.size() - 1) {
                if (op == '+') {
                    ans += last;
                    last = num;
                }
                else if (op == '-') {
                    ans += last;
                    last = -num;
                }

//-------------addition to earlier code -----------

                if (c == ')') {
                    return ans + last;
                }
// ---------- addition to earlier code ------------
                op = c;
                num = 0;
            }
        }
        return ans + last; 
    }
    int calculate(string s) {
       return helper(s);
    }

};

Jdecodes