UMBC CMSC201, Computer Science I, Fall '98

Project 5: The Polynomial ADT

Due date: Friday, December 11, 1998

Description of the Program

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:

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.

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

Design limitations and details

• You should read and store all of the polynomials in linked lists before beginning to do any of the operations found in the operations.dat file.
• Implementation requirements:
  • A term is to be a struct (the data portion of a node) containing an integer coefficient and an integer exponent as its members.
  • A polynomial is to be a sorted linked list of nodes where a term is the data portion of the node, and the list is kept in descending sorted order by the exponent member of each term.
  • Operations :
    • PrintPolynomial should print out a polynomial in the format discussed above.
    • CombineLikeTerms should take a polynomial and combine like terms, if necessary, and return the answer. Example: 3x^4 - 5x^3 + 5 + x^2 + x + 2x^3 - 4x + 2 can be simplified by combining like terms i.e. -5x^3 + 2x^3 = -3x^3, x - 4x = -3x
      and 5 + 2 = 7, producing 3x^4 - 3x^3 + x^2 - 3x + 7
    • ExpandPolynomial You may choose to keep the terms of your polynomials in either expanded form or simplified form. If you keep them in simplified form, meaning all 0 terms are not stored, then they will take up less space. This is completely up to you. If you do store your polynomials in reduced form, you will need a function called ExpandPolynomial to put the 0 terms in before doing addition and subtraction. This will make the addition and subtraction functions much easier to write.
    • AddPolynomials adds two polynomials producing the sum.
    • SubPolynomials subtracts the second polynomial from the first and produces the difference.
    • ScalarMultiply multiplies all of the terms of the polynomial by an integer.
    • ScalarDivide divides each of the terms of the polynomial by an integer.
    • MultiplyPolynomials should multiply two polynomials together producing a product.
    • IsFactor should indicate whether one polynomial is a factor of another. If it is, the other factor should be also be printed out. See the example in the sample output.
      A fully working function called IsFactor, whose output is as shown in the sample output, is worth 10 points of EXTRA CREDIT.
      All students must have a function called IsFactor. Those students who do not wish to attempt the extra credit should simply print out the message, "Didn't do factoring" within the function and return 0 (false).
  • Implementation requirements and issues:
    • All of the functions that you are required to write should return polynomial answers (not just print it out within the function), with the exception of PrintPolynomial(), which is a procedure and IsFactor(), which is a predicate function.
    • Scalar divide should only be done if each of the original coefficients can be evenly divided by the integer passed in, otherwise print a message and return the polynomial that was passed in, unchanged.
    • Suggestions for reading from the operations.dat file:
      Read one line at a time using fgets, then use sscanf to get the 2 or 3 important pieces of information from the string you read in.
    • You will be graded on your design and on the efficiency of the program, as well as the correctness of the program, documentation and style.

  ---

  Sample Output

  print poly[3] x + 2 combineTerms poly[6] 3x^4 - 3x^3 + x^2 - 3x + 7 add poly[0] + poly[4] x^2 - x - 5 sub poly[0] - poly[1] x^2 - 3x - 4 scalarMult 3 x poly[0] 3x^2 - 6x - 9 scalarDiv poly[2] / 2 x^3 + 3x^2 + 8x + 4 mult poly[3] x poly[4] x^2 - 4 isFactor poly[0] , poly[1] x + 1 is a factor of x^2 - 2x - 3 (x + 1)(x - 3) = x^2 - 2x - 3 Returned True isFactor poly[0] , poly[4] x - 2 is not a factor of x^2 - 2x - 3 Returned False

  Data files

  There are links to each of the data files in this document above where they are shown.

  The executable and the data files need to be in the same directory in order to work properly.

  Submitting your project

  Submit your projects as usual, using the submit command. You do not need to submit the data files.