Week 10: Looking over A2

Since I'm writing this a few weeks late, I realize there may be errors here, but I decided to work out all the kinks in my A2 code, just for kicks (alliteration!).

I'll start with the first error:

 AssertionError: False is not true : Rejects valid regex: ((0|1)*|2)*

For my A2 code, I used several helper functions, and turns out that some were quite useless:

I made a function called num_parentheses, and used it in balanced_parentheses:

def balanced_parentheses(s: str) -> bool:

    if num_parentheses(s) == 2:

        return s[0] == '(' and s[-1] == ')' 

    if len(s) == 1:

        return s == '0' or s =='1' or s =='2' or s == 'e'

    i = []

    for char in s:

        if char == '(':

            i.append('(')

        if char == ')':

            if len(i) == 0:

                return False

            else:

                i.pop()

    return len(i) == 0

Look familiar? This is very similar to Dan's code for stacks and balanced parentheses, minus the stack ADT.

The problem here was very straightforward:

  if num_parentheses(s) == 2:

        return s[0] == '(' and s[-1] == ')' 

This code would lead to an error for any regex which did not have ')' as the last character, such as ((0|1)*|2)*. Upon taking it out, the code worked for this case, as well as the next failure (grumble).

Another failure in my code was:

AssertionError: None is not true : Rejects valid match: (DotTree(Leaf('e'), Leaf('2')), '2')

In order to figure out the mistake in my code, I scrutinized the section handling DotTrees:

if r.symbol == '.':

        for i in range(0, len(s)):

            s1 = s[0:i+1]

            s2 = s[i+1:]

            if regex_match(r.children[0], s1) and \

               regex_match(r.children[1], s2):

                return True

Looking at the length of the string s, I realized that my code did not account for the special case where s is one character long! All I needed to add was this:

if len(s) == 1:

            return regex_match(r.children[0], '') and \

                   regex_match(r.children[1], s) or\

                   regex_match(r.children[1], '') and \

                   regex_match(r.children[0], s)

And the code worked.

For the next failure:

AssertionError: None is not true : Rejects valid match: (DotTree(StarTree(Leaf('1')), StarTree(Leaf('2'))), '2222')

This time, the problem with my code was that I assumed no matter what, the string would be at least 1 character long in order to match, especially with the Bar and Dot operators. I'll leave this for next week's post, so I have some information left to cover.