Basic Calculator

Intuitionturning each parenthesized expression into one signed number

Ignore parentheses for a moment. A flat expression can be evaluated by remembering two things: the result accumulated so far and the sign that belongs to the next number. When you finish reading a number, add sign times number to result. A plus sets sign to 1, and a minus sets it to -1. Spaces do not change either value.

Parentheses temporarily change the place where numbers are being added. When you read an opening parenthesis, save the outside result and sign, then start a fresh inner result at zero. When the closing parenthesis arrives, the inner result is complete: multiply it by the saved sign and add it to the saved result. The stack stores these saved pairs, one pair for each currently open parenthesis.

Approachone pass, with the stack holding only unfinished outer expressions

1. 1Scan the string from left to right while maintaining result, sign, and num. Keeping num separate lets a multi-digit number be completed before it is added.
2. 2When you read a digit, append it to num with num = num * 10 + digit. Without this accumulation, 123 would be treated as three separate terms instead of one number.
3. 3When you read plus or minus, add sign * num to result, clear num, and set sign to 1 or -1 for the next term. Flushing num before changing sign prevents the operator from being applied to the wrong number.
4. 4When you read an opening parenthesis, push the current result and sign onto the stack, then reset result to 0 and sign to 1. The inner expression must be evaluated independently, while the saved pair remembers how it will rejoin the outside.
5. 5When you read a closing parenthesis, first add sign * num so the final inner number is not lost. Then multiply the inner result by the saved sign and add the saved outer result, popping those values in reverse order from the stack.
6. 6After the scan ends, add sign * num one final time. The input has no operator after its last number, so the last number has not yet been flushed by a plus, minus, or closing parenthesis.
7. 7Return result. Every parenthesized expression has already been collapsed when its closing parenthesis was processed, so no second pass or post-processing is needed.

Complexitythe scan is linear even when parentheses are deeply nested

Annotated solutionC++ · iterative stack · the version that handles nesting in one pass

#include <cctype>
#include <stack>
#include <string>

using namespace std;

class Solution {
public:
    int calculate(string s) {
        stack<int> st;
        int result = 0;
        int sign = 1;
        int num = 0;

        for (char c : s) {
            if (isdigit(static_cast<unsigned char>(c))) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                result += sign * num;
                num = 0;
                sign = (c == '+') ? 1 : -1;
            } else if (c == '(') {
                st.push(result);
                st.push(sign);
                result = 0;
                sign = 1;
            } else if (c == ')') {
                result += sign * num;
                num = 0;

                result *= st.top();
                st.pop();
                result += st.top();
                st.pop();
            }
        }

        result += sign * num;
        return result;
    }
};

The two pushes at an opening parenthesis deliberately use result first and sign second. The close operation therefore sees the sign at the top, applies it to the completed inner result, and then retrieves the saved outer result. Resetting result and sign after the push is equally important: without it, the inner expression would inherit terms that belong outside the parentheses.

The recursive alternativea different arrangement, with the same asymptotic cost

You can replace the explicit stack with recursive calls. A parser evaluates the expression inside an opening parenthesis and returns when it reaches the matching close. The caller then treats that returned value like one number. This is not an asymptotic optimisation: the explicit stack becomes the runtime call stack, so both methods use O(n) extra space in the worst nesting depth.

#include <cctype>
#include <string>

using namespace std;

class Solution {
private:
    int parse(const string& s, int& index) {
        int result = 0;
        int sign = 1;

        while (index < static_cast<int>(s.size())) {
            char c = s[index];

            if (c == ' ') {
                ++index;
            } else if (isdigit(static_cast<unsigned char>(c))) {
                int num = 0;
                while (index < static_cast<int>(s.size()) &&
                       isdigit(static_cast<unsigned char>(s[index]))) {
                    num = num * 10 + (s[index] - '0');
                    ++index;
                }
                result += sign * num;
                sign = 1;
            } else if (c == '+') {
                sign = 1;
                ++index;
            } else if (c == '-') {
                sign = -1;
                ++index;
            } else if (c == '(') {
                ++index;
                result += sign * parse(s, index);
                sign = 1;
            } else {
                ++index;
                return result;
            }
        }

        return result;
    }

public:
    int calculate(string s) {
        int index = 0;
        return parse(s, index);
    }
};

The recursive version buys a direct correspondence between nesting and function calls, which can make the parser easier to extend. The iterative version avoids dependence on the language call stack and keeps all unfinished expressions in visible storage. Choose recursion for the cleaner structural match; choose the explicit stack when input nesting may approach the stack limit.

Common mistakesthree wrong shapes that look plausible in a quick review