Patterns

Push openers; pop and check match on closers

When to useBrackets/parentheses validation, undo operations

iterative

Stack Applications

stack_applications

Valid Parentheses

valid_parentheses

Remove Adjacent Duplicates in String

remove_adjacent_duplicates_in_string

Backspace String Compare

backspace_string_compare

Evaluate Reverse Polish Notation

evaluate_reverse_polish_notation

Stack Intro

stack_intro

Baseball Scorekeeping

baseball_scorekeeping

Amazon OA — Matching Brackets

amazon_oa_matching_brackets

Basic Calculator Ihard

basic_calculator_i · no slots

Basic Calculator IImedium

basic_calculator_ii · no slots

INITIALIZE

empty stack; map of pairs if needed

const pairs = { ')': '(', ']': '[', '}': '{' };
const stack = [];

const pairs = { ')': '(', ']': '[', '}': '{' };
const stack = [];

const stack = [];

const stack = [];

const stack = [];

const pairs = { ')': '(', ']': '[', '}': '{' };
const stack = [];

const stack = [];

const pairs = { ')': '(', ']': '[', '}': '{' };
const stack = [];

—

TRAVERSE

for-of input

for (const ch of s) {

for (const ch of s) {

for (const ch of s) {

for (const ch of str) {

for (const token of tokens) {

for (const ch of s) {

for (const op of ops) {

for (const ch of s) {

—

[MATCH]

if opener push; if closer pop and verify

  if (ch in pairs) {
    if (stack.pop() !== pairs[ch]) return false;
  } else {
    stack.push(ch);
  }

  if (ch in pairs) {
    if (stack.pop() !== pairs[ch]) return false;
  } else {
    stack.push(ch);
  }

  if (stack.length > 0 && stack[stack.length - 1] === ch) {
    stack.pop();
  } else {
    stack.push(ch);
  }

  if (ch === '#') {
    stack.pop();
  } else {
    stack.push(ch);
  }

  if (['+', '-', '*', '/'].includes(token)) {
    const b = stack.pop();
    const a = stack.pop();
    if (token === '+') stack.push(a + b);
    else if (token === '-') stack.push(a - b);
    else if (token === '*') stack.push(a * b);
    else stack.push(Math.trunc(a / b));
  } else {
    stack.push(parseInt(token));
  }

  if (ch in pairs) {
    if (stack.pop() !== pairs[ch]) return false;
  } else {
    stack.push(ch);
  }

  if (op === 'X') {
    stack.push(stack[stack.length - 1] * 2);
  } else if (op === '+') {
    stack.push(stack[stack.length - 1] + stack[stack.length - 2]);
  } else if (op === 'Z') {
    stack.pop();
  } else {
    stack.push(Number(op));
  }

  if (ch in pairs) {
    if (stack.length === 0 || stack.pop() !== pairs[ch]) return false;
  } else {
    stack.push(ch);
  }

—

RETURN

stack.length === 0 (or other final check)

return stack.length === 0;

return stack.length === 0;

return stack.join('');

return build(s) === build(t);

return stack.pop();

return stack.length === 0;

return stack.reduce((sum, n) => sum + n, 0);

return stack.length === 0;

—