/****************************************************************************
 FileName     [ largeNum.cpp ]
 PackageName  [ addlargeNum ]
 Synopsis     [ Define main() function ]
 Author       [ (Jacky) Chang ]
 ****************************************************************************/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstring>

using namespace std;

bool enterNum(vector<char> &, short &);
void addSum(vector<char> &, vector<char> &, const short, const short);
int  compare(const vector<char>, const vector<char>);

int main()
{
    vector<char>    num_x;
    vector<char>    num_y;
    //---------------------------
    // +1:positive, -1:negative
    //---------------------------
    short            signed_x = 1;
    short            signed_y = 1;

    bool   INPUTVALID = 0;

    cout << "Please enter first number:" << endl;
    INPUTVALID = enterNum(num_x, signed_x);

    if ( INPUTVALID )
    {
        cout << "Please enter second number:" << endl;
        INPUTVALID = enterNum(num_y, signed_y);
    }

    if (INPUTVALID)
        addSum(num_x, num_y, signed_x, signed_y);

    return 0;
}

//--------------------------------------------------------
//     Function: read input from user keyboard.
//--------------------------------------------------------
bool enterNum(vector<char>& num, short& signedbit)
{
    bool            is_First = 1;
    bool            is_Valid = 1;
    char            input = 0;

    while (1)
    {
        input = cin.get();

        if ( input == '\n' )
            break;
        else if ( input < 48 || input > 57 )
        {
            if ( is_First == 1 && input == 45)
                ;
            else
            {
                is_Valid = 0;
                break;
            }
        }
        else
        {
            num.push_back(input);
        }

        if ( input == '0' && num.size() == 1 )
        {
            is_Valid = 0;
            break;
        }

        if (is_First)
        {
            if ( input == 45 )
            {
                signedbit = -1;
            }
            else if ( input == '0' && num.size() != 1 )
            {
                is_Valid = 0;
                break;
            }
            is_First = 0;
        }
    }

    if (is_Valid)
        return 1;
    else
    {
        cout << "Invalid input!!" << endl;
        return 0;
    }
}

//--------------------------------------------------------
//     Function: add two number and print the result.
//--------------------------------------------------------
void addSum(vector<char>& num_x, vector<char>& num_y, const short signed_x, const short signed_y)
{
    int ii = num_x.size() - 1;
    int jj = num_y.size() - 1;
    int over = 0;
    int tmp = 0;
    int borrow = 0;
    bool has_Negative = 0;
    vector<char> result;

    //-------------------------------------------------------
    // case 1: num_x > 0, num_y < 0
    //      (a) |num_x| > |num_y|
    //      (b) |num_x| < |num_y|
    // case 2: num_x < 0, num_y > 0
    //      (a) |num_x| > |num_y|
    //      (a) |num_x| < |num_y|
    // case 3: num_x > 0, num_y > 0 || num_x < 0, num_y < 0
    //-------------------------------------------------------

    while (1)
    {
        if ( signed_x == 1 && signed_y == -1 )
        {
            if ( compare(num_x, num_y) == 1 )
            {
                if ( ii >= 0 && jj >= 0)
                    tmp = (num_x[ii]-48) - (num_y[jj]-48) - borrow;
                else if ( ii >= 0 && jj < 0 )
                    tmp = (num_x[ii]-48) - borrow;
                else
                    break;

                if ( tmp < 0 )
                {
                    tmp = tmp + 10;
                    borrow = 1;
                }
                else
                    borrow = 0;

                result.push_back(tmp%10+48);
            }
            else if ( compare(num_x, num_y) == -1 )
            {
                if ( ii >= 0 && jj >= 0)
                    tmp = (num_y[jj]-48) - (num_x[ii]-48) - borrow;
                else if ( ii < 0 && jj >= 0)
                    tmp = (num_y[jj]-48) - borrow;
                else
                    break;

                if ( tmp < 0 )
                {
                    tmp = tmp + 10;
                    borrow = 1;
                }
                else
                    borrow = 0;

                result.push_back(tmp%10+48);
                has_Negative = 1;
            }
            else if ( compare(num_x, num_y) == 0 )
            {
                result.push_back(48);
                break;
            }
        }
        else if ( signed_x == -1 && signed_y == 1 )
        {
            if ( compare(num_x, num_y) == 1 )
            {
                if ( ii >= 0 && jj >= 0)
                    tmp = (num_x[ii]-48) - (num_y[jj]-48) - borrow;
                else if ( ii >= 0 && jj < 0 )
                    tmp = (num_x[ii]-48) - borrow;
                else
                    break;

                if ( tmp < 0 )
                {
                    tmp = tmp + 10;
                    borrow = 1;
                }
                else
                    borrow = 0;
                result.push_back(tmp%10+48);
                has_Negative = 1;
            }
            else if ( compare(num_x, num_y) == -1 )
            {
                if ( ii >= 0 && jj >= 0)
                    tmp = (num_y[jj]-48) - (num_x[ii]-48) - borrow;
                else if ( ii < 0 && jj >= 0)
                    tmp = (num_y[jj]-48) - borrow;
                else
                    break;

                if ( tmp < 0 )
                {
                    tmp = tmp + 10;
                    borrow = 1;
                }
                else
                    borrow = 0;

                result.push_back(tmp%10+48);
            }
            else if ( compare(num_x, num_y) == 0 )
            {
                result.push_back(48);
                break;
            }
        }
        else
        {
            if ( ii >= 0 && jj >= 0 )
                tmp = (num_x[ii]-48) + (num_y[jj]-48) + over;
            else if ( ii >= 0 && jj < 0 )
                tmp = (num_x[ii]-48) + over;
            else if ( ii < 0 && jj >= 0 )
                tmp = (num_y[jj]-48) + over;
            else
                break;

            if ( tmp > 9 )
            {
                result.push_back(tmp%10+48);
                over = tmp/10;
            }
            else
            {
                result.push_back(tmp+48);
                over = 0;
            }

        }
        --ii; --jj;
    }

    reverse(result.begin(), result.end());

    if ( signed_x == -1 && signed_y == -1 )
        has_Negative = 1;

    if ( has_Negative )
        cout << "-";

    if ( over != 0 )
        cout << over;

    cout << "The sum is:" << endl;
    for (unsigned short loop = 0; loop < result.size(); ++loop)
        cout << result[loop];
    cout << endl;
}

//--------------------------------------------------------
//     Function: compare the value of two numbers.
//     Output  : 1: a>b, 0: a=b, -1: a<b.
//--------------------------------------------------------
int compare(const vector<char> num_x, const vector<char> num_y)
{
    int loop = 0;
    if ( num_x.size() > num_y.size() )
        return 1;
    else if ( num_x.size() < num_y.size() )
        return -1;
    else
    {
        while (1)
        {
            if ( num_x[loop] > num_y[loop] )
                return 1;
            else if ( num_x[loop] < num_y[loop] )
                return -1;
            else if ( num_x[loop] == num_y[loop] )
            {
                if ( loop == num_x.size() )
                    return 0;
            }
            ++loop;
        }
    }
}