P1

a. Completing the LinkedStack class

In the LinkedNumberStack class, you are required to implement the following methods:

push(int v) – This method adds an integer to the top of the stack.

pop() – This method removes an element from the top of the stack and returns the element. It throws a RuntimeException "pop attempted on an empty stack" if this operation is attempted on an empty stack.

size() – This method returns the number of elements on the stack.

Note that you are only supposed to touch the above three methods. You are NOT allowed to create any other methods, instance variables, or make any changes to methods other than these three methods or files other than "LinkedNumberStack.java". Points will be taken off if you fail to follow this rule.

b. Code Testing

You are provided with a test driver implemented by "TestStack.java" (Do not make any changes to this file!) so there is no need to write your own.

Once you have completed the methods, you can run the test. You should create a plain text file named "output-P1.txt", copy and paste the output corresponding to Problem 1 (if your code crashes or does not compile, copy and paste the error messages) to this file and save it.

P2

a. Completing the StackApps class

In this programming question, you are required to implement two methods, a binary number conversion and a big integer subtraction.

(1) An XOR (eXclusive OR ) operation on two operands return false if they are identical and true otherwise. For instance, both ‘+’ XOR ‘-’ and ‘-’ XOR ‘+’ return ‘+’ whereas ‘+’ XOR ‘+’ and ‘-’ XOR ‘-’ return ‘-’. Note that we use character ‘+’ to represent true and ‘-’ for false. In the StackApps class, the evaluateSigns() method takes a stack of signs (‘+’ and ‘-’) and performs the XOR operations on every pair of adjacent signs saved on the stack. It reduces the number of signs by 1 after each round and eventually there is only one sign left. The method returns this sign as the result of the evaluation. In the following example, you will see how the method evaluates the signs.

To do this task, you will need to use an auxiliary stack (already created for you) that helps you save the reduced expression. You need to alternate between the signs and the aux stacks because you cannot simply push a sign back into the stack which you just popped off (without using other techniques such as recursion). Do not create any arrays or other data structures in your implementation. Using char variables is okay.

(2) When an integer has more than a certain number of digits, it is represented using scientific notation. The int type itself cannot be used to store numbers with more than 10 digits. In some cases, this may be inconvenient as people usually expect complete numbers and doing big integer computations are inevitable. The addBigInteger() method takes two numbers as CharStacks num1 and num2, and add the number stored in num1 to the one stored in num1, i.e., num1 + num2. For example, when adding 181,749 to 314,739,847, the two stacks and the result stack would look like the following:

In the addBigInteger() method, you are provided with a char stack, stackResult. You will need to perform additions between the two operands and save the result on the result stack. Pay attention to the order of the digits (see above figure for reference). You should compute the sum of the two big numbers digit by digit (from low to high). Be sure to take care of carries. Do not create any arrays or import the java.math.BigInteger library or anything from the Character, Integer, Double, and String classes in your implementation! Same as above, you are only supposed to deal with the digits at the char and int level and make use of stacks.

Note that you are only supposed to touch the above two methods. You are NOT allowed to create any other methods, instance variables, or make any changes to methods other than the two method or files other than "StackApps.java".

b. Code Testing

In "TestStack.java" (Again, do not make any changes to this file!), a test driver for StackApps is provided. You are also given a data file "testNumbers.dat" that contains 5 decimal numbers that need to be converted to binary and 15 pairs of big integers for subtraction.

Depending on your programming environment, the data file might need to be placed in different folders so that you test driver can read it. For jGRASP, you can leave the data file in the same folder as your java files. For IntelliJ, you should place it in your project folder in which you see directories like out and src, etc.

Once you have completed the evaluateSigns and addBigInteger methods, you can run the test. You should create a plain text file named "output-P2.txt", copy and paste the output corresponding to Problem 2 (if your code crashes or does not compile, copy and paste the error messages) to this file and save it.

This assignment has been answered 2 times in private sessions.