Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Stack Parsing

Guide 4 of 6 · Path 4 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardstack-parsing

Basic Calculator

Problem (restated)

Evaluate expression with +, -, parentheses, non-negative integers, and spaces. No * or /.

Intuition

Scan left-to-right accumulating res and current number. On ( push res and sign, reset; on ) apply saved sign and add outer res.

Approaches

Sign stack for parentheses

Tested only
Time O(n)Space O(n)

Idea. Treat unary context as signed terms. Parentheses open a nested accumulator.

Walkthrough. “(1+(4+5+2)-3)+(6+8)” → 23.

Trade-offs. Multi-digit numbers need running num; spaces are no-ops.

Solution
export function calculate(s: string): number {
  let res = 0;
  let num = 0;
  let sign = 1;
  const stack: number[] = [];
  for (let i = 0; i < s.length; i++) {
    const ch = s[i]!;
    if (ch >= "0" && ch <= "9") {
      num = num * 10 + (ch.charCodeAt(0) - 48);
    } else if (ch === "+" || ch === "-") {
      res += sign * num;
      num = 0;
      sign = ch === "+" ? 1 : -1;
    } else if (ch === "(") {
      stack.push(res);
      stack.push(sign);
      res = 0;
      sign = 1;
    } else if (ch === ")") {
      res += sign * num;
      num = 0;
      res *= stack.pop()!;
      res += stack.pop()!;
    }
  }
  return res + sign * num;
}

export function calculate(s: string): number {
  let res = 0;
  let num = 0;
  let sign = 1;
  const stack: number[] = [];
  for (let i = 0; i < s.length; i++) {
    const ch = s[i]!;
    if (ch >= "0" && ch <= "9") {
      num = num * 10 + (ch.charCodeAt(0) - 48);
    } else if (ch === "+" || ch === "-") {
      res += sign * num;
      num = 0;
      sign = ch === "+" ? 1 : -1;
    } else if (ch === "(") {
      stack.push(res);
      stack.push(sign);
      res = 0;
      sign = 1;
    } else if (ch === ")") {
      res += sign * num;
      num = 0;
      res *= stack.pop()!;
      res += stack.pop()!;
    }
  }
  return res + sign * num;
}

Template connection

Stack parsing of nested expressions.

Reflection