[알고리즘 스터디] 2주차_스택_코드업 3021

문제

int는 32비트, long long 은 64비트라서 이 보다 더 큰 숫자는 저장할 수 없다.
아주 큰 숫자의 덧셈을 하려고 한다.
계산 결과를 출력하시오.

입력

첫째줄과 둘째줄에 큰 수 a, b가 입력된다. (a, b는 100자리 이하의 정수)

출력

큰 수 덧셈의 결과를 출력한다.

코드

#include <iostream>

using namespace std;

enum { eMaxCount = 100001, eInvalid = -1 };

class Stack
{
public:
    Stack()
        : muTopIndex(0u)
        , StackSize(0)
    {
    }

    void Push(int _iData)
    {
        if (eMaxCount <= muTopIndex)
        {
            cout << "Stack overflow!" << endl;
            return;
        }

        StackSize++;
        miarrData[muTopIndex++] = _iData;
    }

    bool IsEmpty(void)
    {
        return -1 == muTopIndex;
    }

    int Size()
    {
        return StackSize;
    }

    int Top(void)
    {
        if (true == IsEmpty())
        {
            cout << "Stack underflow!" << endl;
            return eInvalid;
        }

        return miarrData[muTopIndex];
    }

    void Pop(void)
    {
        if (true == IsEmpty())
        {
            cout << "Stack underflow!" << endl;
            return;
        }

        StackSize--;
        muTopIndex--;
    }

private:
    int             miarrData[eMaxCount];
    unsigned int    muTopIndex;
    int             StackSize;
};

void Recursive(Stack* _StackA, Stack* _StackB, Stack* _StackC, bool IsOverTen)
{
    if (true == _StackA->IsEmpty() && true == _StackB->IsEmpty())
    {
        if (IsOverTen == true)
        {
			_StackC->Push(1);
		}
		return;
	}
	else if (true == _StackA->IsEmpty())
	{
        if (_StackB->Top() + IsOverTen < 10)
        {
			_StackC->Push(_StackB->Top() + IsOverTen);
			_StackB->Pop();
			IsOverTen = false;
			Recursive(_StackA, _StackB, _StackC, IsOverTen);
        }
        else
        {
            _StackC->Push(_StackB->Top() + IsOverTen - 10);
            IsOverTen = true;
            _StackB->Pop();
            Recursive(_StackA, _StackB, _StackC, IsOverTen);
        }
	}
	else if (true == _StackB->IsEmpty())
	{
        if (_StackA->Top() + IsOverTen < 10)
        {
            _StackC->Push(_StackA->Top() + IsOverTen);
            _StackA->Pop();
            IsOverTen = false;
            Recursive(_StackA, _StackB, _StackC, IsOverTen);
        }
        else
        {
            _StackC->Push(_StackA->Top() + IsOverTen - 10);
            IsOverTen = true;
            _StackA->Pop();
            Recursive(_StackA, _StackB, _StackC, IsOverTen);
        }
	}
	else // 둘다 empty가 아니면
	{
		int Sum = _StackA->Top() + _StackB->Top();
		if (Sum >= 10 || Sum + IsOverTen >= 10)
		{
			_StackC->Push(Sum - 10 + IsOverTen);
            IsOverTen = true;
            _StackA->Pop();
            _StackB->Pop();
            Recursive(_StackA, _StackB, _StackC, IsOverTen);
        }
        else
        {
            _StackC->Push(Sum + IsOverTen);
            IsOverTen = false;
            _StackA->Pop();
            _StackB->Pop();
            Recursive(_StackA, _StackB, _StackC, IsOverTen);
        }
    }
}

int main(void)
{
    Stack* StackA = new Stack();
    Stack* StackB = new Stack();
    Stack* StackC = new Stack();
    Stack* StackD = new Stack();

    char CharA[100] = { 0, };
    char CharB[100] = { 0, };

    std::cin >> CharA;
    std::cin >> CharB;

    for (int i = 0; i < 100; i++)
    {
        if (CharA[i] != '\0')
        {
            StackA->Push(CharA[i] - '0');
        }

        if (CharB[i] != '\0')
        {
            StackB->Push(CharB[i] - '0');
        }
    }

    StackA->Pop();
    StackB->Pop();

    Recursive(StackA, StackB, StackC, false);

    StackC->Pop();

    while (false == StackC->IsEmpty())
    {
        std::cout << StackC->Top();
        StackC->Pop();
    }
}