Assignment 2

Since today in class Danny said that assignment 2 is marked, I suspect that the grade should be something similar to the auto marker results shown on MarkUs. The auto test shows that have 38/38 passes, so I would like to share my solution here. I would be happy to compare my solution to someone else's solution or to hear suggestions on how my algorithm can be improved to become a more efficient one. 

class RegexTree:
    """A Regex Tree"""
    def __init__(self: 'RegexTree', regex: str) -> None:
        """Req: regex must be valid regular expression.
           Initialize a regular expression tree.
        """
        # Parse a regex into tree.
        self.root = self.regex_to_tree(regex)

    def regex_to_tree(self: 'RegexTree', regex: str):
        # Last index of the regex string.
        last = len(regex) - 1

        # Create RegexTreeNode for '0', '1', or 'e'.
        if (len(regex) == 1):
            return RegexTreeNode(regex, [])

        # Create StarNode for regex that ends with '*'.
        elif (regex[last] == '*'):
            return StarNode(self.regex_to_tree(regex[:last]))

        # Create BarNode or DotNode.
        elif (regex[0] == '(' and regex[last] == ')'):

            # Initialize parentheses counters.
            l_paren = 0
            r_paren = 0

            # Go through each character in the regex string, ignoring
            # the first and the last characters, which are '(' and ')'.
            for i in range(1, last):

                # Increment left parentheses counter when encounter one.
                if (regex[i] == '('):
                    l_paren += 1

                # Increment right parentheses counter when encounter one.
                elif (regex[i] == ')'):
                    r_paren += 1

                # Create BarNode when appropriate.
                elif (regex[i] == '|') and (l_paren == r_paren):
                    return BarNode(self.regex_to_tree(regex[1:i]),
                                   self.regex_to_tree(regex[(i + 1):last]))

                # Create DotNode when appropriate.
                elif (regex[i] == '.') and (l_paren == r_paren):
                    return DotNode(self.regex_to_tree(regex[1:i]),
                                   self.regex_to_tree(regex[(i + 1):last]))


def regex_match(r: 'RegexTree', s: str) -> bool:
    return node_match(r.root, s)


def node_match(node: 'RegexTreeNode', s: str) -> bool:
    # Check if a regex of length one (when the symbol of the
    # node is '0', '1' or 'e') matches a given string.
    if (node.children == []):
        return ((node.symbol == '0' and s == '0') or
                (node.symbol == '1' and s == '1') or
                (node.symbol == 'e' and s == ''))

    # Check if a regex of the form r* (when the symbol of the
    # node is '*') matches a given string.
    elif (node.symbol == '*'):
        # Return True if the given string s is an empty string.
        if (s == ''):
            return True

        # Otherwise check if the string s can be broken down into such strings,
        # where every string will match the regex node.
        else:
            for x in range(len(s)):
                if (node_match(node.children[0], s[:(len(s) - x)])):
                    # Return True if regex matches the whole string s.
                    # Keep breaking s into parts if regex matches some part
                    # of string s.
                    return node_match(node, s[(len(s) - x):])

            # Return False if there is part of string s that doesn't
            # match regex.
            return False

    # Check if a regex of the form (r1|r2) (when the symbol of the
    # node is '|') matches a given string.
    elif (node.symbol == '|'):
        return ((node_match(node.children[0], s)) or
                (node_match(node.children[1], s)))

    # Check if a regex of the form (r1.r2) (when the symbol of the
    # node is '.') matches a given string.
    elif (node.symbol == '.'):
        for i in range(len(s) + 1):
            # Partition the string s into all possible strings s1 and s2,
            # where s1 + s2 = s, until r1 matches s1 and r2 matches s2.
            if ((node_match(node.children[0], s[:i])) and
               (node_match(node.children[1], s[i:]))):
                return True

        # Return False if such a partition of s into s1 and s2 is impossible.
        return False