欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top

Assignment 3

Note: operator- should stop when it has subtracted the items indicated or the list is empty, which ever comes first.

Before the submission deadline we will provide tests for this updated data structure in a hw3_check folder released in the homework_resources repository.

Problem 4 (Stacks, 10%) Use your ULListStr from Problem 3 to create a Stack data structure for variables of type std::string . Download and use the provided stackstring.h as is (do NOT change it). Notice the stack has a ULListStr as a data member. This is called composition, where we compose/build one class from another, already available class. Essentially the member functions of the

StackString class that you write should really just be wrappers around calls to the underlying linked list.

You should think carefully about efficiency. All operations (other than possibly the destructor) should run in O(1). You will lose significant points if your Stack data structure does not meet the runtime requirements. You are welcome to change your ULListStr class implementation if you find any bugs or runtime violations!

Your submission should contain stackstring.h and stackstring.cpp . Although there is no test file required for this problem, we recommend you write your own unit- tests.

Problem 5 (String Manipulation Parser and Evaluator, 40%)

For this problem, create a new .cpp file named:

stringparser.cpp .

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. The > operator indicates you should delete the first character of 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:

  1. Any string of 1 or more letters a-z (lower-case only) is a string expression.

  2. If Y1, Y2, ..., Yk are string expressions then the following are string expressions:


>Y1 (Y1) (Y1-Y2)


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.

Valid Examples:

(<<dagobah -(>>yoda+go )) // evaluates to `b`

<> <<<((eve + boo+buzz) - ( >< <nemo)) // evaluates to

<>((<<mario + >>zelda)- ><samus) // evaluates to `arld`

Invalid Examples for which you should output Malformed :

((<mccoy+sulu) // missing parenthesis (leonardo-foot+splinter) // mixing operators (+pikachu+charizard) // extra +

(clARk + bruCE) // the strings use capital letters

If you aren't sure whether an expression is valid or MALFORMED , try to repeatedly (recursively) apply the listed rules to find substitutions that can be made to reduce the whole expression down to a single string expression. So recall the rules:

Thus, given an expression like ( (abc)+(def) ) let's see if it is valid. Start by finding rules/substitutions that can be applied:

( (abc)+(def) )

=> ( (Y1) + (Y2) ) // where "abc" = Y1 and "def" = Y2 by

=> ( Y3 + Y4 ) // where Y3 = (Y1) and Y4 = (Y2) usin

=> Y5 // using the (Y1+Y2+Y3+...+Yk) rule

=> VALID since it reduces to a single string expression

Now take:


=> (Y1) + (Y2) // where abc = Y1 and def = Y2 by ite

=> Y3 + Y4 // where Y3 = (Y1) and Y4 = (Y2) by

=> No rule matches this (since the + operator needs pare


Your program should take two command-line arguments, 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.

We make the following promise:

  1. 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.

  2. Each expression will be at most 10000 characters long.

  3. Blank lines (consisting of just white space, or nothing at all) are possible; for those, the correct output is also a blank line.

  4. You will never produce the empty string. That is, the operations < and > will never be applied on a 1- character string, and formula such as () won't be used.

  5. Apart from this, we make no further promises: the string could contain arbitrary characters, arbitrary white space, etc.

  6. If you cannot open the input file you should simply output Error to cout and exit the program.

Helpful Library Functions

istream& istream::get(char& c) : Though the return type is an istream& you can treat it like a bool and write things such as

while(myinputfile.get(c)) { /* code */ } int isspace(int c) via #include <cctype> :

Though the argument is an int you should pass a

char , and though the return value is an int it sould be interpreted as a bool (i.e it will return 0 = false and non-zero = true).

int islower(int c) via #include <cctype> : Though the argument is an int you should pass a char , and though the return value is an int it sould be interpreted as a bool (i.e it will return 0 = false and non-zero=true).

size_t string::find(const string& target) const : Note that if the target is not found in the

string, a constant string::npos is returned which is

some unsigned integral value that is reserved to mean not found. It is likely the maximum size_t value possible but should not be assumed as such. Instead just use string::npos anywhere you like such as if(mystr.find("abc") != string::npos) {

/* code */ }

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 entire expression string, assuming that everything was correctly formatted (otherwise, report an error), your stack should contain exactly one string, which you can output.

Another hint is to break your problem into smaller tasks such as evaluating a group of parenthesis when you get a closed paren, or applying the < and > after a string is found, and consider what other functions would allow you to decompose your code into smaller chunks (e.g. a function to handle the + operator or the - operator).

You are intended to use your StackString 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 StackString class (thereby helping you identify where any bugs may be). You MUST eventually get your code working with StackString and if you do not, you will lose points (see note below) for this problem.

Beyond the StackString class, you do NOT have to write any other classes and can instead decompose your task into global level functions (similar to HW1 teams problem). If you decide to write any additional helper classes you can put their declaration and definition into the single stringparser.cpp file.

You must write a Makefile which can build an executable named stringparser by executing the command make stringparser . You should break your Makefile into targets to compile/produce ulliststr.o and stackstring.o on which your final target, stringparser can depend along with the actual source code stringparser.cpp . Refer to your Makefile lab.




添加客服微信: abby12468