Multiply Strings

字符串乘法，有两个字符串表示的正数a、b，求乘积c，也用字符串表示。涉及字符串乘法、字符串加法。

class Solution

{

private:

char mul(char a, char b, char &carry)

{

int val = (a - '0') * (b - '0') + (carry - '0');

carry = '0' + val / 10;

return  '0' + val % 10;

}

char add(char a, char b, char &carry)

{

int val = (a - '0') + (b - '0') + (carry - '0');

carry = '0' + val / 10;

return  '0' + val % 10;

}

string addition(string num1, string num2)

{

string result(num1.size() > num2.size() ? num1.size() : num2.size(), '0');

string::const_reverse_iterator ita = num1.rbegin();

string::const_reverse_iterator itb = num2.rbegin();

string::reverse_iterator itc = result.rbegin();

char carry = '0';

while (ita != num1.rend() || itb != num2.rend())

{

const char a = ita == num1.rend() ?  '0' : *ita++;

const char b = itb == num2.rend() ? '0' : *itb++;

*itc++ = add(a, b, carry);

}

return carry == '0' ? result : carry + result;

}

public:

string multiply(string num1, string num2)

{

if (num1 == "0" || num2 == "0") return "0";

string lastNum;

for (string::const_reverse_iterator ita = num2.rbegin();

ita != num2.rend();

++ita)

{

string tmp(ita - num2.rbegin() + num1.size(), '0');

string::reverse_iterator itc = tmp.rbegin() + (ita - num2.rbegin());

char carry = '0';

for (string::const_reverse_iterator itb = num1.rbegin();

itb != num1.rend();

++itb)

{

*itc++ = mul(*ita, *itb, carry);

}

if (carry != '0')

{

tmp = carry + tmp;

}

lastNum = addition(lastNum, tmp);

}

return lastNum;

}

};

原文链接: https://www.cnblogs.com/codingmylife/archive/2012/09/27/2705518.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍