Balanced Parentheses
  • Parentheses need to be in a balanced fashion
  • Balanced parentheses means that each opening symbol has a corresponding closing symbol and the pairs of parentheses are properly nested
  • # StackModule.py
    #!/usr/bin/python3
    import copy
    
    class Stack(object):
        def __init__(self):
            self.items = []
    
        def isEmpty(self):
            return len(self.items) == 0
    
        def push(self, element):
            try:
                self.items.append(element)
                return True
            except Exception as e:
                return False
    
        def pop(self):
            try:
                return self.items.pop()
            except Exception as e:
                return None
    
        def peek(self):
            try:
                return self.items[len(self.items)-1]
            except Exception as e:
                return None
    
        def size(self):
            return len(self.items)
    
        def __str__(self):
            output = []
    
            items = copy.copy(self.items)
            items.reverse()
    
            for item in items:
                output.append(str(item))
    
            return " -> ".join(output)
                
    #!/usr/bin/python3
    from StackModule import Stack
    
    def balance(string):
        s = Stack()
        balanced = True
    
        for c in string:
            if c in '([{':
                s.push(c)
            elif c in ')]}':
                peek = s.pop()
                if not matches(peek, c):
                    return False
    
        return s.size() == 0
    
    def matches(o,c):
        if o is None:
            return False
        opens = "([{"
        closers = ")]}"
        match = opens.index(o) == closers.index(c)
        return match
    
    if __name__ == '__main__':
        print(balance('(5+6)*(7+8)/(4+3)')) # True
        print(balance('((()))')) # True
        print(balance('(()')) # False
        print(balance('{({([][])}())}')) # True
        print(balance('[{()]')) # False
        print(balance('[{])')) # False
        print(balance('[{]}')) # False
                
    Reference
  • Problem Solving with Algorithms and Data Structures using Python