Data Structures and Algorithms I

Program 2 

This program will manipulate polynomials. Recall that a polynomial is a function of the form a_nxⁿ + a_n-1x^n-1 + ... + a₀x⁰. Storing a polynomial requires storing its coefficients and degree. In some cases, polynomials have a lot of zero terms (such as 23x²⁰⁷ + 3). It would be wasteful to store all of the 0 coefficients. Polynomials should be displayed with terms ordered by decreasing powers (degree).

Design and implement two classes: Term and Polynomial. A Term must represent a coefficient and the degree of the term. A Polynomial is a list of Term objects, each with a different degree, and maintained in decreasing order of degree. You must use dynamic storage for the list.

Terms should utilize public methods to initialize, access, and update internal data. Coefficients are non-zero integers (with one exception), exponents are non-negative integers. One special Term represents the constant 0 (exponent must be 0 if the coefficient is 0). Enforce these limits. 

Provide methods to input into a Term, and output from a Term. Output of a Term should display the coefficient, the letter x, and the exponent in this format: +23x^12. Note that a leading sign must be printed even if the coefficient is positive. You should also 

• suppress the output of a coefficient of +/-1; that is, -x^2 or +x^3 should be displayed rather than -1x^2 or +1x^3. 

• suppress the output of an exponent of 1 or 0; that is, 2x^1 is displayed as +2x and 3x^0 is displayed as +3

Input of a Term should skip leading whitespace, extract an optional sign (+ is assumed if missing), extract an integer coefficient, extract and discard the letter x (or any other alpha character (a-z or A-Z)). If the character is not an alpha, assume this is a constant term and stop extracting. Otherwise check for the character ^ and, if present extract it and continue on to extract the exponent. If the ^ is not present, assume an exponent of 1. Note that the coefficient might be missing in which case you must substitute a 1 (-x^2, +x^3, or even x^4). The coefficient might be zero (as in 0x^3) resulting in the special zero Term. If the coefficient or exponent are illegal values for a Term, the stream should be put into an error state (the fail flag should be set). If end-of-file error occurs, you should return with the stream in that state.

The Polynomial class needs a conversion constructor that converts a Term to a Polynomial. It also must contain input and output methods and methods to compute the sum, difference, and product of two Polynomials. These methods should be called using this syntax:

p.difference(q, r); //p is set to the result of q-r

Output of a Polynomial is simply Output of the Terms of the Polynomial. Input of a Polynomial uses the input method for Terms. Note that Polynomials being input may not be arranged in the correct Term order - your program must account for this. Polynomial input continues until an exclamation character (!) is encountered or the stream reports an error. Your input routine must extract the exclamation and any whitespace preceding it. It is possible that no Terms are extracted before the exclamation is encountered. This would result in the zero Polynomial.

You must write a test program that uses the above classes to read Polynomials from a file and perform the indicated operations. Each problem in the file consists of a +, -, or * character representing an operation followed by two Polynomials (each terminated by '!'). An ! (in the place of an operation) marks the end of the file. You must output the problem and answer on the screen. A test file is included, but you should add to it as I will be testing your program on my own file. Your program must ask the user to enter the test file name.

Test File: poly.txt

Output for this sample file should look like this (cases 2 and 3 corrected):

Output for the file poly.txt
+0 + +0 = +0
-3x^2+2x-2 + -3x^2+6x = -6x^2+8x-2
-3x^2+2x-2 - -3x^2+6x = -4x-2
+x^7+5x * +x^4-x = x^11-x^8+5x^5-5x^2
+6x-3 * -x^2+2 = -6x^3+3x^2+12x-6
+2 + -2 = +0 

Submit your completed project to margush@uakron.edu as a zipped attachment to an email with subject line DSA1 Program 2 - Fred Jones (substitute your name). The zip file must be named with your last name and the digit 2 attached to the end (Fred Jones would submit a file named Jones2.zip). The zip file must unzip to create a folder with the same name (Jones2) and the folder must contain all of the project files needed to open the workspace and build the project. Please erase the Debug folder before zipping.