Maintained by Vikas Dulgunde, software engineer
You are handed a string that contains nothing but the six bracket characters: round, square, and curly, in their opening and closing forms. Your job is to report whether the brackets line up into a well-formed sequence.
Three conditions all have to hold. Each opening bracket must eventually be closed by a bracket of the exact same type. The closings have to respect nesting, so the most recently opened bracket is the next one that gets closed. And there can be no stray closing bracket that never had a matching opener.
Return true when all three hold and false otherwise. A string like a single unmatched opener counts as invalid because it is never closed.
The natural way to think about it is order of resolution. Whenever you meet a closing bracket, the opener it pairs with should be the last one still waiting. That last-in, first-out behavior is exactly what a stack gives you.
Each pair opens and closes immediately, so every bracket finds its partner with nothing left over.
The closing square bracket does not match the round bracket that is still open, so the types disagree.
The brackets are interleaved rather than nested. The round bracket should close before the square one, but it closes second, breaking the order.
The square pair sits cleanly inside the curly pair, so nesting is respected end to end.
Visible test cases
When you read a closing bracket, which opening bracket does it need to match? It is always the one most recently opened and not yet closed.
A structure that hands back the last thing you put into it is exactly what you need. Push openers, and pop to check on a closer.
Two ways to fail: a closer with the wrong opener on top (or no opener at all), and openers still sitting in the stack once the string ends.
Any valid string can be reduced to empty by deleting an adjacent matching pair over and over. If you keep stripping (), [], and {} until nothing changes, a balanced string collapses to an empty string.
Walk the string once. Push opening brackets onto a stack; on a closing bracket, the top of the stack must be its matching opener, so pop and compare. A clean run leaves the stack empty.