相關介紹: 在java中，整數是有最大上限的。所謂大數是指超過整數最大上限的數，例如18 452 543 389 943 209 789 324 233和8 123 534 323 432 323 432 123 212 443就是兩個大數，在java中這是無法用整型int變數或長整型l ...
相關介紹:
在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為例進行加法的計算過程。
對於兩個大數的加法，其操作步驟歸納如下:
- 將兩個加數的相應位從高位到低位依次壓入棧sA和sB中。
- 若兩個加數棧都非空，則依次從棧中彈出棧頂數字相加，和存入變數partialSum中，若和有進位，則將和的個位數壓入結果棧sum中，並將進位數加到下一位數字相加的和中，若和沒有進位，則直接將和壓入結果棧sum中
- 若某個加數堆棧為空，則將非空加數棧中的棧頂數字依次彈出與進位相加，和的個位數壓入結果棧sum中，直到此該棧為空為止，若最高位有進位，則最後將1壓入棧sum中
- 若兩個加數棧都為空，則棧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
