CS215 - Introduction to Program Design, Abstraction, and
Problem Solving
Fall, 2002
Programming Assignment #2
Assigned: Thursday, October 24th, 2002
External Documentation Due: in class on Tuesday, November 5th, 2002
Listing and Executions Due: by e-mail by 11:59 pm on Tuesday,
November 12th, 2002
Design, write, and execute a C++ program that manipulates mathematical
polynomials, allowing the user to work with an ongoing, "current"
polynomial by repeatedly choosing actions from the following menu:
- resetting the current polynomial to a new polynomial
- adding the current polynomial to a new polynomial, and making
this sum be the current polynomial
- subtracting a new polynomial from the current polynomial, and making
this difference be the current polynomial
- multiplying the current polynomial with a new polynomial, and
making this product be the current polynomial
- evaluating the current polynomial at a particular value of x
- asking for help and being shown a list of the available operations
- quitting the program
In case you need a refresher, a polynomial is a sequence of terms added
together, each term being of the form "cx^e", where c is the term's
coefficient, x is the variable of the entire polynomial, and e is the
term's exponent. Thus, an example polynomial might be
3x^2 + -4x^1 + 2x^0
which is read "3 x to the 2nd power plus negative 4 x to the 1st power
plus 2 x to the zeroth power". Because x^1 is really just x, and x^0
is really just 1, we can write this as
3x^2 - 4x + 2
which is read, more simply, as "3 x squared minus 4 x plus 2".
If you need a reminder about how to add, subtract, multiply, or evaluate
polynomials, you may want to take a look at the sample executions below,
refer to a basic algebra textbook, and/or check with your friendly
CS215 instructor.
Here are some requirements for your program:
- Your program should have the notion of a "current polynomial" that
it retains and displays the entire time your program is running.
- When your program first starts, the current polynomial should
automatically be set to 0 (which is really just the polynomial having
no terms).
- When the program asks the user to enter a polynomial:
- He or she should be allowed to enter the terms in any order.
- He or she should be allowed to enter terms with the same exponent more
than once, and have each of these terms added into the resulting
polynomial.
- He or she should be allowed to enter a term with a coefficient of 0,
but the program should ignore that term.
- He or she should signal the end of entering a polynomial by entering 0
for both the coefficient and the exponent.
- When the program is displaying a polynomial, it should follow the
following "standard format":
- It should display the terms in decreasing order by exponent.
- It should never display two terms having the same exponent.
- It should display a term whose coefficient is 1 without actually
displaying the 1 (for example, 1x^2 should be displayed simply as x^2).
- It should never display any term whose coefficient is 0 (unless
the polynomial has no terms at all, in which case it should simply
display the single polynomial term 0).
- For for a term containing x^1, it shouldn't display the exponent of
1 (for example, 5x^1 should be displayed simply as 5x).
- For a term containing x^0, it shouldn't display any of the x^0 (for
example, 7x^0 should be displayed simply as 7).
- Instead of displaying a plus sign, followed by a term with a
negative coefficient, it should instead display simply a minus sign
(for example, instead of 3x^2 + -2x + -1, it should display 3x^2 - 2x -
1).
- Your program should give back to the system any and all memory freed
up when discarding polynomials and/or their terms.
You should write this program by extending the LList class that
we are currently developing in our CS215 lecture to represent each
polynomial, and by (slightly) revising the listnode class that
we are currently using in lecture to represent each polynomial term.
As always, in order to make your main function relatively modular and
easy to read, you should also include additional methods and/or functions
as necessary.
Here are some hints to make your coding easier:
- You can assume that all polynomial coefficients will be whole numbers.
You can assume that all polynomials exponents will be non-negative
whole numbers.
- You can assume that there will always be sufficient memory to
allocate storage for new nodes in your linked lists.
- Be very careful using pointers! Many programming errors can be traced to
the incorrect use of pointers that are undefined (for example, that are
uninitialized or are dangling). Be sure that each pointer you are using
to access a listnode has directly or indirectly been initialized
by using the new operator, and that it isn't NULL, and
isn't dangling due to premature use of the delete operator.
If you seem to be having trouble getting your pointers to work, a good
debugging technique is to draw some sample LList objects by hand,
and then trace through your code step-by-step looking for places where
your pointers seem to go astray.
Be sure to follow the overall requirements for programming assignments
found in the document called "Programming Requirements" posted on the
CS215 Web Homepage. You'll need to develop and run your own thorough set
of testcases, as well as run the set of required testcases I will make
available shortly before the program listings and executions are due.
Be sure to submit your External Documentation printed out on paper, using
the MS Word word-processing program and the MS Word "External Documentation
Outline" provided on the CS215 Web Homepage.
Be sure to submit your Listing and Executions as two separate attachments
to a single piece of e-mail sent from your SWEB computer account using the
"pine" e-mail program. For your Listing, you should simply attach your
C++ program (which should be in a file called "program2.cc"). For your
Executions, you should attach your script file (which should be in a file
called "program2.script"). Make sure that your script file shows that your
program compiles using the g++ command on the SWEB Unix computer system,
and shows both the required testcases and your own proposed testcases being
executed by your program running on the SWEB Unix computer system. Be sure
to use the following Subject: line in your e-mail, based on your CS215
section number:
- For students enrolled in CS215 section 001 (Tuesdays and Thursdays
at 3:30 pm), use the subject line: CS215-001 PA2
Following is a sample of what your program executions should look like when
completed.
Good luck!
Polynomial Manipulation Package, Version 1.0 (c) 2002, (Your Name)
Current polynomial is P(x) = 0
Command (h for help): h
valid commands are:
r reset reset the current polynomial by entering a new one
a add add a new polynomial to the current polynomial
s subtract subtract a new polynomial from the current polynomial
m multiply multiply a new polynomial into the current polynomial
e evaluate evaluate the current polynomial at a given value of x
q quit quit the program
Current polynomial is P(x) = 0
Command (h for help): r
Resetting the current polynomial.
Enter coefficient and exponent (0 0 to stop): -2 1
Enter coefficient and exponent (0 0 to stop): 4 3
Enter coefficient and exponent (0 0 to stop): 5 0
Enter coefficient and exponent (0 0 to stop): 0 0
Entered polynomial is Q(x) = 4x^3 - 2x + 5
Resetting completed.
Current polynomial is P(x) = 4x^3 - 2x + 5
Command (h for help): a
Adding a new polynomial to the current polynomial.
Enter coefficient and exponent (0 0 to stop): 3 2
Enter coefficient and exponent (0 0 to stop): -2 3
Enter coefficient and exponent (0 0 to stop): 2 1
Enter coefficient and exponent (0 0 to stop): 0 0
Entered polynomial is Q(x) = -2x^3 + 3x^2 + 2x
Addition completed.
Current polynomial is P(x) = 2x^3 + 3x^2 + 5
Command (h for help): m
Multiplying a new polynomial into the current polynomial.
Enter coefficient and exponent (0 0 to stop): 3 2
Enter coefficient and exponent (0 0 to stop): 1 1
Enter coefficient and exponent (0 0 to stop): 0 0
Entered polynomial is Q(x) = 3x^2 + x
Multiplication complete.
Current polynomial is P(x) = 6x^5 + 11x^4 + 3x^3 + 15x^2 + 5x
Command (h for help): s
Subtracting a new polynomial from the current polynomial.
Enter coefficient and exponent (0 0 to stop): 8 7
Enter coefficient and exponent (0 0 to stop): 3 4
Enter coefficient and exponent (0 0 to stop): 0 0
Entered polynomial is Q(x) = 8x^7 + 3x^4
Subtraction completed.
Current polynomial is P(x) = -8x^7 + 6x^5 + 8x^4 + 3x^3 + 15x^2 + 5x
Command (h for help): r
Resetting the current polynomial.
Enter coefficient and exponent (0 0 to stop): 1 1
Enter coefficient and exponent (0 0 to stop): 2 1
Enter coefficient and exponent (0 0 to stop): 3 1
Enter coefficient and exponent (0 0 to stop): 2 3
Enter coefficient and exponent (0 0 to stop): -2 3
Enter coefficient and exponent (0 0 to stop): 0 4
Enter coefficient and exponent (0 0 to stop): 5 2
Enter coefficient and exponent (0 0 to stop): 0 0
Entered polynomial is Q(x) = 5x^2 + 6x
Resetting completed.
Current polynomial is P(x) = 5x^2 + 6x
Command (h for help): e
Evaluating the current polynomial.
Enter a value for x: 3
P(3) = 63
Evaluation completed.
Current polynomial is P(x) = 5x^2 + 6x
Command (h for help): q
Quitting Polynomial Manipulation Package.