大数加法【Java实现】

Java大数加法运算

1. 将两个加法的相应位从高位到低位依次压入栈stackA和stackB中，结果栈stackSum用来存放最终和

2. 如果两个栈非空，则依次从栈中弹出栈顶数字相加，和存入临时变量tempSum中。若和有进位，则将个位数压入结果压入结果栈stackSum，并标志进位isCarry为true，以便将进位数加入到下次数字和中；若无进位，则直接将和压入结果栈stackSum；

3. 步骤2后如果有栈非空（即两个加数位数不同），则依次弹出非空栈stackTemp的栈顶数字。若有进位则与进位数相加，将和个位数压栈；若无则直接压栈

4. 如果最高位有进位，则最后将数字1入栈

5. 打印结果栈stackSum中数字，得到结果和

public class LargeNumberCalculate {
    // 把字符串以字符形式放进栈中
    public Stack<Integer> stringToStack(String str) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c >= '0' && c <= '9')
                stack.push(Integer.valueOf(String.valueOf(c)));
            else
                continue;
        }
        return stack;
    }

    // 大数相加
    public String add(String a, String b) {
        Stack<Integer> stackA = stringToStack(a); // 存放第一个数
        Stack<Integer> stackB = stringToStack(b); // 存放第二个数
        Stack<Integer> stackSum = new Stack<>(); // 存放结果和
        int tempSum; // 两位数求和
        boolean isCarry = false; // 进位标志

        while (!stackA.isEmpty() && !stackB.isEmpty()) {
            tempSum = (Integer) stackA.pop() + (Integer) stackB.pop();
            // 若有进位，加1
            if (isCarry) {
                tempSum++;
                isCarry = false;
            }
            // 位数和大于10，个位数入栈，标志进位
            if (tempSum >= 10) {
                tempSum -= 10;
                stackSum.push(tempSum);
                isCarry = true;
            } else {
                stackSum.push(tempSum);
            }
        }
        // 取不为空的栈
        Stack<Integer> stackTemp = !stackA.isEmpty() ? stackA : stackB;
        while (!stackTemp.isEmpty()) {
            // 若原先有进位
            if (isCarry) {
                int end = (Integer) stackTemp.pop(); // 取出栈中的数
                ++end;
                if (end >= 10) // 大于10，进位
                {
                    end -= 10;
                    stackSum.push(end);
                } else // 小于10，直接入栈
                {
                    stackSum.push(end);
                    isCarry = false;
                }
            }
            // 若原先无进位
            else {
                stackSum.push(stackTemp.pop());
            }
        }
        // 最高位有进位时,直接最后一个数为1
        if (isCarry)
            stackSum.push(1);
        // 把栈中结果转为字符串
        String result = new String();
        while (!stackSum.isEmpty()) {
            result = result.concat(stackSum.pop().toString());
        }
        return result;
    }

    public static void main(String[] args) {
        LargeNumberCalculate largeCalculate = new LargeNumberCalculate();
        // String a = "159";
        // String b = "73";
        String a = "6 293 379 654 943 111 722 643 403";
        String b = "1 523 502 388 432 201 489 337 78";
        System.out.println("和为: " + largeCalculate.add(a, b));
    }

}