Initializing a Regex Tree

The Regular Expression Tree

Converting regular expressions (regexes) into trees was the first part of our last assignment. My thought process with starting to solve the problem. I realized that to finish it, I would have to have a method to deal with every part of the regex string. The regexes have 3 operators, '|', '.', and '*' which determine which type of node we would be using, and at the deepest level, the leaves were numbers, either '0', '1', or 'e' (meaning empty). The thing that quickly became apparent was that dealing with these separate operators and leaves was dependent on first dealing with the parentheses that separated the children of a node from their parents. This really stumped me at first. I tried initially to start from the deepest level and work upward from there, but I ran into a lot of problems and had trouble implementing this method. Mainly, I just couldn't figure out how to work backwards in this way. Eventually, it became clear that an easier method was available. The new way was to count up the parentheses while iterating over the string, and when a symbol was encountered after an equal amount of left and right parentheses, the left and right sides of it were then evaluated, excluding the outermost parentheses.