assignment 2

Assignment 2



 regular expression:
Regular expressions are text matching patterns described with a formal syntax. The patterns are interpreted as a set of instructions, which are then executed with a string as input to produce a matching subset or modified version of the original. The term “regular expressions” is frequently shortened to as “regex” or “regexp” in conversation. Expressions can include literal text matching, repetition, pattern-composition, branching, and other sophisticated rules. A large number of parsing problems are easier to solve with a regular expression than by creating a special-purpose lexer and parser.
Regular expressions are typically used in applications that involve a lot of text processing. For example, they are commonly used as search patterns in text editing programs used by developers, including vi, emacs, and modern IDEs. They are also an integral part of Unix command line utilities such as sed, grep, and awk. Many programming languages include support for regular expressions in the language syntax (Perl, Ruby, Awk, and Tcl). Other languages, such as C, C++, and Python supports regular expressions through extension libraries.
There are multiple open source implementations of regular expressions, each sharing a common core syntax but with different extensions or modifications to their advanced features. The syntax used in Python’s re module is based on the syntax used for regular expressions in Perl, with a few Python-specific enhancements.


it was regular expressions, or regex, for short. Regular expressions are a series of characters that form patterns, or a sort of template, that can be interpreted by a computer to preform a command. In regular expressions, specific characters have different meaning, and the string follows a pattern that can be converted to preform tasks. Assignment 2 focused on the basic concept of parsing through a custom regular expression and converting that string into a binary tree of nodes based on the operators used in the regex.

I implemented a iterative solution for parsing the string. I first dealt with the base cases, then the StarNode, then after checking the ending parentheses (indicating the end of an expression), added in the BarNode and DotNode. All it really took was going through every character and one stack (rex in this case).
The solution for matching was a bit more complicated so I'm not going to post my full solution, but essentially it required checking the .symbol value of the RegexTree and matching it up with the base cases. I was fine for most of the test expressions, but I was not able to fully perfect how the code dealt with StarNode, so my solution did have some problems with some test cases.