一、大数加法的定义
在Java中，整数类型有四种，byte（8位）、short（16位）、int（32位）、long（64位）。
其中，int类型为32为，也就是说最大的整数为2^31，如果超过了这个数，那么就不能再用整型变量来保存，更不用说保存两个这么大的数的和了。
大数就是值超过整数最大上限的数，为了解决两个大数的求和问题，可以把两个加数看成是数字字符串，将这些数的相应数字存储在两个栈中，并从两个栈中弹出对应位的数字一次执行加法即可得到结果。
二、大数加法的实现
1.代码实现
public String addOfLargeNum(String a, String b) throws Exception {LinkStack sum = new LinkStack(); // 大数的和LinkStack sA = numSplit(a); // 加数字符串以单个字符的形式放入栈中 sA.stackTraverse();LinkStack sB = numSplit(b); // 被加数字符串以单个字符的形式放入栈中 sB.stackTraverse();int partialSum; // 对应位置的两个数相加boolean isCarry = false; // 是否仅为标识while (!sA.isEmpty() && !sB.isEmpty()) { // 两个栈都不为空partialSum = (Integer) sA.Pop() + (Integer)sB.Pop(); // 将两个栈的栈顶元素即大数的个位相加if (isCarry) { // 判断低位是否有进位partialSum++; // 如果有进位就加1isCarry = false; // 重置进位标识 }if (partialSum >= 10) { // 如果超过了10就需要进位partialSum -= 10; // 取个位数字sum.Push(partialSum); // 将得到的加和入大数的和栈isCarry = true; // 将进位标志位置为true} else {sum.Push(partialSum); // 不需要进位时直接放入栈中 }}LinkStack temp = !sA.isEmpty()? sA : sB; // 如果有一个加数比另一个加数短，则取长的那个加数加完剩下的栈while (!temp.isEmpty()) { if (isCarry) { // 最后一次执行加法运算中需要进位int t = (Integer)temp.Pop(); // 取出没有参加加法的位t++; // 加上进位位1if (t >= 10) { // 如果超过10，就需要进位t -= 10;sum.Push(t); // 这里没有改变进位标识isCarry，下一次还是true} else {sum.Push(t); // 不需要进位时直接入和栈isCarry = false; }} else {sum.Push(temp.Pop());}}if (isCarry) { // 最高一位入栈后仍然需要进位的情况sum.Push(1); // 再最高位的前一位入栈 }String str = new String();while (!sum.isEmpty()) { // 将栈中的数按正常顺序转化为字符串输出str = str.concat(sum.Pop().toString());}return str;}// 将字符串以单个字符的形式放入栈中，并去除字符串中的空格，返回以单个字符为元素的栈private LinkStack numSplit(String str) throws Exception {LinkStack s = new LinkStack();for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if (c == ' ') { // 去除空格continue; } else if ('0' <= c && c <= '9') { // 判断是不是0到9之间的数s.Push(Integer.valueOf(String.valueOf(c))); // 如果是，就将数字入栈} else {throw new Exception("输入了非法数字型字符");}}return s;}
2.测试和输出
public static void main(String[] args) throws Exception {AdditionOfLargeNumbers add = new AdditionOfLargeNumbers();String largeNum1 = "18 452 453 389 943 209 752 345 473";String largeNum2 = "8 123 542 678 432 986 899 334";System.out.println("两个大数相加得到的和为: " + add.addOfLargeNum(largeNum1, largeNum2));System.out.print("\n");System.out.println("两个大数相加得到的和为: " + add.addOfLargeNum("784", "8 465"));}输出： 此时，链栈中的元素为: 37454325790234998335425481 此时，链栈中的元素为: 4339986892348762453218 两个大数相加得到的和为: 18460576932621642739244807此时，链栈中的元素为: 487 此时，链栈中的元素为: 5648 两个大数相加得到的和为: 9249
3.分析代码执行过程
大数加法算法中主要是isCarry标志位的切换：以“784” + “8 465”为例：
首先，将两个字符取出空格并压入两个栈中，即sA=（栈顶）487， sB=（栈顶）5648
然后4出栈，5出栈，4+5=9，isCarry为false，9入栈sum，
然后8出栈，6出栈，8+6=14，isCarry为true，14-10=4入栈sum，
然后7出栈，4出栈，7+4+1=12,isCarry为true，12-10=2入栈sum，
此时sA为空，temp=sB=8,8出栈，8+1=9，isCarry为false，9入栈sum，
最后将栈sum按顺序输出为：924
