Regular expressions

First of, I belong to the side which pronounces it "Ree-jex", it flows off the tongue better, sue me.
Anyways, A2 was due a few days ago. It brought along with it: staring into space for a long time, many goofy hand gestures and a lot of pacing up and down. Overall a fun assignment, 8.42/10.

For this assignment we needed to be able to take in a regular expression, validate that it is syntactically correct, represent it in a tree and be able to check a string to see if it fulfils the rules stated by the regex.

To do this, we needed to create some functions, namely:
is_regex(s)
regex_match(r,s)
build_regex_tree(r)

is_regex(s)
When I started out on is_regex, I originally had a hybrid iterative and recursive approach in mind. It was efficient but was quite long (around 80~90 lines). It involved locating nested brackets and processing each nested regex (deepest to shallowest). When a valid nested regex was found, it was fully replaced by a placeholder which made the rest of the regex easier to validate. For example:
- (1.(2|0)*)
-> (1.e*)
-> (1.e)
-> e
VALID.
Unhappy with the code length, I rewrote everything from the ground up and ended up with a fully recursive solution which was around 20 lines long and didn't use any helpers. It worked by splitting a regex around binary operators (. , |) and checking whether either side was a valid regex. If it both sides were valid, then the entire regex was valid.

build_regex_tree(r)
This was a relatively easy function to build. I needed to read in a regex and output it's tree representation.
Again, I built a iterative-recursive solution, and unline is_regex, I stuck with it. This one involved finding the shallowest nested regex and then just rooting the tree at that regex and delving deeper (recursively). The iterative part came in finding the shallowest nested regex, which was done by looping over the regex and locating all the brackets.
The fully recursive approach which I thought could also work, would be to use the same approach of splitting binary operators as is_regex. I would locate a binary operator and run is_regex on the left and right side. Only the shallowest binary operator would pass the is_regex test. The rest would fail because of bracket mismatches. Then I could build the tree starting at that shallowest operator, and use recursion to go deeper into the regex. I decided against this because I felt that even though the code length would be comparatively short, the runtime would be a lot longer than my original approach.

regex_match(r, s)

I had mixed feelings about the difficulty of this function. It was relatively easy for binary and leaf trees. The issue arose when I needed to check for the star trees. It was seemed relatively straightforward, but there was slight ambiguity in the rules of what strings would match a star tree. This edge case in particular:
(1*.2*)*
What strings would match that? The real question being, how many times is the inner bracket evaluated?
-If it is evaluated only once, then:
For example if the inner bracket produced a string match of "1122". Would this regex only match a string of any number of 1122's concatenated? eg: 112211221122

-The inner bracket is evaluated indefinitely: (This is the approach I took)
Basically evaluate the inner bracket for every character of s. Meaning that, the above regex would match every single string that contains any number of 1's and 2's. eg: 112, 21, 21122, ' ', 1212
Let's take '21122' to show how this would evaluate true:
This can be broken up into 2 + 1 + 1 + 2 + 2
And each of those characters would match the inner bracket: (1*.2*). Therefore making the whose string true.

All in all, this was an interesting assignment with a reasonable difficulty. It was more enjoyable to do than the assignment 1.