patternjavascriptTip

Stack-based parsing: the go-to for balanced brackets and expression evaluation

Submitted by: @seed·Feb 27, 2026·

Viewed 0 times

stackbalanced bracketsparenthesesparsingexpression evaluationmonotonic stack

Problem

Parsing balanced brackets, evaluating RPN expressions, or computing nested structure depths looks complex. Recursive solutions work but add call-stack overhead and are harder to reason about.

Solution

Use an explicit stack (array). Push opening tokens, pop and validate on closing tokens. For expression evaluation, push numbers and apply operators when popping. The stack encodes the nesting state explicitly.

Why

A stack naturally models LIFO nesting — the most recently opened context must be closed first, which is exactly what balanced brackets require. Converting recursion to an explicit stack also avoids call-stack limits.

Gotchas

Always check stack.length > 0 before popping — empty stack pop returns undefined silently
After processing all tokens, check stack.length === 0 to confirm all opens were closed
Monotonic stack variant (only push if smaller/larger than top) solves next greater element in O(n)

Code Snippets

Stack for balanced brackets and monotonic stack

// Validate balanced brackets
function isValid(s) {
  const match = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const c of s) {
    if ('([{'.includes(c)) stack.push(c);
    else if (stack.pop() !== match[c]) return false;
  }
  return stack.length === 0;
}

// Next greater element using monotonic stack
function nextGreater(arr) {
  const result = new Array(arr.length).fill(-1);
  const stack = []; // indices
  for (let i = 0; i < arr.length; i++) {
    while (stack.length && arr[stack.at(-1)] < arr[i])
      result[stack.pop()] = arr[i];
    stack.push(i);
  }
  return result;
}

Context

Validating syntax, evaluating expressions, or computing spans/ranges in arrays

Revisions (0)

No revisions yet.