It is almost the end of the term,
with the last assignment finished, and the second midterm approaching. This
week I’ll be talking about assignment 2, discussing the choices I made and why.
I have been so focused on the
topic of tree structures these few weeks that I haven’t the time to really talk
about the assignment. So I’ll start from part one, overall my design is very
similar to the instructor’s version but with some differences. First of all, I
did not have a class for leaf nodes, I was leaning toward this idea toward the
end of my design but decided against it as I would just be using my RegexTree
with an empty list as children to denote this anyway, I also clearly stated
that in my precondition which I felt was enough. Another thing I found
interesting in the instructor’s version of design is the inclusion of unary and
binary trees as separate classes, this thought actually hit me during the designing
process, but after actually coding it, I just see a large part of the code not
being used. This can be seen especially from the unary tree, where the only
thing it is affecting is star tree, so I might as well initialize star tree
from regex tree. The __repr__ functions are also completely useless as it is
never called because you have specialized version of these unary and binary
trees. I had a similar case for binary tree as I was able to initialize both
dot tree and bar tree with RegexTree as the parent class without the need for
an intermediate class. Overall I just felt like my way was more efficient and
avoided duplicate code.
Part two of the assignment was
very tricky at the beginning; it took forever to draw the tree out in the
attempt to derive an algorithm for is_regex. I had the base case and star
symbol case already in mind, the only thing left was the dot and bar cases,
where I had to find the split point; after about 4 hours of looking for
patterns, I found out that if the regular expression begins with ‘(‘ and ends
with ‘)’, then after removing these parenthesis, the splitting point would have
balanced parenthesis on both sides, what I meant by this is that the left side
should have equal amount of left and right parenthesis, same goes for the right
side, so I just used the count method in string to find the splitting point,
and the rest was easy. After finishing is_regex, permutation and building the
tree was a breeze, after all, they are all using the same idea. The last part
of the assignment is regex_match, which I felt was the most difficult part,
especially the dot and star cases, where the string can be broken down into
many different cases and you have to check each one of the cases to find a
correct one, if not, return False. What I find really tricky at this part is
actually defining the right base case, because once you go into recursion, you
could have ambiguous cases where the string can be split into a couple
different ways and only one is correct. I kept on getting the wrong results
until I see that the base case is not that length of string is one, but rather
the whole string matches the tree. What regex_match really did for me is allow
me to think of many obscure test cases, where each time I think of something
completely out of the box, more likely than not I will find a small error in my
code, and I was able to make change to it. This not only helped me but also my
friends as they said my test cases helped them find errors in their code as
well.
On a last note, it seems that
every time I am confident about tree structure, a new one is introduced, just
like this week’s lab. Each lab gave us a tree structure but introduced in such
a different manner that it really requires a lot of thinking for every single
one of them, this makes this topic a very difficult thing to master, and one
that I will be focusing on the most in response to the upcoming midterm.
No comments:
Post a Comment