Basic Calculator | Stack Expression Evaluation | Stack

Overview

Basic calculator: evaluate expression with non-negative integers, +, - and (, ). No * or /. The twist: minus can negate a following term, and parentheses change the effective sign. Use a stack to store the sign in effect at each open paren; accumulate the current number and apply the current sign when you see + or - or end.

When to Use

Expression with + - ( ) — stack of signs per nesting level.
Sign propagation — e.g. -(1+2) means -1-2; stack tracks sign at each (
Postfix or two-stack — alternate: convert to RPN then evaluate.

How It Works

Sign stack: push 1. Current sign = 1, result = 0, num = 0. Scan: digit → num = num10 + digit. '+' or '-' → add signnum to result, set num=0, set sign = 1 or -1 by operator. '(' → push current sign (sign before this group). ')' → pop sign. At end add sign*num. Result is the total.

Example 1: Stack of Signs

function calculate(s: string): number {
  const stack: number[] = [1];
  let sign = 1, result = 0, num = 0;
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (c >= '0' && c <= '9') num = num * 10 + Number(c);
    else if (c === '+' || c === '-') {
      result += sign * num; num = 0;
      sign = stack[stack.length - 1] * (c === '+' ? 1 : -1);
    } else if (c === '(') stack.push(sign);
    else if (c === ')') stack.pop();
  }
  return result + sign * num;
}

Time: O(n). Space: O(depth of parens).

Example 2: Cleaner Sign Handling

On '(', push current sign. On ')', pop. On '+', set sign = top; on '-', set sign = -top. Then result += sign * num and reset num when you see an operator or end.

function calculate2(s: string): number {
  const stack: number[] = [1];
  let sign = 1, res = 0, num = 0;
  for (const c of s) {
    if (c === ' ') continue;
    if (c >= '0' && c <= '9') num = num * 10 + Number(c);
    else {
      res += sign * num; num = 0;
      if (c === '+') sign = stack[stack.length - 1];
      else if (c === '-') sign = -stack[stack.length - 1];
      else if (c === '(') stack.push(sign);
      else if (c === ')') stack.pop();
    }
  }
  return res + sign * num;
}

Example 3: Step-by-Step Trace

"1 + (2 - 3) + 4". Stack [1], sign=1, res=0. '1': num=1. '+': res=1, num=0, sign=1. '(': push 1, stack [1,1]. '2': num=2. '-': res=1+2=3, num=0, sign=-1. '3': num=3. ')': res=3+(-1)3=0, pop stack [1]. '+': sign=1. '4': num=4. End: res+signnum = 0+4 = 4.

Example 4: Edge Cases

Leading minus: "-1+2" — start with sign=-1 (e.g. pretend '0+' before first term) or push -1 on stack; then -1 applies to 1.
Single number: "42" — num=42, no operator → result = 0 + 1*42 = 42.
Nested: "1-(2-(3))" — stack and sign updates propagate correctly.
Spaces: skip in loop.

Example 5: With * and /

Basic Calculator II: no parens, + - /. Use one stack of numbers; on + push num, on - push -num, on / pop, apply to num, push result. Or single pass with prevOp: when you see + or -, add term; when * or /, merge with previous term.

Summary

Basic calculator (+, -, ( )): stack of signs; on '(' push sign, on ')' pop; on + - flush num with current sign and update sign. See Valid Parentheses, Decode String.