Basic Calculator

hard stack parsing

Problem

Given a string s representing an expression, implement a basic calculator to evaluate it.

Input"(1+(4+5+2)-3)+(6+8)"

Output23

Inner blocks evaluate to 8 and 14; (1+8-3) + 14 = 23.

expression

def calculate(s):
    result, sign, i = 0, 1, 0
    stack = []
    while i < len(s):
        c = s[i]
        if c == " ":
            i += 1; continue
        if c.isdigit():
            n = 0
            while i < len(s) and s[i].isdigit():
                n = n * 10 + int(s[i]); i += 1
            result += sign * n
            continue
        if c == "+": sign = 1
        elif c == "-": sign = -1
        elif c == "(":
            stack.append(result); stack.append(sign)
            result, sign = 0, 1
        elif c == ")":
            result = stack.pop() * result + stack.pop()
        i += 1
    return result

function calculate(s) {
  let result = 0, sign = 1, i = 0;
  const stack = [];
  while (i < s.length) {
    const c = s[i];
    if (c === " ") { i++; continue; }
    if (c >= "0" && c <= "9") {
      let n = 0;
      while (i < s.length && s[i] >= "0" && s[i] <= "9") { n = n * 10 + (s.charCodeAt(i) - 48); i++; }
      result += sign * n;
      continue;
    }
    if (c === "+") { sign = 1; }
    else if (c === "-") { sign = -1; }
    else if (c === "(") { stack.push(result); stack.push(sign); result = 0; sign = 1; }
    else if (c === ")") { result = stack.pop() * result + stack.pop(); }
    i++;
  }
  return result;
}

class Solution {
    public int calculate(String s) {
        int result = 0, sign = 1, i = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        while (i < s.length()) {
            char c = s.charAt(i);
            if (c == ' ') { i++; continue; }
            if (Character.isDigit(c)) {
                int n = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    n = n * 10 + (s.charAt(i) - '0'); i++;
                }
                result += sign * n;
                continue;
            }
            if (c == '+') sign = 1;
            else if (c == '-') sign = -1;
            else if (c == '(') { stack.push(result); stack.push(sign); result = 0; sign = 1; }
            else if (c == ')') { result = stack.pop() * result + stack.pop(); }
            i++;
        }
        return result;
    }
}

int calculate(string s) {
    int result = 0, sign = 1, i = 0;
    vector<int> stack;
    while (i < (int)s.size()) {
        char c = s[i];
        if (c == ' ') { ++i; continue; }
        if (isdigit(c)) {
            int n = 0;
            while (i < (int)s.size() && isdigit(s[i])) { n = n * 10 + (s[i] - '0'); ++i; }
            result += sign * n;
            continue;
        }
        if (c == '+') sign = 1;
        else if (c == '-') sign = -1;
        else if (c == '(') { stack.push_back(result); stack.push_back(sign); result = 0; sign = 1; }
        else if (c == ')') { int sg = stack.back(); stack.pop_back(); int prev = stack.back(); stack.pop_back(); result = sg * result + prev; }
        ++i;
    }
    return result;
}

Explanation

This calculator only has +, -, and parentheses — no multiplication — so the whole expression is just a sum of signed numbers. The clever part is using a stack to remember the sign context whenever we step into a bracket.

We keep a running result, a current sign (+1 or -1), and a stack. When we read a number, we add sign * number straight into result. A + sets sign = 1, a - sets sign = -1.

When we hit '(', we save the current result and sign on the stack, then reset them to start the inner sum fresh. When we hit ')', we pop the saved sign and saved result and combine: result = savedSign * result + savedResult. This applies the sign that was sitting in front of the whole parenthesis.

Example: "(1+(4+5+2)-3)+(6+8)". The inner (4+5+2) evaluates to 11, then 1+11-3 = 9, then (6+8) = 14, giving 9 + 14 = 23.

Every character is visited once, and the stack depth only grows with how deeply parentheses nest.

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