Skip to main content

Simple Bracket Matching function

Software Development

Given a string containing characters interspersed with brackets, each bracket should have a closing bracket somewhere later in the string while keeping the order of the opening brackets in mind when closing then. That is the lastest opening bracket should be the first to be closed.

This was my revised solution...

My Solution

Essentially the solution ends up using a stack to keep track of the open brackets. My approach stores the expected closing bracket on the stack for each open bracket encountered. Once a closing bracket is encountered, it is compared with the bracket popped off the stack.

Common Edge Cases:

  • A string with no brackets will return True. The stack was never filled nor emptied and is empty at the end.

  • A string with more open brackets than closing ones must return False. The stack will have content at the end of the loop.

  • A string has a closing bracket where there was no earlier open bracket. Should return False. This would actually cause an IndexError when trying to pop off an already empty stack.