添加整数字符串

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;
}