Skip to content

Instantly share code, notes, and snippets.

@cgmb
Created March 5, 2015 03:57
Show Gist options
  • Save cgmb/fbee8cfd7160a5a475ad to your computer and use it in GitHub Desktop.
Save cgmb/fbee8cfd7160a5a475ad to your computer and use it in GitHub Desktop.
Adding big numbers using a stack of digits in Java
public class Add {
public static int charToInt(char c) {
return Integer.parseInt(Character.toString(c));
}
public static LLStack<Integer> stackDigits(String s) {
LLStack<Integer> stack = new LLStack<Integer>();
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
try {
stack.push(charToInt(c));
} catch (IllegalArgumentException e) {
System.err.println("Invalid number: " + s);
System.exit(2);
}
}
return stack;
}
public static int getNextDigit(LLStack<Integer> stack) {
if (stack.isEmpty()) {
return 0;
} else {
return stack.pop();
}
}
public static void main(String[] args) {
if (args.length != 2) {
System.err.println("usage: java Add <number> <number>");
System.exit(1);
}
String result = "";
LLStack<Integer> left = stackDigits(args[0]);
LLStack<Integer> right = stackDigits(args[1]);
int carry = 0;
while (!left.isEmpty() || !right.isEmpty()) {
int sum = getNextDigit(left) + getNextDigit(right) + carry;
result = Integer.toString(sum % 10) + result;
carry = sum / 10;
}
if (carry != 0) {
result = Integer.toString(carry) + result;
}
System.out.println(result);
}
}
import java.util.NoSuchElementException;
public class LLStack<T> {
public LLStack() {
list = new ForwardList<T>();
}
public T pop() {
if (list.isEmpty()) {
throw new NoSuchElementException("No element to pop! List is empty!");
}
T data = list.head.data;
list.removeAtHead();
return data;
}
public void push(T element) {
list.insertAtHead(element);
}
public boolean isEmpty() {
return list.isEmpty();
}
private ForwardList<T> list;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment