c++ - 添加整数字符串

Question

我正在尝试为一个更大的项目编写一个算法，该项目将采用两个都是大整数的字符串(为了这个演示只使用 10 位数字)并将它们加在一起以生成一个准确表示的最终字符串两个原始字符串的总和。我意识到可能有更好的方法可以从一开始就解决这个问题，但我应该专门使用大整数字符串而不是长整数。

我的想法是取两个原始字符串，将它们颠倒，以便它们的个位、十位等都正确对齐以便添加。然后一次一个位置，将字符串中的字符转换为单个整数并将它们加在一起，然后使用该总和作为个位或以其他方式作为最终字符串，一旦完成也将反转回正确的字符顺序.

我认为我遇到麻烦的地方是准备事件，在该事件中，字符串中相应位置的两个整数相加的总和大于 9，然后我会将一些余数转移到下一个位置。例如，如果我的个位上有 7 和 5 加起来就是 12，那么我会保留 2 并在十位循环后将 1 加到十位上。

我没有得到以任何方式准确的结果，并且在花费大量时间尝试纠正我的算法之后，我不确定我需要做什么来解决这个问题。

希望我的预期过程是明确的，并且有人能够为我指明正确的方向或纠正我的程序中可能存在的一些错误。

提前致谢。

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

int main()
{
    string str1 = "1234567890", str2 = "2345678901"; //Two original strings of large integers
    string rev_str1, rev_str2;
    int int1 = 0, int2 = 0;
    string final; //Final product string, sum of two original strings
    int temp_int = 0, buffer_int, remainder = 0;
    string temp_str = "", buffer_str;
    char buffer[100] = {0};

    cout << "str1 = " << str1 << endl;
    cout << endl;
    cout << "str2 = " << str2 << endl;
    cout << endl;

    rev_str1 = string(str1.rbegin(), str1.rend());
    rev_str2 = string(str2.rbegin(), str2.rend());

    for (int i = 0; i < 10; i++)
    {
        buffer_str = rev_str1.at(i);
        int1 = atoi(buffer_str.c_str());
        buffer_str = rev_str2.at(i);
        int2 = atoi(buffer_str.c_str());
        buffer_int += (int1 + int2 + remainder);
        remainder = 0;

        while (buffer_int > 9)
        {
            buffer_int -= 10;
            remainder += 10;
        }

        temp_str = itoa(buffer_int, buffer, 10);
        final += temp_str;
    }

    final = string(final.rbegin(), final.rend());

    cout << "final = " << final << endl;
    cout << endl;
}

Answer 1

这是我想出的。它仅适用于两次求和；如果你有更多，你将不得不稍微调整一下，特别是进位，它可以大于 19，以及结果字符串的分配方式:

#include <iostream>
#include <string>

using namespace std;

int main()
{
    // Two original strings of large integers
    string str1 = "1234567890",
           str2 = "2345678901234";

    // Zero-padd str1 and str2 to the same length
    size_t n = max(str1.size(), str2.size());
    if (n > str1.size())
        str1 = string(n-str1.size(), '0') + str1;
    if (n > str2.size())
        str2 = string(n-str2.size(), '0') + str2;

    // Final product string, sum of two original strings.
    // The sum of two integers has at most one digit more, for more inputs make
    // below reverse_iterator a back_insert_iterator, then reverse the result
    // and skip the removal of the padding.
    string final(n+1, '0');

    // The carry
    char carry = 0;

    // Iterators
    string::const_reverse_iterator s1 = str1.rbegin(), e = str1.rend(),
                                   s2 = str2.rbegin();
    string::reverse_iterator f = final.rbegin();

    // Conversion
    for (; s1 != e; ++s1, ++s2, ++f)
    {
        // Bracketing to avoid overflow
        char tmp = (*s1-'0')+(*s2-'0') + carry;
        if (tmp > 9)
        {
            carry = 1;
            tmp -= 10;
        }
        else
        {
            carry = 0;
        }
        *f = tmp + '0';
    }
    final[0] = carry + '0';

    // Remove leading zeros from result
    n = final.find_first_not_of("0");
    if (n != string::npos)
    {
        final = final.substr(n);
    }

    cout << "str1 = " << str1 << endl
         << "str2 = " << str2 << endl
         << "final = " << final << endl;
}