CMPSC 122 Homework 2

This assignment introduces the definition of classes, and their use in the implementation and use of a simple iterator.

INTRODUCTION TO ITERATORS

Practicing good information hiding means that a client using a container (such as those we will see later) should have no knowledge of the exact implementation (such as next pointers). Of course, it is good for it to know enough about the container to know that it is appropriate to the application, but isolating the implementation greatly reduces the chances of programming errors.

In the first assignment, an array subscript was passed throughout the program to keep track of the position in the input data. The parsing routines were very much aware that they were using an array subscript, even if they always had some helper routines use it.

An iterator is an abstraction that allows a container just to be viewed as a series of data elements in some order, but the exact details are hidden from the outside. The container simply defines where the iterator will begin and where the iterator will end. The iterator will simply proceed from one item to the next.

An application using this iterator now has no need to know just how the underlying data is represented. It just allows the iterator to visit all the data.

In a later assignment, we will actually be replacing what the iterator will be visiting. it is therefore important that your efforts on this one use the iterator fully, so that they will not have to be rewritten later.

PROBLEM DESCRIPTION

1) Complete the provided iterator, by adapting the code that appeared in tokenize.cpp in the previous assignment.

Also, remove the restriction that all numbers must be one digit. As we move away from the understanding that the input is simply an array of characters, we must also move away from the assumption that all tokens are single characters.

For now, it will be sufficient to assume that the only items that consist of multiple characters are numbers, so the only function needing any work would be advance.

2) Modify evaluate.cpp so that it uses the given iterator to traverse the data instead of using an array and a subscript.

It will first create a TokenList object from the character string, and then create a ListIterator to traverse that container. The iterator will be passed to all of the parsing functions, who will advance it as necessary.

The only changes that should be required are those that migrate from the array to the iterator; there should not be any need to reorganize the logic of the program (unless it was flawed in the first assignment).

COMPONENT FILES

Header files (.h) will now begin to declare classes and their methods, and source files (.cpp) will implement many of those methods.

There may be some methods within the header file if they are very brief. These are primarily simple accessor methods (such as betting the integer value of a Token), but I sometimes will expand them to functions that are very very short.

A function that is implemented within a class definition in C++ becomes an in-line function, meaning that when the compiler encounters a function call, it simply expands the function code in place. This does yield code duplication in the executable file (so should not be done for large functions) -- but it avoids the need to call and return, which would dominate the execution time of a simple accessor method.

• tokenlist.h Declares token list s DO NOT CHANGE
• tokenlist.cpp Implements token list Complete methods TokenList::begin and ListIterator::advance One additional method ListIterator::retreat is Extra Credit Implement the Tokenlist constructor and methods
• evaluate.h Declares evaluate function DO NOT CHANGE
• evaluate.cpp Evaluates an arithmetic expression The algorithm will be essentially unchanged, but now it will obtain tokens from an iterator instead of using an array subscript. This will still consist of mutually recursive functions that traverse the data using the iterator, after it has been defined. Complete and submit
• driver.cpp Some code to test the expression evaluation Feel free to edit as desired, but do not submit. A very different version of this file will be used for grading.

The files to be submitted for this assignment are tokenlist.cpp and evaluate.cpp.

A makefile is also provided so that the make utility can be used under Linux to compile this program.

EXTRA CREDIT OPTION

Implement the ListIterator::retreat method, which will find its way back to the previous token.

It must account for the fact that numbers may have multiple digits, and that there may still be any number of spaces between tokens.