Assignment 2 was finished this week, an exercise in trees and a use for them. Though I coded my assignment the way that Prof. Heap suggested it to be coded (specifically with star node and dot node splitting up the string at all possible values and comparing until they get a match), I found an alternative way that may be more efficient (though I have yet to solve for two cases). This is how it goes (this occurs within a helper function that takes in a Node and a str to match, returning a tuple of bool and str):
1. If the Node is a RegexTreeNode, compare its value (either 1, 0 or e) with the first character of the string. Return True if there is a match, or False otherwise, along with the matching string with the first character removed.
2. If the Node is a RegexDotNode, call upon the helper function recursively for left and right sides, giving it the full string for the left side, then giving the left side modified string for the right side. Returns True and modified string if both sides return True, false and modified string otherwise.
3. If the Node is a RegexBarNode, do the same thing as RegexDotNode except it gives the full string for both sides, and returns True (and the respective modified string), if either side returns True.
4. If the Node is a RegexStarNode, keep on calling the function recursively until whatever is within the RegexStarNode returns False. Then return modified string and True (there is no condition that will cause a RegexStarNode to return False).
For example, when given the Regex '(1.(1|0)).0' and the string 110, the code would execute like this:
The Node is a RegexDotNode, call function recursively for left side. Function given: (1.(1|0) and string 110.
The Node is a RegexDotNode, call function recursively for left side. Function given: 1 and string 110
The Node is a RegexTreeNode. Match value of Node to first character of string: 1 matches 1. Removes first element and returns it, as well as True. Returns: (True, 10)
Calls function recursively for right side of RegexDotNode. Function given: (1|0) and string 10
The Node is a RegexBarNode. Call function recursively for left side. Function given: 1 and string 10
The Node is a RegexTreeNode. Match value of Node to first character of string: 1 matches 1. Removes first element and returns it, as well as True. Returns: (True, 0)
Calls function recursively for right side of RegexBarNode. Function given: 0 and string 10
The Node is a RegexTreeNode. Match value of Node to first character of string: 0 does not match 1. Removes first element and returns it, as well as False. Returns: (False, 0)
Since the left side is True and the right side is False, the RegexBarNode returns True and the value of the string that made it True. Returns: (True, 0)
Since both sides of the RegexDotNode are True, the RegexDotNode returns True and the value of the string as it is returned from the right side. Returns: (True, 0)
Calls function recursively for right side of RegexDotNode. Function given: 0 and string 0
The Node is a RegexTreeNode. Match value of Node to first character of string: 0 matches 0. Removes first element and returns it, as well as True. Returns: (True, '')
Since both sides of RegexDotNode are True, the RegexDotNode returns True and the value of the string as it is returned from the right side. Returns: (True, '')
This operation is more efficient than looking at all possible split points for RegexDotNode and StarNode, especially for longer strings, but has two cases in which it fails (though a solution is quite possible, I did not think of one for the assignment due date). The first case is one in which both sides of the RegexBarNode return True, but only one would work (like if it was (1|(1.0).1 and the string was 101), there was no way of calculating easily which side of the RegexBarNode to return. The second case is when the RegexStarNode satisfies the same conditions as the right side of the RegexDotNode (for example, (1|0)*.1 would fail for all strings ending with 1 with the current implementation, as the RegexStarNode code would remove the entire string and not leave a 1 to satisfy the RegexDotNode). These problems I believe I can solve given time however.
In terms of the lectures, sorting algorithms and time complexity was the subject of this week. It was very interesting learning about the different types of "big-oh" complexities, and how they vary throughout the different sorting algorithms, as well as how efficient the python sorting algorithm is and how it's programmed that way. As the exam is next week, I do not have much time to extensively make an entry about the lab this week, but it was a very interesting exploration into converting a tree into a list, we converted strings (and by extension lists) into trees for previous exercises and assignment 2, this is actually the first time we convert a tree back into a list, specifically a linked l
No comments:
Post a Comment