balanced_delimiters

balanced_delimiters.py

#!/usr/bin/python

def balanced_delimiters(s):
    '''
    This function determines if the input string ('s') has balanced number of braces. 
    All the opening braces are appended to 'data'. As soon as a closing brace is
    encountered, the last entry in 'data' is matched with it. If the closing brace is
    the opposite of the last element in 'data' - opening braces and their corresponding
    closing braces are stored in 'braces', we have a match and the the last element
    is popped-off 'data'. This process is continued till either all the elements of 's'
    have been visited or till the first closing brace in 's' is found which does not have
    a matching opening brace at the last position of 'data'.

    Time complexity  : O(n)
    Space complexity : O(n)
    '''

    data = []
    braces = {'{':'}', '(':')', '[':']'}

    for char in s:
        if char in braces:
            data.append(char)
        else:
            if not data or char != braces[data[-1]]:
                return False
            else:
                data.pop()
    return True if not data else False


if __name__ == '__main__':
    strings = ['(){}', '([{}])', '({})', '([)]', '(', ')', '([})']
    
    for elem in strings:
        print balanced_delimiters(elem)