Basic Calculator III

hard string stack math recursion

Problem

Evaluate an arithmetic expression with non-negative integers, +, −, ×, ÷ and parentheses. Integer division truncates toward zero.

Inputs = "2*(5+5*2)/3+(6/2+8)"

Output21

Recurse on '(' to evaluate the inner expression, then treat the returned int as one more operand of the outer expression.

expression

def calculate(s):
    i = [0]
    def helper():
        stack, num, op = [], 0, '+'
        while i[0] < len(s):
            c = s[i[0]]; i[0] += 1
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == '(':
                num = helper()
            if (c in '+-*/)' or i[0] == len(s)) and c != ' ':
                if op == '+': stack.append(num)
                elif op == '-': stack.append(-num)
                elif op == '*': stack.append(stack.pop() * num)
                elif op == '/': stack.append(int(stack.pop() / num))
                num, op = 0, c
                if c == ')': break
        return sum(stack)
    return helper()

function calculate(s) {
  let i = 0;
  const isDigit = (c) => c >= '0' && c <= '9';
  function helper() {
    const stack = []; let num = 0, op = '+';
    while (i < s.length) {
      const c = s[i++];
      if (isDigit(c)) num = num * 10 + (c.charCodeAt(0) - 48);
      else if (c === '(') num = helper();
      if ("+-*/)".includes(c) || i === s.length) {
        if (op === '+') stack.push(num);
        else if (op === '-') stack.push(-num);
        else if (op === '*') stack.push(stack.pop() * num);
        else if (op === '/') stack.push(Math.trunc(stack.pop() / num));
        num = 0; op = c;
        if (c === ')') break;
      }
    }
    return stack.reduce((a, b) => a + b, 0);
  }
  return helper();
}

class Solution {
    int i = 0;
    public int calculate(String s) { return helper(s); }
    int helper(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int num = 0; char op = '+';
        while (i < s.length()) {
            char c = s.charAt(i++);
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            else if (c == '(') num = helper(s);
            if ("+-*/)".indexOf(c) >= 0 || i == s.length()) {
                if (op == '+') stack.push(num);
                else if (op == '-') stack.push(-num);
                else if (op == '*') stack.push(stack.pop() * num);
                else if (op == '/') stack.push(stack.pop() / num);
                num = 0; op = c;
                if (c == ')') break;
            }
        }
        int sum = 0; for (int v : stack) sum += v; return sum;
    }
}

class Solution {
    int i = 0; string str;
    int helper() {
        vector<int> st; int num = 0; char op = '+';
        while (i < (int)str.size()) {
            char c = str[i++];
            if (isdigit(c)) num = num * 10 + (c - '0');
            else if (c == '(') num = helper();
            if (string("+-*/)").find(c) != string::npos || i == (int)str.size()) {
                if (op == '+') st.push_back(num);
                else if (op == '-') st.push_back(-num);
                else if (op == '*') { int t = st.back(); st.pop_back(); st.push_back(t * num); }
                else if (op == '/') { int t = st.back(); st.pop_back(); st.push_back(t / num); }
                num = 0; op = c;
                if (c == ')') break;
            }
        }
        int sum = 0; for (int v : st) sum += v; return sum;
    }
public:
    int calculate(string s) { str = s; return helper(); }
};

Explanation

This is the full calculator with + - * / and parentheses. The clean idea is to handle precedence with a stack of additive terms (like Basic Calculator II) and handle parentheses with recursion: whenever we see '(' we call a helper to evaluate the inside, and that helper returns a single number.

The helper() function keeps its own stack, a running num, and the previous operator op. Digits build up num. A '(' means "evaluate the sub-expression now" — so we recurse, and the value that comes back simply becomes the next num.

At every operator boundary (or end, or a closing ')') we apply the pending op: push num for +, -num for -, or fold into the top of the stack for * and /. When we hit ')' we break and return sum(stack) for that parenthesised group.

Example: "2*(5+5*2)/3". The inner (5+5*2) recurses and returns 15. Back outside, num becomes 15, so we compute 2*15=30 then 30/3=10.

The shared index i (a reference, not a copy) lets the recursive calls keep scanning the same string, so every character is read exactly once.

Time: O(n) Space: O(n)