Basic Calculator III

Hard · Stack · Explanation and code example

Solve Isolated Expressions With Recursion

How it works

Parentheses naturally suggest recursion. When we encounter an opening parenthesis, we can recursively evaluate everything inside it and treat the result as a single number. This makes the problem cleaner since each recursive call handles one level of nesting. The base case is a simple expression without parentheses, which we evaluate using the same logic as Basic Calculator II.

Steps

  1. Append a sentinel @ to the string. Use an index variable shared across recursive calls.
  2. Define a recursive solve function:
    • Initialize a stack, current number, and previous operator (+).
    • While the index is within bounds:
      • If the character is (, increment the index and recursively call solve to get the inner result.
      • If it's a digit, build the current number.
      • Otherwise, apply the previous operator (push for +/-, compute for *//).
      • If it's ), break out of the loop.
      • Reset the number and update the operator.
    • Return the sum of the stack.
  3. Call solve starting from index 0 and return its result.

Complexity

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

Where n is the length of the expression

Things to watch for

Not Resetting State When Entering Parentheses

When encountering an opening parenthesis, you must save the current operator and reset to a default state (usually +). Failing to reset causes the operator before the parenthesis to be applied incorrectly inside.

Incorrect Handling of Closing Parenthesis

When a closing parenthesis is encountered, you must sum all values inside the parentheses and then apply the saved operator from before the opening parenthesis. Missing either step produces wrong results.

Mixing Up Operator Precedence with Parentheses

Multiplication and division still have higher precedence than addition and subtraction, even inside parentheses. The parentheses only group sub-expressions; they do not change the relative precedence of operators within them.

Off-by-One Errors in Index Management with Recursion

When using recursion to handle parentheses, the index must be shared across recursive calls (e.g., using a mutable reference or array). Failing to properly advance the index after processing a sub-expression causes characters to be processed multiple times or skipped.

Forgetting the Sentinel Character

Many solutions append a sentinel character (like @) to trigger processing of the final number. Without this, the last number or sub-expression may not be evaluated.

Python code example

class Solution:
    def calculate(self, s: str) -> int:
        def evaluate(x, y, operator):
            if operator == "+":
                return x
            if operator == "-":
                return -x
            if operator == "*":
                return x * y
            return int(x / y)

        def solve(i):
            stack = []
            curr = 0
            previous_operator = "+"

            while i[0] < len(s):
                c = s[i[0]]
                if c == "(":
                    i[0] += 1
                    curr = solve(i)
                elif c.isdigit():
                    curr = curr * 10 + int(c)
                else:
                    if previous_operator in "*/":
                        stack.append(evaluate(stack.pop(), curr, previous_operator))
                    else:
                        stack.append(evaluate(curr, 0, previous_operator))

                    if c == ")":
                        break

                    curr = 0
                    previous_operator = c

                i[0] += 1

            return sum(stack)

        s += "@"
        return solve([0])

C++ code example

class Solution {
public:
    int calculate(string s) {
        s += "@";
        int i = 0;
        return solve(s, i);
    }

private:
    int evaluate(char op, int x, int y) {
        if (op == '+') {
            return x;
        } else if (op == '-') {
            return -x;
        } else if (op == '*') {
            return x * y;
        }

        return x / y;
    }

    int solve(string& s, int& i) {
        stack<int> stk;
        int curr = 0;
        char previousOperator = '+';

        while (i < s.length()) {
            char c = s[i];

            if (c == '(') {
                i++;
                curr = solve(s, i);
            } else if (isdigit(c)) {
                curr = curr * 10 + (c - '0');
            } else {
                if (previousOperator == '*' || previousOperator == '/') {
                    int top = stk.top();
                    stk.pop();
                    stk.push(evaluate(previousOperator, top, curr));
                } else {
                    stk.push(evaluate(previousOperator, curr, 0));
                }

                if (c == ')') {
                    break;
                }

                curr = 0;
                previousOperator = c;
            }

            i++;
        }

        int ans = 0;
        while (!stk.empty()) {
            ans += stk.top();
            stk.pop();
        }

        return ans;
    }
};
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