CS 112 B1 - Spring 2003: Homework 2

Due Thursday, February 13 at 11:59 P.M.

Reading: Kruse and Ryba Chapters 3 (except 3.5) and 5.

Please keep in mind the policy on collaboration, as described on the syllabus.

Your code will be graded for style as well as correctness and should conform to the following style guidelines.

Don't forget to sign up for our email list by typing csmail -a cs112b1 on csa. Instructions on forwarding your csa mail elsewhere are here.

PROBLEM 1:

(10 points)

Here is a linked-list-based stack, without the Pop() method. Add it to stack2.cpp and test it using your calculator from the previous homework (or the solutions version). Note that you will need not modify anything in calculator.cpp, assuming, of course, it was correct (with one exception: if you called IsFull and never looked at the value return by Push, now IsFull is useless, and you actually need to look at the return value of Push).

(you may download them using a browser; a faster way to do this on csa is to type
cp /cs/www/html/faculty/reyzin/teaching/s03cs112b/hw2/{stack2.h,stack2.cpp,itemtype.h} .
at the Unix prompt to get these files into your current directory.

PROBLEM 2:

(20 points)

Here is an ordered list, without the bool Remove(ItemType item) method, which should return false if the item is not the list, and otherwise remove the item from the list and returns true. Add it to orderedlist.cpp and test it.

PROBLEM 3:

(40 points)

Here is the header for the class Polynomial.

Implement it in a new file polynomial.cpp. It may help you implement EqualToSum, EqualToDiff, and EqualToProd if you remember that a method of a class is allowed to access private members of other instances of the same class. Be sure to handle memory management properly, not leaving any dangling pointers and lost memory. Also be sure to follow the comments in polynomial.h about how the linked list arranged, and print the polynomials as shown below. Note: For grading, the polynomials must print precisely as in the examples below. We will take points off if they do not.

PROBLEM 4:

(30 points)

Create an RPN calculator for polynomials. The input syntax is the same as in the previous homework, with the following exceptions: a / is not allowed, and a ? should be followed by a float coefficient, a space, and an integer degree. This inputs a monomial. To input a polynomial, input its monomials and add them.

Here is a sample input and output:
? 1.5 3 ? 4.3 2 ? 2 0 ++ = ? 4 3 ? 1 1 + = * = ? 2 1 ? -7 0 + = - = ? 0 0 = * = q
1.5x^3 + 4.3x^2 + 2
4x^3 + x
6x^6 + 17.2x^5 + 1.5x^4 + 12.3x^3 + 2x
2x - 7
6x^6 + 17.2x^5 + 1.5x^4 + 12.3x^3 + 7
0
0
 It may help to use the RPN calculator from the previous homework as a starting point (you may take the one from the solution if you wish), and either of the stack implementations. The stack now should hold pointers to polynomials. You will need to modify itemtype.h but not the stack implementation itself. The new itemptype.h will read as follows:

class Polynomial;
typedef Polynomial * ItemType;

 Because your stack now holds pointer, you'll have to handle creation and deallocation of polynomials via new and delete carefully. Again, be sure to deallocate memory before losing track of it.

Put your new calculator into polycalc.cpp.

To submit hw2:

  1. You must be logged onto csa, and all files must be on the csa computer.
  2. Test that your program works by compiling it with g++ -Wall.
  3. Create a subdirectory called hw2, using the mkdir command.
  4. Copy all files to be submitted and no others into this subdirectory. The following files (and ONLY these files) should be in subdirectory hw2:
  5. To submit the assignment, cd to the directory containing the hw2 subdirectory and type:
    gsubmit cs112b1 -cp hw2
    This should submit the entire hw2 subdirectory.

Important: Please follow all instructions about file names and how to submit assignment exactly, or there is a very real chance that your assignment will not be accepted! For example, a directory named "Hw2" will probably not be seen by the grader.