Blog Entry #7: Assignment 2 Part 2

Blog Entry #7: Assignment 2 Part 2

         In last week's blog I divided the assignment 2 into two sections, representation the tree and the matching with a regular expression. This week I will continue discussing the solution to assignment two.

Case # 1: when there's only one character in the tree (e.g. '0', '1', 'e'), in this case, check if the string given is the same as the symbol of the tree, and if the symbol is 'e', allow the string to be empty.
           
               return s == '' if (r.symbol == 'e') else s == r.symbol

Case # 2: when the symbol is '|', either the left child has to be the same as the given string, or the right child has to be the same as the given string, or both if the two children are identical.
 
               return match(r.children[0], s) or match(r.children[1], s)

Case # 3: when the symbol is '.',  the given string only matches the tree if the given string can be divided into two parts, and part one matches the left child, part two matches the second. One problem that I had while coding this case was that when I applied recursive strategy to the coding,  mostly likely the left child and right child will be another complex tree with its own children. Therefore, I cannot just simply divide the string in half which also implies the length of the string is not exactly 2. It could be less than two if the child is 'e' (empty), or more than two is the symbol of the children is '.'. My solution is to divide the string in all possible ways and tests each single case using the recursive strategy.

               for i in range(len(s) + 1):
                      if match(r.children[0], s[:i])  and match(r.children[1], s[i:]):                      
                             return True
              return False


Case # 4 the starNode : firstly I have to admit that I had some troubles getting this right. I tried several strategies and finally got my code working; however, my solution might not be the most efficient one. As the instruction indicates, the string matches the regex if the string is empty. A complex regex also needs to be taken as consideration. For example, if the expression is '(a|b)', the string can be 'aaaaa' or 'bbbb'; another example would be if the expression is '(a.b)', then the string can be 'ababab'. In the case where a dotNode is combined with a batNode, the result could be even more complicated; Therefore,

                if  s is None:
                       return True
                elif isinstance(r.children[0], DotNode):
                      for i in range(len(s)):
                              if match(r.children[0], s[0: i + 1]):
                                     return  match(r, s[i + 1:])
                      return False
               else:
                      return True if False not in [match(r.children[0], i) for i in s] else False