stack_02.py

#!/usr/bin/python3
# ==================================================================
# From: www.youtube.com/watch?v=T7CapM-xGaU
#       determine if parenthesis are balanced
#
# Use a stack to check whether or not a string
# has balanced parentheses.
#
# Example:
#    (), ()(), {{{[]}}}        <-- balanced
#    ()), {{{}}], [][]]        <-- not balanced
#
# ==================================================================

class Stack():
    '''Stach datas structure'''
    def __init__(self):
        self.items = []

    def push(self,item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def is_empty(self):
        return self.items == []

    def peek(self):
        if not self.is_empty():
            return self.ittems[-1]

    def get_stack(self):
        return self.items

def is_match(p1,p2):
    '''Test if open and close parentheses match'''
    if p1 == "(" and p2 == ")":
        return True
    elif p1 == "{" and p2 == "}":
        return True
    elif p1 == "[" and p2 == "]":
        return True
    else:
        return False

def are_parens_balanced(paren_string):
    '''does string contain bananced parentheses'''
    s = Stack()
    is_balanced = True
    index = 0

    while index < len(paren_string) and is_balanced:
        paren = paren_string[index]   # get char from string
        
        ##print("paren[{}] = {}".format(index,paren))

        if paren in "({[":            # open parenthesis
            s.push(paren)
        elif not paren in ")}]":      # ignore non-close parenthesis
            pass                       
        else:                         # test for a matching close parenthesis
            if s.is_empty():
                is_balanced = False
            else:
                top = s.pop()         # get top of stack
                if not is_match(top,paren):
                    is_balanced = False
        index += 1

    ##print("stack = {}".format(s.get_stack()))

    if s.is_empty() and is_balanced:
        return True
    else:
        return False

# ------------------------------------------------------------------
# main
# ------------------------------------------------------------------

strs = [ "()()[]{}",                # balanced
         "((([{{}}])))",            # balanced
         "()([]{}",                 # not balanced
         "((([{{}])))",             # not balanced
         "abc(xyz[olp]qsr)asd"      # balanced
       ]

for s in strs:
    b = are_parens_balanced(s)
    if b:
        print("balanced      {}".format(s))
    else:
        print("not balanced  {}".format(s))