> A recursive solution springs to mind, but I can recall implementing recursive solutions in production code only a few tens of times over a ten year career.

If you are not comfortable with recursion, just remember: Recursion is really just a free stack. To use your example:

Whenever you see an opening brace, push onto the stack. (Or, make a recursive call, which goes onto the call stack...)

Whenever you see a closing brace, pop off the stack. (Or, return from the recursive call, which then pops off the call stack...)

If the stack isn't empty at end of input, then there are mismatched opening braces. If you ever try to pop from an empty stack, then there are mismatched closing braces.