数据结构（十）栈的作用--大数的加法运算

　　一、大数加法的定义

　　在Java中，整数类型有四种，byte（8位）、short（16位）、int（32位）、long（64位）。

　　其中，int类型为32为，也就是说最大的整数为2^³¹，如果超过了这个数，那么就不能再用整型变量来保存，更不用说保存两个这么大的数的和了。

　　大数就是值超过整数最大上限的数，为了解决两个大数的求和问题，可以把两个加数看成是数字字符串，将这些数的相应数字存储在两个栈中，并从两个栈中弹出对应位的数字一次执行加法即可得到结果。

 

　　二、大数加法的实现

　　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("
");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