UMBC CMSC201, Computer Science I, Fall '98

Project 5: The Polynomial ADT

Due date: Friday, December 11, 1998

This project will give you practice implementing an abstract data type, a polynomial in one variable, using sorted linked lists. You will get more practice with pointers, structs, file-handling, command-line arguments and, of course, design and separate compilation.

Description of the Program

You must use command-line arguments for this project where the appropriate command line argument to run your project will be:

a.out polynomials.dat operations.dat

A polynomial in one variable is composed of terms, where each term has both a coefficient and an exponent. An example of a polynomial is:

x³ + 3x² - 5x + 6

where, the standard form of expression is that the terms are in descending order by the exponent of x. It is also standard to eliminate the terms that have a coefficient of 0. A detailed explanation of the terms is as follows:

The first term, x³, has an implied coefficient of 1 and the exponent is 3.
The second term, 3x², has a coefficient of 3 and the exponent is 2.
NOTE: The operator between the first and second term gives the sign of the coefficient for the second term. In this case the operator is +, indicating a coefficient of positive 3.
The third term, 5x, has a coefficient of -5 since the operator preceding this term is -. The exponent is an implied 1.
The last term of the example polynomial is 6. This is the coefficient and it is positive due to the + operator preceding it. The exponent of x is 0. By definition, anything taken to the 0th power is 1. So the coefficient is 6 and it is to be multiplied by 1, resulting in 6.

Notice how many times I used the word "implied" in the discussion about polynomials above. People tend to have little trouble interpreting implied things, but computers don't do as well. For that reason, we will use a different format for expressing our polynomials. Nothing will be implied about any term. Of course, it won't look as nice. Here's how I will express this same polynomial in the data file:

1 3 3 2 -5 1 6 0 You are to use a similar format to store each of the terms in your linked list of terms known as a polynomial.
Since a user of the system will expect to see a polynomial in a form that he is familiar with, you will print out your polynomials in a form closer to the algebraic form. The polynomial shown above should be printed as: x^3 + 3x^2 - 5x + 6 where coefficients of 1 aren't displayed, exponents of 1 aren't displayed, and when x has an exponent of 0 (as in the last term of the example), the x isn't displayed, just its coefficient.

The two data files are shown below. The polynomials.dat file, begins by giving the number of polynomials present in the file. Each of the polynomials is on a seperate line. The terms of the polynomial are made up of coefficient and exponent pairs, as explained previously. The terms in the polynomial may, or may not, be in descending sorted order by exponent.

7 0: 1 2 -2 1 -3 0 1: 1 1 1 0 2: 2 3 16 1 6 2 8 0 3: 1 1 2 0 4: 1 1 -2 0 5: 1 2 -4 0 6: 3 4 -5 3 5 0 1 2 1 1 2 3 -4 1 2 0

The operations.dat file gives a list of operations to be performed on a specified polynomial or polynomial pair.

print poly[3] combineTerms poly[6] add poly[0] + poly[4] sub poly[0] - poly[1] scalarMult 3 x poly[0] scalarDiv poly[2] / 2 mult poly[3] x poly[4] isFactor poly[0] , poly[1] isFactor poly[0] , poly[4]

Design limitations and details