class Stack:
    """
    Una implementacion simplona de pila
    """
    def __init__(self):
        self.stack = []
    def is_empty(self):
        return len(self.stack) == 0
    def push(self, e):
        self.stack.insert(0, e)
    def pop(self):
        return self.stack.pop()
        
def pda(s):
    """
    Implementacion del PDA (notar que es determinista) y acepta por pila vacia
    """
    stack = Stack()
    for c in s:
        if c == "(":
            stack.push(c)
        elif c == ")":
            if stack.is_empty():
                return False
            else:
                stack.pop()
                
        
    if not stack.is_empty():
        return False
    return True
    
def imprimir_resultado(s):
    """
    Recibe un string de parentesis y muestra si el PDA acepta o rechaza
    """
    if pda(s): 
        tmp = "aceptado" 
    else:
        tmp = "rechazado"
    print ("El string %s es " + tmp) % s
    
# Probar con distintos strings  
imprimir_resultado("(()())()")
imprimir_resultado("(((((((")
imprimir_resultado(")))")
imprimir_resultado("())")
imprimir_resultado("()()()()")
imprimir_resultado("(((())))")