1 · Model, solve and test · 25 MIN

Validate nested brackets with a stack

Validate nested brackets with a stack

Nested structures require remembering the most recently opened item. Push each opening bracket onto a stack and pop when its matching closing bracket appears. Reject an unexpected closer immediately and require an empty stack at the end. This exercise accepts only bracket characters; it deliberately does not claim to parse JavaScript strings, comments or templates. State that restricted input language before implementing the algorithm.

The next closer must match the most recent unmatched opener.

Read the example

function solve(input){const stack=[],pairs={')':'(',']':'[','}':'{'};for(const char of input){if('([{'.includes(char))stack.push(char);else if(stack.pop()!==pairs[char])return false}return stack.length===0}
console.log(JSON.stringify(solve("([]{})")));

true

Your challenge

Given a string containing only (), [] and {}, return whether every bracket closes in the correct nested order. An empty string is valid.

Solution cost: O(n) character visits. time · O(n) stack in the worst case. space

Common trap

Counting openers and closers cannot distinguish ([)] from a properly nested expression.