Due Friday, April 11 2008

Your assignment is to write two classes:

- LinkedBigInt -- implements the the BigIntADT below; represents and manipulates arbitrarily large non-negative integers.
- EvalBigInts -- takes postfix expressions using only the operations +, *, e (exponent) and ! (factorial) from a file, and evaluates it using a stack and representing the numbers as LinkedBigInts.

public interface BigIntADTYou should write a LinkedBigInt class that uses a linked list to implement this interface. Some helpful advice:

{

// Gives the number of digits in the BigInt

public int length();

// Returns a BigInt representing the sum of the

// current BigInt and int2

public BigIntADT add(BigIntADT int2);

// Returns a BigInt representing the product of the

// current BigInt and int2

public BigIntADT mult(BigIntADT int2);

// Returns a BigInt representing the the current BigInt

// raised to the int2 power

public BigIntADT power(BigIntADT int2);

// Returns a BigInt representing the factorial of int

public BigIntADT factorial(BigIntADT int)

// Returns true if the current BigInt is the same as

// int2, false otherwise

public boolean equals(BigIntADT int2);

// Returns a string representation of the current BigInt

public String toString();

// Returns an iterator that provides the digits of the current

// BigInt, one at a time.

public Iterator iterator();

}

- If you store the digits backwards in the list it will be easier
to manipulate your BigInts (e.g., add them). Think about what you do in
computing 437 + 28:
- 8+7=15; put down the 5, carry the 1
- 1 (carry) + 3 + 2 = 6
- 4 + 0 = 4

- Once you have figured out addition, multiplication should be
easy.
Just remember that
*x * y*is just*x + x + ... + x*(y xs). That is, you can think of multiplication as repeated addition. Start with 0 and add*x*to it*y*times, and voila! You've computed*x * y*. - Once you have figured out multiplication, exponentiation should
be easy.
Just remember that
*x*is just^{y}*x * x * ... * x*(y xs). That is, you can think of exponentiation as repeated multiplication. Start with 1 and multiply by*x**y*times, and voila! You've computed*x*.^{y}

- Factorial is the same idea yet again - start at 1 and work your
way up to x (1 * 2 *.... * x)

- The equals method can just compare the corresponding digits of the two bigints. This does assume that there is just one representation for each integer -- in particular, that there are no leading 0s. So 0 should just be 0, never 00 or 000, and 16 should never be 016. Be sure that your initial representations are in this form and that your BigInts stay in this form as you manipulate them.
- You'll want to provide 3 constructors for generating
BigInts.

- The first should be null - this should create a BigInt
initialized to 0.

- The second should take an int - allowing us to seemlessly
translate between ints and BigInt.

- The third should take a String value - this can be used to
initialize a BigInt that is already too big to be represented as
an int. You need to take care to ensure that the
string contains only numbers. If the constructor is called
with a bad string, it should throw an exception.

Code for a stack evaluator is in the text and last week's lab;
yours will be similar, but your use of bigints will require some modifications.