CSE 214 Data structures Homework 1: Abstract Data Types
HOMEWORK - FALL 2023
HOMEWORK 1 - due Friday, September 15th by 7PM (China time)
REMINDERS:
- Be sure your code follows the coding style for CSE214.
- Make sure you read the warnings about academic dishonesty. Remember, all work you submit for homework or exams MUST be your own work.
- Login to your grading account and click "Submit Assignment" to upload and submit your assignment.
- You are not allowed to use ArrayList, LinkedList, Vector, BigDecimal, BigInteger or any other predefined Java API Data Structure classes to implement this assignment.
- You may use Scanner, InputStreamReader, or any other class that you wish for keyboard input.
High precision arithmetic arises in many numerical analysis applications. However most programming languages, including Java, only support numbers with limited precision as their built-in data types. The purpose of this assignment is to design a LongInteger Abstract Data Type that defines a nonnegative long integer with desired precision and implements the basic arithmetic operations on long integers. Also a test program is required to verify the correctness of LongInteger ADT.
A nonnegative (unsigned) long integer is represented as a string of digits, where each digit is a number from 0 to 9. The maximum number of digits should be defined as a final variable.
1. Write a fully-documented class named LongInteger that stores a long integer in an array of integers. Each element of the array contains one digit of the long integer. There are different options to store the long integer. However it is recommended that you store the digits of the long integer from right to left starting from index 0 of the array, i.e. the rightmost digit is placed in index 0. The maximum number of digits is defined as MAX_DIGITS, which should be set to 100. Make sure you write your code using MAX_DIGITS instead of 100; otherwise 5 points will be deducted! The class will be based on the following ADT specification:
public class LongInteger
The LongInteger class implements an abstract data type for long integers supporting common operations on long integers.
- Constructor for LongInteger
public LongInteger()
Construct an instance of the LongInteger class with all elements set to 0.
Postcondition:
This LongInteger has been initialized to 0. - clone
public Object clone()
Generate a copy of this LongInteger.
Returns:
The return value is a copy of this LongInteger. Subsequent changes to the copy will not affect the original, nor vice versa. Note that the return value must be typecast to a LongInteger before it can be used. - equals
public boolean equals (Object obj)
Compare this LongInteger to another object for equality.
Parameters:
obj - an object in which this LongInteger is compared
Returns:
A return value of true indicates that obj refers to a LongInteger object with the same value as this LongInteger. Otherwise, the return value is false.
Note:
If obj is null or it is not a LongInteger object, then the return value is false. - setDigit
public void setDigit(int digit, int position)
Set the digit associated with the given position for this LongInteger.
Parameters:
digit - value of a digit in this LongInteger
position - position of a digit in this LongInteger.
NOTE: The rightmost digit of a long integer is in position 0.
Preconditions:
This LongInteger object has been instantiated, 0 < position < MAX_DIGITS-1 and 0 < digit < 9.
Postcondition:
Sets the multiplier of the given position of this LongInteger to the given digit.
Throws:
IllegalArgument
Indicates that digit is not from 0 to 9, or position is negative or exceeds the maximum number of digits. - getDigit
public int getDigit(int position)
Get the digit associated with the given position for this LongInteger.
Parameters:
position - position of any digit in this LongInteger
Preconditions:
This LongInteger object has been instantiated, and 0 < position < MAX_DIGITS-1.
Returns:
The digit associated with the given position for this LongInteger.
Throws:
IllegalArgument
Indicates that position is negative or exceeds the maximum number of digits of a LongInteger. - add
public static LongInteger add(LongInteger p1, LongInteger p2)
Generates and returns the sum of two given LongIntegers.
Parameters:
p1 - the first LongInteger
p2 - the second LongInteger
Precondition:
This LongInteger objects referenced by p1 and p2 have been instantiated.
Returns:
A LongInteger containing the sum of the two given LongInteger parameters.
Note:
The return value is null if either p1 or p2 is null.
Throws:
ResultOverFlow
Indicates that the result exceeds the maximum number of digits. - subtract
public static LongInteger subtract(LongInteger p1, LongInteger p2)
Generates and returns the difference of two given LongIntegers.
Parameters:
p1 - the first LongInteger
p2 - the second LongInteger
Precondition:
This LongInteger objects referenced by p1 and p2 have been instantiated.
Returns:
A LongInteger containing the difference of the two given LongInteger parameters, i.e. p1 - p2.
Note:
The return value is null if either p1 or p2 is null.
Throws:
ResultOverFlow
Indicates that p2 is greater than p1. - multiply
public static LongInteger multiply(LongInteger p1, LongInteger p2)
Generates and returns the product of two given LongIntegers.
Parameters:
p1 - the first LongInteger
p2 - the second LongInteger
Precondition:
This LongInteger objects referenced by p1 and p2 have been instantiated.
Returns:
A LongInteger containing the product of the two given LongInteger parameters.
Note:
The return value is null if either p1 or p2 is null.
Throws:
ResultOverFlow
Indicates that the result exceeds the maximum number of digits. - multiplyByNumber
public void multiplyByNumber(int number)
Calculates the product of the given number by this LongInteger.
Parameters:
number - the number to be multiplied by this LongInteger, where 0 < number < 10.
Precondition:
This LongInteger object has been instantiated.
Postcondition:
Calculates the product of the given number by this LongInteger and store the result in this LongInteger.
Throws:
ResultOverFlow
Indicates that the result exceeds the maximum number of digits.
Note: This is an auxiliary method that can be used to multiply two long integers. If the given number is equal to 10, simply append a zero to the right of this LongInteger (i.e. multiply by 10), otherwise multiply the number by this LongInteger. - divide (optional - extra credit)
public static LongInteger divide(LongInteger p1, LongInteger p2)
Generates and returns the quotient of two given LongIntegers.
Parameters:
p1 - the first LongInteger
p2 - the second LongInteger
Precondition:
This LongInteger objects referenced by p1 and p2 have been instantiated.
Returns:
A LongInteger containing the quotient of the two given LongInteger parameters, i.e. p1 div p2.
Note:
The return value is null if either p1 or p2 is null.
Throws:
ResultOverFlow
Indicates that p2 is equal to zero.
Notes:
- You may define an additional constructor that takes a string of digits and constructs an instance of LongInteger.
- To increase the performance of your code, you may declare a variable such as manyDigits, which holds the number of digits in a LongInteger.
2. Write a fully documented class named LongIntegerOperations that is based on the following specification:
public class LongIntegerOperations
The LongIntegerOperations Java application tests the methods of the LongInteger class and allows the user to input long integers and perform operations on them.
- main
public static void main(String[] args)
The main method reads a sequence of operations and associated long integers from the keyboard and displays the results after each operation is performed. Following is the list of abbreviations and number of parameters for each operation:
Add: A <LongInteger> <LongInteger> Divide: D <LongInteger> <LongInteger> optinal - extra credit Equal: E <LongInteger> <LongInteger> Multiply: M <LongInteger> <LongInteger> Subtract: S <LongInteger> <LongInteger> Quit program: Q
3. Also, provide additional class(es) to handle the exceptions.
Note: You may include additional methods in the LongInteger class or LongIntegerOperations, as necessary.
INPUT FORMAT:
- Each operation and its associated long integers are entered on separate lines.
- Each long integer is entered on one line. Leading zeros are accepted but they must be ignored.
- A long integer consists of decimal digits (0 to 9), and no other symbols are used.
- You may assume that all input numbers are non-negative long integers and there are no errors in the input (DON'T CHECK FOR ANY POSSIBLE ERRORS IN THE INPUT).
OUTPUT FORMAT:
- Echo the input numbers in the output. Leading zeros must be removed.
- All outputs must be accompanied by additional information (or symbols) explaining the specific operation, as shown in the sample output.
SAMPLE INPUT/OUTPUT:
// Comment in green, input in red, output in black
(A) Add (D) Divide (E) Equal (M) Multiply (S) Subtract (Q) Quit Enter a selection: A Enter number 1: 111111111111111111111111111111111111111111111111111111111111111111111111 Enter number 2: 222222222222222222222222222222222222222222222222222222222222222222222222 Answer: 111111111111111111111111111111111111111111111111111111111111111111111111 + 222222222222222222222222222222222222222222222222222222222222222222222222 = 333333333333333333333333333333333333333333333333333333333333333333333333 // show menu Enter a selection: A Enter number 1: 55555 Enter number 2: 222222222222222222222222222222222222222222222222 Answer: 55555 + 222222222222222222222222222222222222222222222222 = 222222222222222222222222222222222222222222277777 // show menu Enter a selection: A Enter number 1: 9999999999999999999999999999999999999999999999999999 Enter number 2: 1111111111111111111111111111111111111111111111111111 Answer: 9999999999999999999999999999999999999999999999999999 + 1111111111111111111111111111111111111111111111111111 = 11111111111111111111111111111111111111111111111111110 // show menu Enter a selection: S Enter number 1: 999999999999999999999999999999999999999999999999999999999999999999999999 Enter number 2: 333333333333333333333333333333333333333333333333333333333333333333333333 Answer: 999999999999999999999999999999999999999999999999999999999999999999999999 - 333333333333333333333333333333333333333333333333333333333333333333333333 = 666666666666666666666666666666666666666666666666666666666666666666666666 // show menu Enter a selection: M Enter number 1: 444444444444444444444444444444444444444444444444 Enter number 2: 02 Answer: 444444444444444444444444444444444444444444444444 * 2 = 888888888888888888888888888888888888888888888888 // show menu Enter a selection: M Enter number 1: 3333333333333333333333333333333333333333333333333333333333333333 Enter number 2: 11 Answer: 3333333333333333333333333333333333333333333333333333333333333333 * 11 = 36666666666666666666666666666666666666666666666666666666666666663 // show menu Enter a selection: E Enter number 1: 123456789012345678901234567890 Enter number 2: 0000123456789012345678901234567890 Answer: 123456789012345678901234567890 = 123456789012345678901234567890 ? True // show menu Enter a selection: E Enter number 1: 123456789012345678901234567890 Enter number 2: 1234567890123456789012345678900000 Answer: 123456789012345678901234567890 = 1234567890123456789012345678900000 ? False // show menuEnter a selection: Q
Program terminated normally.
