K：大數加法

相關介紹:

 在java中，整數是有最大上限的。所謂大數是指超過整數最大上限的數，例如18 452 543 389 943 209 789 324 233和8 123 534 323 432 323 432 123 212 443就是兩個大數，在java中這是無法用整型int變量或長整型long變量來進行儲存的，更不用說儲存他們之間相加的和了。為解決該問題，可以把兩個相加數看成是字元串，将這些數的相應數字存儲在兩個堆棧中，并從兩個棧中彈出對應位的數字依次執行加法可得到結果,以784和8465為例進行加法的計算過程。

對于兩個大數的加法，其操作步驟歸納如下:

1. 将兩個加數的相應位從高位到低位依次壓入棧sA和sB中。
2. 若兩個加數棧都非空，則依次從棧中彈出棧頂數字相加，和存入變量partialSum中，若和有進位，則将和的個位數壓入結果棧sum中，并将進位數加到下一位數字相加的和中，若和沒有進位，則直接将和壓入結果棧sum中
3. 若某個加數堆棧為空，則将非空加數棧中的棧頂數字依次彈出與進位相加，和的個位數壓入結果棧sum中，直到此該棧為空為止，若最高位有進位，則最後将1壓入棧sum中
4. 若兩個加數棧都為空，則棧sum中儲存的就是計算結果。注意棧頂是所得計算結果的最高位

其代碼如下:

package queueandstack;
import java.util.Stack;
/**
 * 該類用于示範大數加法的相關代碼
 * @author 學徒
 *
 */
public class BigNumberAdd
{
    /**
     * 求兩個大數的和，加數與被加數以字元串的形式輸入(允許大數中出現空格)，計算的結果也以字元串的形式傳回
     */
    public String add(String number1,String number2)throws Exception
    {
        Stack result=new Stack();//大數的和
        Stack number1Stack=numberSplit(number1);//加數字元串以單個字元的形式放入棧中
        Stack number2Stack=numberSplit(number2);//被加數字元串以單個字元的形式放入棧中
        int partialSum;//對于兩個位的求和
        boolean isCarry=false;//進位标志
        while(!number1Stack.isEmpty()&&!number2Stack.isEmpty())//加數和被加數棧同時非空
        {
            partialSum=(Integer)number1Stack.pop()+(Integer)number2Stack.pop();//對于兩個位進行求和，并在棧中去除掉加數和被加數中的該位
            //當有低位的進位時
            if(isCarry)
            {
                partialSum++;
                isCarry=false;
            }
            //需要進行進位
            if(partialSum>=10)
            {
                partialSum-=10;
                isCarry=true;
            }
            //将本位的結果放入結果棧中
            result.push(partialSum);
        }
        Stack temp=!number1Stack.isEmpty()?number1Stack:number2Stack;//将temp引用指向加數和被加數中非空棧
        while(!temp.isEmpty())
        {
            //當最後一次加法運算中存在進位的時候
            if(isCarry)
            {
                int t=(Integer)temp.pop();//取出其中的加數或者被加數中沒有參加的位
                ++t;//進位加到此位上
                if(t>=10)//當其需要進行進位的時候
                {
                    t-=10;
                }
                else//重置其進位标志
                {
                    isCarry=false;
                }
                result.push(t);
            }
            else//最後一次執行加法運算中不需要進位
            {
                result.push(temp.pop());//把加數或者被加數中非空的值放入和中
            }
        }
        if(isCarry)//将最高位加入到結果中
        {
            result.push(1);
        }
        String resultstr=new String();
        while(!result.isEmpty())
        {
            //把棧中的元素轉化為字元串
            resultstr=resultstr.concat(result.pop().toString());
        }
        return resultstr;
    }
    
    /**
     * 該方法用于将輸入的大數拆分成單個的字元，并去掉字元串中的空格，傳回以單個字元為元素的棧
     * 
     */
    public Stack numberSplit(String str)throws Exception
    {
        Stack result=new Stack();
        for(int i=0;i<str.length();i++)
        {
            char c=str.charAt(i);//指定索引處的char值
            if(' '==c)//去除掉空格
                continue;
            else if('0'<=c&&'9'>=c)//将數字放入棧中
                result.push(Integer.valueOf(String.valueOf(c)));
            else
                throw new Exception("錯誤:輸入了非數字型的字元!");
        }
        return result;
    }
    /**
     * 用于測試程式
     */
    public static void main(String[] args)throws Exception
    {
        BigNumberAdd a=new BigNumberAdd();
        System.out.println("兩個大數為:");
        System.out.println("1. 18 452 543 389 943 209 752 345 473");
        System.out.println("2. 8 123 542 678 432 986 899 334");
        System.out.println("其和為:");
        System.out.println(a.add("18 452 543 389 943 209 752 345 473", "8 123 542 678 432 986 899 334"));
    }
}


運作結果:
兩個大數為:
1. 18 452 543 389 943 209 752 345 473
2. 8 123 542 678 432 986 899 334
其和為:
18460666932621642739244807
           

回到目錄|·(工)·）

轉載于:https://www.cnblogs.com/MyStringIsNotNull/p/8206746.html