Addition and Subtraction of large ints without Math.BigInteger

Question

Alright, so I have been assigned an exercise in using stacks. The challenge for this assignment is to create a program that can add and subtract extremely large integers (presumably of infinite size) without using any libraries or imports (e.g no BigInteger).

This is how I approached addition:

---

public Stack<Integer> sum(Stack<Integer> leadingStack, Stack<Integer> secondStack) {
    int carry = 0;
    Stack<Integer> resultStack = new Stack<Integer>();
    while (leadingStack.isEmpty() == false && secondStack.isEmpty() == false) {
        int result = 0;
        int dig1 = leadingStack.pop();
        int dig2 = secondStack.pop();
        int resultDig = 0;

        result = dig1 + dig2 + carry;
        resultDig = result % 10;
        carry = result / 10;
        resultStack.push(resultDig);
    }
    if (carry > 0)
        resultStack.push(carry);
    return resultStack;
}

This method appears to work with some integers and not others. For example, if I input 500 & 450, I get 950 as expected. However, if I input 500 and 45, I get 45.

---

And this is how I approached subtraction (very similar approach):

---

    public Stack<Integer> sub(Stack<Integer> leadingStack, Stack<Integer> secondStack) {
    boolean borrow = false;
    Stack<Integer> resultStack = new Stack<Integer>();
    while (leadingStack.isEmpty() == false && secondStack.isEmpty() == false) {
        int dig1 = leadingStack.pop();
        int dig2 = secondStack.pop();
        if (borrow = true) {
            dig1 -= 1;
            borrow = false;
        }
        if (dig1 - dig2 < 0) {
            dig1 += 10;
            resultStack.push(dig1 - dig2);
            borrow = true;
        }
    }
    return resultStack;
}

This has a very similar issue. For example, if I subtract 50 and 45, I get 4. if I subtract 50,000 and 45,000 I get 4,900.

---

I am sure I am missing something simple here, but I have looked over the code over and over and I am not sure what it is.

Answer 1

There are few places in your code that need attention:

• If stacks have different size, the remaining part of a bigger stack is not handled
• When returning the result stack, its elements has to be reversed as the smallest position digit is pushed first (and bigger position last)
• Mixed assignment operator with equality at if (borrow = true)
• Subtraction method does not handle negative numbers

All together in code:

public Stack<Integer> sum(Stack<Integer> leadingStack, Stack<Integer> secondStack) {
  int carry = 0;
  Stack<Integer> resultStack = new Stack<Integer>();
  while (leadingStack.isEmpty() == false && secondStack.isEmpty() == false) {
    int dig1 = leadingStack.pop();
    int dig2 = secondStack.pop();
    int result = dig1 + dig2 + carry;
    int resultDig = result % 10;
    carry = result / 10;
    resultStack.push(resultDig);
  }

  Stack<Integer> leftStack = leadingStack.isEmpty() ? secondStack : leadingStack;
  while (leftStack.isEmpty() == false) {
    int dig = leftStack.pop();
    if (carry > 0) {
        dig += carry;
        carry = 0;
    }
    resultStack.push(dig);
  }

  if (carry > 0) resultStack.push(carry);
  return reverse(resultStack);
}

public Stack<Integer> sub(Stack<Integer> leadingStack, Stack<Integer> secondStack) {
  boolean borrow = false;
  Stack<Integer> resultStack = new Stack<Integer>();

  if (leadingStack.size() < secondStack.size()) {
    // Handle negative number
  }
  while (leadingStack.isEmpty() == false && secondStack.isEmpty() == false) {
    int dig1 = leadingStack.pop();
    int dig2 = secondStack.pop();
    if (borrow) {
        dig1 -= 1;
        borrow = false;
    }
    if (dig1 < dig2) {
        dig1 += 10;
        resultStack.push(dig1 - dig2);
        borrow = true;
    }
    else {
        resultStack.push(dig1 - dig2);
    }
  } 

  Stack<Integer> leftStack = leadingStack.isEmpty() ? secondStack : leadingStack;
  while (leftStack.isEmpty() == false) {
    int dig = leftStack.pop();
    if (borrow) {
      dig -= 1; 
      borrow = false;
    }
    resultStack.push(dig);
  }

  if (borrow) {
    // Handle negative number
  }
  return reverse(resultStack);
}

private Stack<Integer> reverse(Stack<Integer> inStack) {
  Stack<Integer> outStack = new Stack<>();
   while (inStack.isEmpty() == false) outStack.push(inStack.pop());
   return outStack;
}