Assignment 7, due Thursday April 6 at noon.

You must submit your program electronically via gsubmit on csa.

Under no circumstances will late assignments be accepted.

The code you submit must conform with the programming guidelines.

Program Description

In this assignment you will develop a program that can add, multiply, and subtract polynomials of one variable.

Write and submit five files:

  1.   list.cpp -- member functions for your doubly-linked list ADT
  2.   list.h -- class definition and function prototypes associated with your doubly-linked list ADT
  3.   polynomial.cpp -- member functions for your polynomial ADT
  4.   polynomial.h -- class definition and function prototypes associated with your polynomial ADT
  5.   main.cpp -- the main program

Linked List ADT Class Definition and Implementation

Implement the doubly-linked list ADT using dynamic memory allocation as described in the Main and Savitch text.

Polynomial ADT Class Definition and Implementation

Implement the polynomial ADT using doubly-linked lists.  A polynomial should be stored as a linked list. There is no maximum degree.  Each node in the list should contain a non-zero coefficient and its associated exponent.  For instance, the equation  4x^5 + 2x^1 - x^0 should result in the following linked list of size = 3:

linked list

Implement three overloaded mathematical operators for the polynomial class: +, -, and *.

Main Program

Write a main program that takes one argument on the command line: the input filename.  Here are some example input files:
  1. example1
  2. example2
  3. example3
You can assume that the input file consists of one line, and follows the format

(polynomial) operation (polynomial)

where operation can only be +, -, or  *.  Each polynomial is of a single variable x and can have arbitrary degree.  You can assume that each term in the polynomial consists of a coefficient a times x raised to an exponent: ax^k.   The exponent will always be an integer that is greater than or equal to zero. In this file format, all mathematical operators are separated by whitespace.   Each polynomial is enclosed in parentheses. You can also assume that there is no error in the input file format.

Your program should read the input file, perform the requested mathematical operation, and then print the result to standard output.  For the example files above, the correct format of the printed results would be:

  1. 4.5x^6  + 9x^5 + 6x^3 + 12x^2 -15x^1 - 30x^0
  2. 4.5x^5 - 9.09x^4 + 6x^2 + 8x^1 + 7198x^0
  3.  -14x^4 - 6x^2 + x^1 + 7228.0x^0
Note that the terms in the printed resulting polynomial are shown in decreasing order of exponent.

Extra Credit

In addition to completing the above, extend your program to handle addition, subtraction, multiplication of n polynomials. Your program should work for any positive n. For instance, here is an example input file where n=4: example4. As before, you can assume that each polynomial is enclosed in parentheses. Be sure to observe the precedence of the multiplication operator over addition and subtraction.

Grading Criteria

Refer to the grading criteria file: p7.criteria

Academic Honesty and Collaboration

Cooperation is recommended in understanding various concepts and system features. But the actual solution of the assignments, the programming and debugging must be your individual work, except for what you specifically credit to other sources. (Your grade will be based on your own contribution.) For example, copying without attribution any part of someone else's program is plagiarism, even if you modify it and even if the source is a textbook. The University takes acts of cheating and plagiarism very seriously: first time violators are routinely suspended for a semester.