【数据结构与算法】大数加减

#include <bits/stdc++.h>
using namespace std;

struct BigNum {
    bool is_positive;
    vector<int> data; // 低位在前
    BigNum(string a) {
        if (!a.empty() && a[0] == '-') {
            is_positive = false;
            a = a.substr(1);
        } else {
            is_positive = true;
        }
        for (int i = (int)a.size() - 1; i >= 0; i--) {
            data.push_back(a[i] - '0');
        }
    }
};

string bignum_to_str(BigNum* res) {
    while (res->data.size() > 1 && res->data.back() == 0) {
        res->data.pop_back();
    }
    if (res->data.size() == 1 && res->data[0] == 0) return "0";

    string str;
    if (!res->is_positive) str += "-";
    for (int i = (int)res->data.size() - 1; i >= 0; i--) {
        str += char(res->data[i] + '0');
    }
    return str;
}

bool is_abs_bigger(BigNum* a, BigNum* b) {
    if (a->data.size() > b->data.size()) return true;
    if (a->data.size() < b->data.size()) return false;
    for (int i = (int)a->data.size() - 1; i >= 0; i--) {
        if (a->data[i] > b->data[i]) return true;
        if (a->data[i] < b->data[i]) return false;
    }
    return false; // 相等
}

// 只做 |a| - |b|，返回带符号的字符串
string sub(string a, string b) {
    BigNum* n1 = new BigNum(a);
    BigNum* n2 = new BigNum(b);
    BigNum* res = new BigNum("0");
    res->data.clear();

    bool neg = false;
    if (!is_abs_bigger(n1, n2)) {
        swap(n1, n2);
        neg = true; // 结果为负
    }

    int borrow = 0;
    for (size_t i = 0; i < n1->data.size(); i++) {
        int x = n1->data[i];
        int y = i < n2->data.size() ? n2->data[i] : 0;
        int z = x - y - borrow;
        if (z < 0) {
            z += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res->data.push_back(z);
    }

    string ans = bignum_to_str(res);
    if (ans != "0" && neg) ans = "-" + ans;
    return ans;
}

string add(string a, string b) {
    BigNum* n1 = new BigNum(a);
    BigNum* n2 = new BigNum(b);
    BigNum* res = new BigNum("0");
    res->data.clear();

    if (n1->is_positive == n2->is_positive) {
        // 同号直接相加
        res->is_positive = n1->is_positive;
        int carry = 0;
        for (size_t i = 0; i < n1->data.size() || i < n2->data.size() || carry; i++) {
            int x = i < n1->data.size() ? n1->data[i] : 0;
            int y = i < n2->data.size() ? n2->data[i] : 0;
            int sum = x + y + carry;
            res->data.push_back(sum % 10);
            carry = sum / 10;
        }
        return bignum_to_str(res);
    } else {
        // 异号 → 转成减法
        if (n1->is_positive) {
            return sub(a, b.substr(1)); // a + (-b) = a - |b|
        } else {
            return sub(b, a.substr(1)); // (-a) + b = b - |a|
        }
    }
}

int main() {
    string a, b;
    cin >> a >> b;
    string res = add(a, b);
    cout << res << endl;
    return 0;
}