Python: Bracket Validator

Today let’s look at a bracket validator program. This will accept an input string that contains a bunch of brackets. It’ll check whether they are correctly opened and closed (in the right order).

The examples below will give a better idea of valid and invalid inputs:

s1 = ['(((}})))']
bracket_validator(s1) # returns False

s2 = '[](([[{{}}]]))'
bracket_validator(s2) # returns True

Now let’s have a look at the code:

# Problem: Bracket validator (balanced vs unbalanced) (using Stack)

def bracket_validator(s):
    
    if len(s)%2 != 0:
        return False
    
    openers_to_closers = {
        '(' : ')',
        '{' : '}',
        '[' : ']'
    }
    
    openers = openers_to_closers.keys()
    closers = openers_to_closers.values()
    
    openers_stack = []
    
    for char in s:
        
        if char in openers:
            openers_stack.append(char)
        elif char in closers:
            if not openers_stack:
                return False
            else:
                last_unclosed_opener = openers_stack.pop()
                if openers_to_closers[last_unclosed_opener] != char:
                    return False
    
    if len(openers_stack) == 0:
        return True
        

s1 = ['(((}})))']
bracket_validator(s1) # returns False

s2 = '[](([[{{}}]]))'
bracket_validator(s2) # returns True

The very first thing we do is check the input is odd or even in length. If it is odd, return False.

Next we maintain a dictionary of openers to closers and turn those into sets of openers and closers. We also maintain a openers_stack as a list.

We then run a for loop going through each character in the input string. If the character is in opener, add it to the openers stack.

If we find a closer and openers stack doesn’t is empty, return False. If openers stack is not empty, pop the top element from the openers stack and check whether our current closer is the correct closing pair for the top element in the stack (last unclosed opener).

For example, if our closer is ] and the last unclosed opener is [ then we’re good. If not, we return False.

At the very end if length of openers_stack is zero, return True.