C++ 大整數相加實現：字符串模擬列豎式加法與棧逆序輸出

問題背景

內建類型 (long long ≤ 10¹⁸) 無法容納超大整數。解決方案：**字符串存儲數字，模擬人工豎式加法**，逐位相加處理進位。

算法流程

1. 讀入兩字符串 str1, str2。
2. 雙指針從**最低位 (字符串末尾)** 向最高位遍歷。
3. 對應位轉數值 (ch - '0') 相加 + 進位 carry。
4. 當前位 = sum % 10，新進位 = sum / 10。
5. 將當前位 **壓入棧** (或存入動態數組/字符串尾部)。
6. 處理完較長字符串剩餘位 + 進位。
7. 最終若 carry > 0 壓入棧。
8. 棧彈出輸出 → 正序結果。

完整代碼 (C++ STL)

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string str1, str2;
    while (cin >> str1 >> str2) { // 支持多組輸入
        stack st;
        int carry = 0;
        int i = str1.length() - 1;
        int j = str2.length() - 1;

        // 同時遍歷公共長度
        while (i >= 0 && j >= 0) {
            int sum = (str1[i] - '0') + (str2[j] - '0') + carry;
            st.push(sum % 10);
            carry = sum / 10;
            --i; --j;
        }
        // 處理剩餘長串
        while (i >= 0) {
            int sum = (str1[i] - '0') + carry;
            st.push(sum % 10);
            carry = sum / 10;
            --i;
        }
        while (j >= 0) {
            int sum = (str2[j] - '0') + carry;
            st.push(sum % 10);
            carry = sum / 10;
            --j;
        }
        // 最終進位
        if (carry) st.push(carry);

        // 輸出
        while (!st.empty()) {
            cout << st.top();
            st.pop();
        }
        cout << '\n';
    }
    return 0;
}

關鍵點解析

複雜度分析

• 時間：O(max(N, M))，單次遍歷。
• 空間：O(max(N, M))，棧存儲結果位。

進階優化方向

1. 基數優化：每位存 4 位十進制 (base=10000) 或 32 位 (base=2^32)，減少循環次數 4-9 倍 (大數乘法必備)。
2. 原地操作：結果直接寫入預分配的 string 或 vector 末尾，最後 reverse，省去棧開銷。
3. SIMD/多線程：超大數 (10⁶ 位+) 可分塊並行加法 + 進位傳播。