Java實現基於棧實現整數加法算法

整數是有最大上限的,如果整數超出最大上限位數,如 4398912120931092319+49832232849329019019210921029,此時整型變量無法保存這些數字.解 決的辦法是,可利用字符串保存這些數字,再利用棧做按位加法.

1.用Java實現,首先使用鏈表LinkedList構造棧數據結構.

import java.util.LinkedList;
public class IntStack {
　　 private LinkedList<Integer> storage = new LinkedList<Integer> ();
　　 /** 入棧 */
　　 public void push(int v) {
　　　　 storage.addFirst(v);
　　 }
　　 /** 出棧，但不刪除 */
　　 public int peek() {
　　　　 return storage.getFirst();
　　 }
　　 /** 出棧 */
　　 public int pop() {
　　　　 return storage.removeFirst();
　　 }
　　 /** 棧是否為空 */
　　 public boolean empty() {
　　　　 return storage.isEmpty();
　　 }
　　 /** 打印棧元素 */
　　 public String toString() {
　　　　 return storage.toString();
　　 }
}

2.使用棧加法操作.

2.1棧oper1和棧oper2分別保存兩個加數,棧result保存結果;

2.2方法pushNum(String soper1, String soper2)將兩個數字字符串分別保存於兩個棧中 ;

2.3方法add()進行加法操作,具體算法是:

[1]整型變量addition保存一個十位值,只能取值0或1,兩個9相加為18;

[2]循環從兩個棧中取數據,將相加的結果的個位值保存於棧result,十位值保存於整型變 量addition;

[3]整型變量addition初始值為0,每次要參與下一輪運算;

[4]當某加數棧(棧oper1或棧oper2)為空後,直接將另一個棧的數據復制到棧result;

2.4 測試,執行程序輸出:

Operator1:1313
Operator2:19
Result　 :1332
public class StackOper {
　　 private IntStack oper1;
　　 private IntStack oper2;
　　 private IntStack result;
　　 private String soper1;
　　 private String soper2;
　　 public StackOper(IntStack stack1, IntStack stack2) {
　　　　 oper1 = stack1;
　　　　 oper2 = stack2;
　　　　 result = new IntStack();
　　 }
　　 public void pushNum(String soper1, String soper2) {
　　　　 this.soper1 = soper1;
　　　　 this.soper2 = soper2;
　　　　 push(soper1, oper1);
　　　　 push(soper2, oper2);
　　 }
　　 private void push(String s, IntStack stack) {
　　　　 char num[] = s.toCharArray();
　　　　 for (int i = 0; i < num.length; i++) {
　　　　　　 if (num[i] <= 57 && num[i] >= 48)
　　　　　　　　 stack.push(num[i] - 48);
　　　　　　 else
　　　　　　　　 throw new UnsupportedOperationException("Not Digital");
　　　　 }
　　 }
　　 public void add() {
　　　　 int addition = 0;
　　　　 while (!oper1.empty()　&& !oper2.empty()) {
　　　　　　 int sum = oper1.pop() + oper2.pop() + addition;
　　　　　　 if (sum < 10) {
　　　　　　　　 result.push(sum);
　　　　　　　　 addition = 0;
　　　　　　 } else {
　　　　　　　　 result.push(sum - 10);
　　　　　　　　 addition = 1;
　　　　　　 }
　　　　 }
　　　　 while (addition == 1) {
　　　　　　 if (!oper1.empty()){
　　　　　　　　 int sum = oper1.pop() + addition;
　　　　　　　　 if (sum < 10) {
　　　　　　　　　　 result.push(sum);
　　　　　　　　　　 addition = 0;
　　　　　　　　 } else {
　　　　　　　　　　 result.push(sum - 10);
　　　　　　　　　　 addition = 1;
　　　　　　　　 }
　　　　　　 }else if (!oper2.empty()){
　　　　　　　　 int sum = oper2.pop() + addition;
　　　　　　　　 if (sum < 10) {
　　　　　　　　　　 result.push(sum);
　　　　　　　　　　 addition = 0;
　　　　　　　　 } else {
　　　　　　　　　　 result.push(sum - 10);
　　　　　　　　　　 addition = 1;
　　　　　　　　 }
　　　　　　 }else {
　　　　　　　　 result.push(1);
　　　　　　　　 addition = 0;
　　　　　　 }
　　　　 }
　　　　 while (!oper1.empty())
　　　　　　 result.push(oper1.pop());
　　　　 while (!oper2.empty())
　　　　　　 result.push(oper2.pop());
　　 }
　　 public void printResult() {
　　　　 System.out.print("Operator1:" + soper1 + '\n');
　　　　 System.out.print("Operator2:" + soper2 + '\n');
　　　　 System.out.print("Result　 :");
　　　　 while (result.empty() == false)
　　　　　　 System.out.print(result.pop());
　　　　 System.out.println();
　　 }
　　 public static void main(String[] args) {
　　　　 IntStack int1 = new IntStack();
　　　　 IntStack int2 = new IntStack();
　　　　 StackOper so = new StackOper(int1, int2);
　　　　 so.pushNum("1313", "19");
　　　　 so.add();
　　　　 so.printResult();
　　 }
}