Java 基於棧的大整數加法算法實作

前言

Java 基本型別 int/long 有上限，超大整數無法直接運算。本文利用字串儲存數字、棧倒序存放數位、逐位相加進位，實現任意長度整數加法。

算法原理

1. 將兩數字串逐字元推入各自棧（低位在棧頂）。
2. 迴圈彈出兩棧頂數位相加 + 進位 carry (0 或 1)。
3. 結果個位推入結果棧，十位作為新 carry。
4. 一棧空後，將另棧剩餘數位 + carry 繼續處理。
5. 最終若 carry=1 再推入 1。
6. 彈出結果棧即為正序和。

棧實作

public class IntStack {
    private LinkedList<Integer> storage = new LinkedList<>();
    public void push(int v) { storage.addFirst(v); }
    public int pop() { return storage.removeFirst(); }
    public boolean empty() { return storage.isEmpty(); }
}

加法運算類

public class StackOper {
    private IntStack oper1, oper2, result;
    private String s1, s2;

    public StackOper(IntStack s1, IntStack s2) {
        this.oper1=s1; this.oper2=s2; result=new IntStack();
    }

    public void pushNum(String n1, String n2) {
        this.s1=n1; this.s2=n2;
        push(n1, oper1); push(n2, oper2);
    }
    private void push(String s, IntStack st) {
        for (char ch : s.toCharArray()) {
            if (ch>='0' && ch<='9') st.push(ch - '0');
            else throw new IllegalArgumentException("Non-digit");
        }
    }

    public void add() {
        int carry = 0;
        // 兩棧皆非空
        while (!oper1.empty() && !oper2.empty()) {
            int sum = oper1.pop() + oper2.pop() + carry;
            result.push(sum % 10);
            carry = sum / 10;
        }
        // 處理剩餘棧
        IntStack rem = oper1.empty() ? oper2 : oper1;
        while (!rem.empty()) {
            int sum = rem.pop() + carry;
            result.push(sum % 10);
            carry = sum / 10;
        }
        // 最終進位
        if (carry == 1) result.push(1);
    }

    public void printResult() {
        System.out.println("Operator1: " + s1);
        System.out.println("Operator2: " + s2);
        System.out.print("Result : ");
        while (!result.empty()) System.out.print(result.pop());
        System.out.println();
    }

    public static void main(String[] args) {
        StackOper so = new StackOper(new IntStack(), new IntStack());
        so.pushNum("1313", "19");
        so.add(); so.printResult();
        // 輸出: 1332
    }
}

擴展思路

• 減法：大減小，逐位相減借位。
• 乘法：模擬豎式乘法，中間結果位移累加（雙重迴圈）。
• 除法：試商法，高位向低位遞減。
• BigInteger：生產環境請直接使用 java.math.BigInteger，已高度優化。

總結

棧的「後進先出」特性完美匹配「從低位向高位」的手算邏輯。此實作展示了數據結構如何服務於算法設計，是理解大數運算原理的優秀教學範例。