Question

Dynamic Implementation of Stack -

The purpose is to use our dynamic implementation of stack. The application will be to add large numbers.

Review adding large numbers

Remember that we can use stacks to safely add integer values that overflow the int data type

• g. in Java, the maximum possible int value Integer.MAX_VALUE is:
  2147483647
• so any int addition larger than this will overflow and fail

Using stacks to add large numbers safely

Will actually represent the large integers to be added as strings of characters, to avoid any overflow problems here. Then will use three(!) stacks of datatype Integer to do the addition safely.

The idea is to add each pair of digits from the numbers, from right to left. The units part of this total is pushed to the results stack, the tens part is the carry digit, added in to the next pair.

The addition algorithm in pseudocode is something like:

//push digits from numbers into stacks in appropriate order
loop for the digits in the first number
    push digit to first stack
loop for the digits in the second number
    push digit to second stack
//pop stacks, add digits and push result to result stack.  Careful with carry
while (!stacks are empty)
    pop digits from stacks and add
    push units part to result stack
    tens part is the carry to be added in next iteration
//print the result from the result stack
while (!result stack is empty)
    pop result stack

Open the project and see Tester::main(). You must write code in the Tester::main() method that uses the stack implementation to add the pairs of numbers given.

Format your output so that it shows the first and second numbers, and your result (I've used '?' below to show where your result will go). Run your program three times to test each of the pairs of numbers provided e.g.

1 + 2147483647 = ?

2147483647 + 1 = ?

2147483647 + 2147483647 = ?

public class Tester
{
public static void main()
{
//first shorter
String first = "1";
String second = "2147483647";

//second shorter
//String first = "2147483647";
//String second = "1";

//same length
//String first = "2147483647";
//String second = "2147483647";
  
//you must write all of your code here
}
}

public class StackUnderflowException extends RuntimeException
{
public StackUnderflowException()
{
super();
}

public StackUnderflowException(String message)
{
super(message);
}
}

public class LinkedStack<T> implements StackInterface<T>
{
private Item<T> top;

public LinkedStack()
{
top = null;
}

public void push(T element)
{
Item<T> item = new Item<T>(element);

if (!isEmpty())
item.next = top;

top = item;
}

public T pop() throws StackUnderflowException
{
if (isEmpty())
throw new StackUnderflowException("Pop attempted on empty stack");
else {
T info = top.info;
top = top.next;
return info;
}
}

public boolean isEmpty()
{
return top == null;
}
}

public interface StackInterface<T>
{
void push(T element);

T pop() throws StackUnderflowException;

boolean isEmpty();
}

public class Item<T>
{
protected T info;
protected Item<T> next;

public Item()
{
info = null;
next = null;
}

public Item(T info)
{
this.info = info;
next = null;
}
}

Answer 1

:: solution ::

public static void main(String []args){
        String first = "2147483647";
        String second = "2147483647";
        
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        
        int len1 = first.length();
        int len2 = second.length();
        
        int duplen1 = len1;
        int duplen2 = len2;
        while(len1>0 || len2>0){
                if(len1>0){
                        stack1.push(first.charAt(duplen1-len1)-'0');
                        len1--;
                }
                if(len2>0){
                        stack2.push(second.charAt(duplen2-len2)-'0');
                        len2--;
                }
        }
        
        String res = "";
        
        int carry = 0;
        while(!stack1.isEmpty() || !stack2.isEmpty()){
                int firstDigit = (stack1.isEmpty())?0:stack1.pop();
                int secondDigit = (stack2.isEmpty())?0:stack2.pop();
                if(carry+firstDigit+secondDigit >= 10){
                        res = (carry+firstDigit+secondDigit-10)+res;
                        carry = 1;
                }
                else{
                        res = (carry+firstDigit+secondDigit)+res;
                        carry = 0;
                }
        }
        if(carry==1){
                res = 1+res;
        }
        
        System.out.println("sum of numbers "+first+" and "+second+" = "+res);
}

</> Online Java Compiler - Online Jax + X ... f → CO tutorialspoint.com/compile_java_online.php codingground Compile and Execute Java Online (JDK 1.8.0) Fork 1. Project - Edit Setting & Login SIMPLY EASY CODING STDIN Lili Result BOL . Execute > Share Source File 1 import java.util.*; 2- public class HelloWorld{ $javac HelloWorld.java $java -Xmx128M -Xms16M HelloWorld sum of numbers 1 and 2147483647 = 2147483648 public static void main(String []args) { String first = "1"; String second = "2147483647"; Stack<Integer> stack1 = new Stack<>(); Stack<Integer> stack2 = new Stack<>(); int len1 = first.length(); int len2 = second.length(); int duplen1 = len1; int duplen2 = len2; while(len1>0 || len2>0){ if(len1>0){ stack1.push(first.charAt(duplen1-len1)-'0'); len1--; } if(len2>0){ stack2.push(second.charAt(duplen2-len2)-'0'); len2--; } 10 11 12 13 14 15 16 17 - 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 } String res = ""; int carry = 0; while(!stack1.isEmpty() || !stack2.isEmpty()){ int firstDigit = (stack1.isEmpty())?0:stack1.pop(); int secondDigit = (stack2.isEmpty())?0:stack2.pop(); if(carry+firstDigit+secondDigit >= 10) { res = (carry+firstDigit+secondDigit-10)+res; carry = 1; } else{ res = (carry+firstDigit+secondDigit)+res; carry = @; } IH Type here to search fi ENG 18:21 US 15-09-2020 1 26

</> Online Java Compiler - Online Jax + X ... CO tutorialspoint.com/compile_java_online.php codingground Compile and Execute Java Online (JDK 1.8.0) Fork 1. Project - Edit Setting & Login SIMPLY EASY CODING STDIN Lili Result BOL . Execute > Share Source File 1 import java.util.*; 2- public class HelloWorld{ $javac HelloWorld.java $java -Xmx128M -Xms16M HelloWorld sum of numbers 2147483647 and 1 = 2147483648 public static void main(String []args) { String first = "2147483647"; String second = "1"; Stack<Integer> stack1 = new Stack<>(); Stack<Integer> stack2 = new Stack<>(); int len1 = first.length(); int len2 = second.length(); int duplen1 = len1; int duplen2 = len2; while(len1>0 || len2>0){ if(len1>0){ stack1.push(first.charAt(duplen1-len1)-'0'); len1--; } if(len2>0){ stack2.push(second.charAt(duplen2-len2)-'0'); len2--; } 10 11 12 13 14 15 16 17 - 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 } String res = ""; int carry = 0; while(!stack1.isEmpty() || !stack2.isEmpty()){ int firstDigit = (stack1.isEmpty())?0:stack1.pop(); int secondDigit = (stack2.isEmpty())?0:stack2.pop(); if(carry+firstDigit+secondDigit >= 10) { res = (carry+firstDigit+secondDigit-10)+res; carry = 1; } else{ res = (carry+firstDigit+secondDigit)+res; carry = @; } IH Type here to search fi ENG 18:22 US 15-09-2020 1 26

</> Online Java Compiler - Online Jax + X ... CO tutorialspoint.com/compile_java_online.php codingground Compile and Execute Java Online (JDK 1.8.0) Fork 1. Project - Edit Setting & Login SIMPLY EASY CODING STDIN Lili Result BOL . Execute > Share Source File 1 import java.util.*; 2 public class HelloWorld{ $javac HelloWorld.java $java -Xmx128M -Xms16M HelloWorld sum of numbers 2147483647 and 2147483647 = 4294967294 public static void main(String []args) { String first - "2147483647"; String second = "2147483647"; Stack<Integer> stack1 = new Stack<>(); Stack<Integer> stack2 = new Stack<>(); int len1 = first.length(); int len2 = second.length(); int duplen1 = len1; int duplen2 = len2; while(len1>0 || len2>0){ if(len1>0){ stack1.push(first.charAt(duplen1-len1)-'0'); len1--; } if(len2>0){ stack2.push(second.charAt(duplen2-len2)-'0'); len2--; } 10 11 12 13 14 15 16 17 - 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 } String res = ""; int carry = 0; while(!stack1.isEmpty() || !stack2.isEmpty()){ int firstDigit = (stack1.isEmpty())?0:stack1.pop(); int secondDigit = (stack2.isEmpty())?0:stack2.pop(); if(carry+firstDigit+secondDigit >= 10) { res = (carry+firstDigit+secondDigit-10)+res; carry = 1; } else{ res = (carry+firstDigit+secondDigit)+res; carry = @; } IH Type here to search fi ENG 18:22 US 15-09-2020 1 26

I have provide you the main function with code.

And also provided the screenshots of the inputs you provided for testing.

Hope you like it.