'''
   Aufgabe 4 (Bonusaufgabe): Regulaere Ausdruecke parsen
'''

class State(dict):
    def __hash__(self):
        return id(self)
    def add(self, char, state):
        if char in self:
            self[char].add(state)
        else:
            self[char] = set([state])
    def recognize(self, strng, final):
        if strng == '':
            return any(state in final for state in self.closure())
        for epsi in self.closure():
            for state in epsi.get(strng[0], []):
                if state.recognize(strng[1:], final):
                    return True
        return False
    def closure(self):
        reachable = set([self])
        agenda = [self]
        while agenda:
            state = agenda.pop()
            for other in state.get('', []):
                reachable.add(other)
                agenda.append(other) 
        return reachable

class NFA:
    def __init__(self, initial, final):
        self.initial = initial
        self.final = final
    def recognize(self, string):
        return self.initial.recognize(string, self.final)
    def generate(self):
        stack = [(self.initial, '')]
        while stack:
            (state, strng) = stack.pop(0)
            if state in self.final:
                yield strng
            for (char, tgts) in state.items():
                for tgt in tgts:
                    stack.append((tgt, strng + char))
    @staticmethod
    def singleton(char):
        final = set([State()])
        return NFA(State([(char, final)]), final)
    def concat(self, other):
        for final in self.final:
            final.add('', other.initial)
        return NFA(self.initial, other.final)
    def union(self, other):
        initial = State()
        initial.add('', self.initial)
        initial.add('', other.initial)
        return NFA(initial, self.final | other.final)
    def star(self):
        initial = State()
        initial.add('', self.initial)
        for final in self.final:
            final.add('', initial)
        return NFA(initial, set([initial]))
    def plus(self):
        for final in self.final:
            final.add('', self.initial)
        return self


# Aufgabe 4
def parse_regexp(strng):
    # Dein Code hier
    pass