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