CMPSC 122 Homework 3

This assignment incorporates a simple linked list into the project, including an iterator to traverse that list. It also includes the implementation and use of a stack.

PROBLEM DESCRIPTION

What people find to be a natural way of writing an arithmetic expression is not so natural to a machine implementation. Even for something as simple as 2 + 2, we recognize that the addition operator applies to the value that follows it. In scanning the expression from left to right, we implicitly remember the plus, until we know what it would be adding.

In a computer program, we certainly have a natural way of remembering a value, those are stored in memory. But remembering an operation (which may involve several machine instructions) is not so natural. With that in mind, some machine designers would prefer to have the operands precede the operation, such as 2 2 +. Once the plus symbol is seen, the values to add have already been encountered.

Consider this expression (simplified from the earlier assignments):

9 - 5 + 6 * ( 2 + 8 / 4 )

Rewriting this with the operators last, and with parentheses included for clarity, this would become

( 9 5 - ) ( 6 ( 2 ( 8 4 / ) + ) * ) -

Now the first addition is clearly postponed until its operands have been determined.

Usually, expressions like this are written without parentheses. Every operator applies to the values that immediately precede it, where those values are either given, or computed by other operators:

9 5 - 6 2 8 4 / + * -

Postfix expressions therefore have no need for parentheses, which simplifies their grammar, as well as the machine implementation. It is actually used by Hewlett Packard calculators, and also by the Java Virtual Machine (a hidden simulation within a Java implementation).

Unfortunately, it is unlikely that most of the population at large will adopt postfix notation for general use, so most programs will still accept the more well-known infix form.

This assignment consists of three major steps:

• Convert the original input string into a list of Tokens.
• Convert the infix expression into a postfix expression. Both expressions will be represented as a linked list of Tokens.
• Evaluate a postfix expression that computes to an integer value. Doing so will make use of another linked list of Tokens (integers only).

Between these last two steps, display the contents of both linked lists.

ALGORITHM HINTS

The first step is simply scans the data. It only needs to distinguish numbers from non-numbers, and add the appropriate element into a linked list. Once that is done, an iterator will be able to visit that list for the next step.

The second step is very similar to the existing assignments. Already the code exists for understanding the expression given the series of tokens. Instead of returning an integer value from each function, add the appropriate token to the postfix expression. The change is simply to produce a new linked list for use in the next step.

The third step above is actually simpler than the second. Each operator in a postfix expression applies to operands that precede it. The algorithm will expect to find the values of these two operands in a TokenList, and then would store the result of a calculation in that same TokenList. It will always be retrieving the most recent operands that have been determined, so one needs to use the TokenList in a way that supports that. All it needs to do is scan a postfix expression (with an iterator) and perform operations as it sees them.

There is an algorithm to implement the second step as a loop, but for this homework, it would be far better not to. For the later assignments, the recursive parsing method would actually be much simpler, so it would save a lot of student programming time to keep the same algorithm here as was used since the first assignment.

COMPONENT FILES

• token.h Declares tokens DO NOT CHANGE
• token.cpp Allows output of tokens to cout DO NOT CHANGE
• tokenlist.h Declares token lists DO NOT CHANGE
• tokenlist.cpp Implements token list Implement the constructor, push+back, push_front and pop_front Additional local functions may be implemented as desired.
• evaluate.h Declares evaluate function Same as before. DO NOT CHANGE
• evaluate.cpp Evaluates a tokenized expression Must now do the three steps listed above. Be sure o display both lists immediately after translation and before evaluation. 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.

EXTRA CREDIT OPTION

Consider the following expression:

4 * ( - ( - 4 - 3 ) )

An 'easy' way to address the negation operator is to imagine it is subtracting from 0, yielding this postfix expression:

4 0 0 4 - 3 - - *

Implement a clean and simple solution to this negation operator that does not require pushing extra zeros onto the stack. Be sure to mention that you have done so in the Message Box when submitting, so the grader will know to test your code.

Since the specifications above require displaying both linked lists, the grader should be able to see how you went about addressing this problem.