代写一个字符串表达式解析器引擎，并计算表达式的值。
Requirement
Your task is to write a program that will read expressions consisting of
strings and operations from a file, and evaluate and show the output of the
given expression.
String expressions consist of strings, the operators + (concatenate), - (remove), < (remove end), and > (remove start), along with
parentheses to specify a desired order of operations. The < operator
indicates you should delete the last character of the string, unless the
string consists of only a single character, in which case you should not
change the string. The > operator indicates you should delete the first
character of the string, unless the string consists of only a single
character, in which case you should not change the string. The + operator
indicates you should append the second string to the end of the first string.
The - operator indicates that you should remove the first instance of the
second string from the first string (the first string is returned unmodified
if there is no match).
String expressions are defined formally as follows:
- Any string of 1 or more letters a-z (lower-case only) is a string expression.
- If Y1, Y2, …, Yk are string expressions (for
k > 1) then the following are string expressions:
*<Y1
*>Y1
*(Y1-Y2)
*(Y1+Y2+Y3+...+Yk)
Notice that our format rules out the expression ab+bc, since it is missing the
parentheses. It also rules out (ab+bc-b) which would have to instead be
written ((ab+bc)-b), so you never have to worry about precedence. This should
make your parsing task significantly easier. Whitespace may occur in arbitrary
places in string expressions, but never in the middle of a string of letters.
Each expression will be on a single line.
Examples (the first four are valid, the other four are not):
(<<dagobah -(>>yoda+go )) // evaluates to b
<> <<<((eve + boo+buzz) - >< <nemo) // evaluates to eboo
<>((<<mario + >>zelda)- ><samus) // evaluates to arld
><<de // evaluates to d
((<mccoy+sulu) // missing parenthesis
(leonardo-foot+splinter) // mixing operators
(+pikachu+charizard) // extra +
(clARk + bruCE) // the strings use capital letters
Your program should take two parameters, the first being the input filename in
which the formulas are stored, and the second being the output filename. For
each expression, your program should print to the output file, one per line,
one of the options:
- Malformed if the expression was malformed (did not meet our definition of a string expression) and then continue to the next expression.
- A string equal to the evaluation of the expression, if the expression was well-formed.
Some things to note
- Each expression will be on a single line by itself so that you can use getline() and then parse the whole line of text that is returned to you.
- Blank lines are possible. As a 0-length string is not a proper string expression, you should output Malformed if you encounter one.
While this may be contrary to your expectation of us, you must not use
recursion to solve this problem. Instead keep a stack on which you push pieces
of formula. Push open parenthesis ‘(‘, strings, and operators onto the stack.
When you encounter a closing parenthesis ‘)’, pop things from the stack and
evaluate them until you pop the open parenthesis ‘(‘. Now — assuming
everything was correctly formatted — compute the value of the expression in
parentheses, and push it onto the stack as a string. When you reach the end of
the string, assuming that everything was correctly formatted (otherwise,
report an error), your stack should contain exactly one string, which you can
output.
You are intended to use your StackStr class from Problem 4 for the above
purpose. However, you are encouraged to use the STL Stack as placeholder code
to test your program, before replacing it with your StackStr class (thereby
helping you identify where any bugs may be). If you do not use your StackStr
class in your submitted code, you will receive a 5 point reduction on this
problem. You may not use any other STL data containers. Warning: This problem
is significantly more difficult than the previous problems. If you are having
issues with the earlier problems, you are strongly encouraged to fix those
before tackling this problem.
Write your code in stringparser.cpp and provide a rule in your Makefile to
compile the program. Running make stringparsershould produce an executable
called stringparser in your hw3 directory.
