Stack

Linear Helpers

Signal

Matching/balance/nesting, undo last

Template

Push openers, pop and verify on closers.

Worked example (1)

#8

Stack

Stack

Given a string of brackets ()[]{}, decide whether they are correctly matched and nested.

function isValid(s: string): boolean {
  const match: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
  const stack: string[] = [];
  for (const c of s) {
    if (c === '(' || c === '[' || c === '{') stack.push(c);
    else if (stack.pop() !== match[c]) return false;
  }
  return stack.length === 0;
}

def valid_parentheses?(s)
  match = { ')' => '(', ']' => '[', '}' => '{' }
  stack = []
  s.each_char do |c|
    if '([{'.include?(c)
      stack.push(c)
    elsif stack.pop != match[c]
      return false
    end
  end
  stack.empty?
end