This homework consists of three programming problems creating successively-more complicated versions of the Reverse Polish Notation Calculator from the last homework. The first will make the calculator generic, but still use integers, the second will use Big Integers, and the third will extend this further by designing a calculator which can manipulate polynomials. You should make sure to observe the following points.
This problem is just to set the stage for the more challenging problems to follow. On the class web site, we give you a generic Reverse Polish Notation Calculator called RPNCalculator.java and a client IntegerCalculator.java which implements the user interface. We also give you an ancillary file MyInt.java, and two interfaces CalculatorOperand.java, and Stack.java. This calculator is a little different from the calculator from the last homework, for example, it does not print out the stack every time, but has an explicit command to do that. It also does not allow you to define variables (and hence does not use a symbol table).
The RPNCalculator is generic in that it will work on any classes that implement the CalculatorOperand interface:
public interface CalculatorOperand<T> {
void addTo (T addend); // Adds addend to the operand represented by this class
void subtractFrom (T subtrahend); // Ditto for subtraction
void multiplyBy (T multiplicand); // Ditto for multiplication
String toString(); // provide a string of this operand suitable for printing
}
What this basically does is to replace the normal +, -, and * by methods defined for a particular kind of value (i.e., not just doubles as in the last assignment); the calculator is thus just a generic way of managing a stack doing Reverse Polish arithmetic. Note that we've eliminated division to make your life easier in Problem 3. A simple example of such a class is the MyInt class which is simply a "wrapper" class for ints, providing these methods for ints.
You can see an example of this calculator in action on ints in the file Trace1.txt on the class web site.
What to do: The only thing missing is a stack (generic, of course), as you can see from the RPNCalculator class; what you must do is to implement a generic stack using linked lists, which satisfies the interface Stack.java. You should call this EvalStack, and note carefully the description of the operations in the interface code, as you must follow these to have the calculator behave properly. You will have to figure out how to write the toString method to get the calculator to print out the stack as in the Trace1.txt file. Get the calculator to work with your EvalStack and play around with the code so that you understand it thoroughly, as it will be the basis for the rest of the assignment.
What to hand in: EvalStack.java
Now you will extend this calculator so that it works on BigIntegers, which are defined in java.Math.BigInteger (which you will need to import) and which you can read about by Googling "BigInteger Java". You can keep the RPNCalculator and EvalStack classes, of course (because they are generic!), but need to reimplement the others. The calculator behaves just about as before, but you can type in integers that have, say, 35 digits; take a look at Trace2.txt on the web site to see a working version in action.
What to do: (A) You need to rewrite the operand class MyInt to use BigIntegers, calling it MyBigInteger. In order to do this, you will need to read about BigIntegers and in particular understand how arithmetic is done (using explicit methods such as add() rather and +, -, etc.). Note that BigInteger already implements a toString() method, so writing a toString method for your class should be easy! (B) Next, you need to rewrite the client code to create a BigIntegerCalculator class. (Hint: the Scanner class can work with BigIntegers, so you should look at its documentation in the Java API to understand how.)
What to hand in: MyBigInteger.java, BigIntegerCalculator.java.
Now we will repeat the process one more time, but this time for polynomials (in a single variable x), represented as linked lists. If you forgot how polynomials works, you may read about addition, subtraction, and multiplication of polynomials by Googling "polynomial arithmetic." As in the previous problem, you will need to implement a class for the new type of operand, and a client that drives the calculator. You can see a sample trace of a version of this calculator in Trace3.txt on the class web site.
What To Do
(A) You should think about how to represent the polynomials, and how to do the operations. Represent a monomial as a single node with two integers (the coefficient and the degree or exponent). Represent a polynomial as a linked list of monomials, in order of decreasing degree. Only monomials with nonzero coefficients should be present in your list. Thus, for example, 6x^10 + 4x^3 + 15x^2 + 2 should be represented as the list
(6,10) -> (4, 3) -> (15, 2) -> (2, 0).
(where (6,10) is a node containing two integers and a next pointer). It follows that the zero polynomial is the empty list.
Use the "header node" technique from the class notes.
Thus, at creation, your linked list has one node, and the meaningful parts
are pointed to by its next pointer.
Write a constructor Polynomial(int c, int d) that takes a coefficient c and a degree d and
creates a new polynomial cx^d. If the coefficient is 0, it should
create
the zero polynomial.
You will never create polyomials with more than a single monomial by using the constructor. Instead, you will use the addition and subtraction methods of the calculator to build up larger polynomials as sums of monomials. Take a look at the trace file to understand this point.
(B) Before writing any other arithmetic methods, write a private method
void addToAndDestroy (Polynomial addend) that adds
addend to the current polynomial and destroys addend
itself in the process. This method should not allocate any more memory;
rather, it should
merge the two lists of monomials---the list present in this and
the list present in addend. Be sure to merge monomials with the
same degree properly by adding their coefficients, and to discard the
resulting node if the coefficients turns out to be zero. For example,
adding 6x^10 + 4x^3 + 15x^2 + 2 and 8x^12 + x^9 - 4x^3 + 7x^2 + x
amounts to merging the lists
(6,10) -> (4, 3) -> (15, 2) -> (2, 0) and
(8,12) -> (1, 9) -> (-4, 3) -> (7, 2) -> (1, 1),
which will make the (4, 3)
node cancel the (-4, 3) node, and (15, 2) node combine with the (7,2)
node to form the (22, 2) node.
If properly written, this method will run in time Theta(m+n), where m
and n
are the numbers of monomials in the two polynomials. Note that, because of
the already-sorted order of polynomials, this is
faster than adding one monomial at a time, which could take as along as Omega(mn) (we will cover
Theta and Omega -- cousins of O -- in class shortly).
(C) Now write the addTo, which copies the addend to a new
temporary polynomial, and then calls addToAndDestroy. Write the
subtractFrom method similarly. Make sure that the addend
and the subtrahend themselves are not modified.
You may wonder why bother writing addTo when one can build an
RPN calculator using addToAndDestroy, since the calculator
doesn't mind if the operands are destroyed during the operation, and
addToAndDestroy is more efficient. The answer is that often there
is a tradeoff between safety and generality on the one hand, and efficiency
on the other. If you were really producing a Polynomial class for
a large project, publishing the addTo method would be safer than addToAndDestroy method, which has the side effect of destroying
its argument that some users of your class may not understand (and thus may
produce buggy code). Moreover, the CalculatorOperand interface
says it must provide addTo. Of course, because the interface
doesn't specify that the argument of addTo cannot be destroyed,
you could simply write addTo the way you wrote
addToAndDestroy, and it would work correctly for this application.
However, such addTo would be very unsafe, because nothing in the
name of the method suggests that it would destroy its argument, and someone
else (or you yourself at some later time) using this method is likely to
introduce a bug because of it.
(D) Now write the multiplyBy method to consist of repeated
multiplication by monomials and additions. Create a new polynomial
res to hold
the result, initialized to zero. For each monomial of this,
create a new temporary polynomial equal to multiplicand times the
monomial (this is similar to the copying code in addTo, except you
multiply by the monomial as you copy), and then addToAndDestroy it
to the res. Finally, move the linked list of res back over to
the linked list of this (that can be done in a single assignment,
because you don't need to preserve res).
If properly written, this will take time Theta(mn).
(E) Write a toString method that produces reasonable-looking
strings representing polynomials. This is a bit tricky to write because of
special cases. Make sure it produces outputs that match the following
examples verbatim (because automated grading scripts will be applied to the output of your programs):
4x^2 - x + 2
-x^3 - 2x^2 + x + 1
x^2 - 1
-2x^5
0
1
-1
It may be a good idea to work on designing the class and writing the
constructor and
addToAndDestroy together.
(F) Now you need to write the class PolynomialCalculator to simulate the behavior shown in the file Trace3.txt. The essential idea is that you will be reading ints (not BigIntegers!) as in Problem 1, but you will need to read two ints (separated by white space) for each monomial, representing the coefficient and the exponent.
What to hand in:
Polynomial.java, PolynomialCalculator.java.