2023年11月25日

java代写 | Regular Expressions Simplifier

本次java代写是正则表达式简化

Regular Expressions Simplifier
Benjamin Sanders, M.S. October 1, 2019
1 Assignment Description
In recent lectures, we have been learning about symbols, regular expressions and finite automata. Today, you
will write code to simplify regular expressions.
• You will write this in Java, C++ or Python.
• This program will accept a single line of user input and will ignore anything more. It will use spaces to
parse between tokens.
• To parse this user input, we will agree on some common symbols and their ‘keyboard equivalents.’ Therefore, this list is what we expect to be typed in, and displayed as output as well.
• Your program should adopt the following structure:
1. Prompt the user for a single expression.
2. Parse the input string into tokens. Hint: use a “list” style data structure to store the tokens in
individual variables.
3. Simplify the expression, according to the rules given in Lecture 9. You are only required to implement
the rules given as 9.1 to 9.13, but the additional reasoning through the lecture may be helpful in your
application of these rules.
4. Output the simplified expression.
2 Common Symbols and Keyboard Equivalents
• ⊆ C
• ∪ v
• ∩ ˆ
• a
n a[SUP n]
• ai a[SUB i]
• a
n
i a[SUP n SUB i]
•
def = DEF=
• iff IFF
• |x| |x|
• | ST
• + +
• ∗ *
• (, ) (, )
• × CROSS
•
ˆδ DELTAHAT
• ∈ IN
• ∈/ NOTIN
• ≡ EQUIV
• ≤ <
• ≥ >
• ⇒ =>
• ⇐⇒ <=>
•
a
−→ a->
• ∅ MTST
• α ALPHA
• β BETA
• γ GAMMA
• δ DELTA
•  EPSILON
• A A
• B B
• Γ BIGGAMMA
• ∆ BIGDELTA
• E E
• Σ SIGMA
• … …
1
3 Example 9.2
Consider the following expression.
• (1 + 01 + 001) ∗ ( + 0 + 00)
This should be input to your program as the following:
• ( 1 + 01 + 001 ) * ( EPSILON + 0 + 00 )
Notice the use of spacing to separate all tokens. Notice the use of only symbols we can strictly type from the
keyboard. Notice the reasoning given to simplify this expression, in Example 9.2.
Finally, output to the user should be the following:
• ( ( EPSILON + 0 ) ( EPSILON + 0 ) 1 ) * ( EPSILON + 0 ) ( EPSILON + 0 )
This is equivalent to (( + 0)( + 0)1) ∗ ( + 0)( + 0) as detailed in Example 9.2.
4 Example 7.1
Consider the following expression.
• x1 + x2 + … + xm
This should be input to your program as the following:
• x[SUB 1] + x[SUB 2] + … + x[SUB m]
Finally, output to the user should be the following:
• SIGMA[SUP m SUB i=1] x[SUB i]
This is equivalent to
• Σ
m
i=1xi
5 Notes
I realize that this style of assignment contains a subjective component: what exactly is the criterion for calling one expression simplified and another not? Therefore, I do not expect valid outputs from two individual
students’ efforts to necessarily match.
I expect to see your best individual effort to implement rules 9.1 to 9.13 from Lecture 9. You should consider
creating test examples for each rule. I will be testing your program against examples based on these rules, and
will evaluate the validity of the output of your program as a human interpreting the results.
2