北大软设作业答案

大整数

题目描述

补全类 BigInt。它代表一个大整数，你可以通过 + 运算符对大整数做加法。

大整数应当以 C 风格字符串的形式存放在成员 data 所指向的内存中。我们已经为这个类实现了 和 来实现输入输出。

此外，我们提供了一些工具函数，可供你直接使用：

  1. int add(const char* a, const char* b, char* dest);，若 a 和 b 是存储整数的字符串，则将它们的和存放到 dest 指向的位置。dest 为空指针时，返回期望写入的字符个数（含末尾空字符）。
  2. int itoa(int a, char* dest);，将整数 a 转换到字符串，存储到 dest 中。dest 为空指针时，返回期望写入的字符个数（含末尾空字符）。

以上两个函数的典型使用方式是：

int size = add(a, b, nullptr);
char* buffer = new char[size];
add(a, b, buffer);
// 别忘记在合适的地方 delete[] buffer

 

关于输入

一行，共两个数。第一个数是大整数 a, 0 < a <= 10420000。第二个数 b 是 int 范围内的正整数。

关于输出

共七行。

第一行：a + b

第二行：a + b

第三行：a + b

第四行：2b + 10

第五行：2b + 12

第六行：2b + 12

第七行：2b + 13

核心技巧

  • operator= 只用定义复制赋值重载。其它所有你设想的重载，都可以通过转换构造函数导出的隐式转换，加上复制赋值来实现。如果复制赋值重载使用“复制-交换”手法，则可以让代码更简洁。
  • operator+ 只需实现为非成员的重载，且两个操作数都为 const BigInt&。其它所有你设想的重载，都可以通过隐式转换，转换到这个 operator+ 上。
  • operator+ 应当返回值而非引用。
  • operator+= 直接解释为 operator+ 和 operator= 的组合。
  • operator++ 直接调用 operator+=。注意前缀和后缀的返回值区别。

参考答案

#include <cstring>
#include <cstdio>
#include <iostream>
#include <utility>
using std::cin, std::cout, std::endl;

int add(const char* a, const char* b, char* dest);
int itoa(int a, char* dest);

class BigInt {
    char* data{};

public:
    BigInt(int n = 0) {
        int size = itoa(n, nullptr);
        data = new char[size];
        itoa(n, data);
    }
    BigInt(const char* n) {
        int size = std::strlen(n) + 1;
        data = new char[size];
        std::strcpy(data, n);
    }
    BigInt(const BigInt& other) : BigInt(other.data) {}

    BigInt& operator=(BigInt rhs) {
        std::swap(this->data, rhs.data);
        return *this;
    }

    BigInt& operator+=(const BigInt& rhs) {
        return *this = *this + rhs;
    }

    BigInt& operator++() {
        return *this += 1;
    }
    BigInt operator++(int) {
        BigInt result = *this;
        ++*this;
        return result;
    }

    friend BigInt operator+(const BigInt& lhs, const BigInt& rhs) {
        int size = add(lhs.data, rhs.data, nullptr);
        char* data = new char[size];
        add(lhs.data, rhs.data, data);
        BigInt result(data);
        delete[] data;
        return result;
    }
//
    ~BigInt() {
        delete[] data;
    }

    friend std::istream& operator>>(std::istream& in, BigInt& c);
    friend std::ostream& operator<<(std::ostream& out, const BigInt& c);
};

int main() {
    BigInt a(0), b("0");
    int n;

    cin >> a >> n;
    a = ("0" + a);
    b = n;

    cout << a + b << endl;
    cout << n + a << endl;
    cout << a + n << endl;

    cout << ((b += n) += "10") << endl;
    cout << ++++b << endl;
    cout << b++ << endl;
    cout << b << endl;
}

// 以下是工具函数的实现，不用关心。

#include <algorithm>
#include <iterator>
#include <memory>
#include <string>

int add(const char*a,const char*b,char*d){int
i=std::strlen(a),j=std::strlen(b),k{},c{};auto
r=std::make_unique<char[]>(std::max(i,j)+1);
auto f=[&](auto...a){int s=(...+a);r[k++]=s%
10+48,c=s/10;};while(i&&j)f(a[--i]-48,b[--j]
-48,c);while(i)f(a[--i]-48,c);while(j)f(b[--
j]-48,c);if(c)r[k++]=c+48;if(d)std::copy(&r[
0],&r[k],std::reverse_iterator{d+k}),d[k]=0;
return k+1;}int itoa(int a,char*dest){return
(dest?sprintf(dest,"%d",a):snprintf(nullptr,
0,"%d",a))+1;}std::istream&operator>>(std::
istream&i,BigInt&c){std::string s;i>>s;c=BigInt
(s.c_str());return i;}std::ostream&operator
<<(std::ostream&o,const BigInt&c){return o<<
c.data;}