一、大數加法的定義

　　在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("\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

轉載于:https://www.cnblogs.com/BigJunOba/p/9187814.html

總結

以上是生活随笔為你收集整理的数据结构（十）栈的作用--大数的加法运算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。