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.