#include<iostream.h>
#include<string.h>

////////Примерна реализация на дълги числа посредством низове///////////////////

//Представеният по-долу код не е най-оптималният вариант за реализация на дълги числа.
//Може да се направят много оптимизации и подобрения на функционалността.
//Например, с малко усилие, може да се реализира работа и с отрицателни числа,
//с дробни числа; да се напише функция за делене и т.н...



//Преди да започнем със същината, една помощна функция, която ще използваме;)
unsigned long max(unsigned long a, unsigned long b)
{
	return (a>b)? a:b;
}




//Понеже ще работим с дълги	числа а не просто с низове, добре би било
//да разглеждаме дългите числа като отделен тип данни.
typedef char* longNumber;




//Ще използваме динамично заделяне на памет, и затова е добре е да си направим две функции,
//едната от които да се грижи за заделянето на необходимата памет,
//а другата - за освобождаването.


//		longNumber CreateLong( const char * = "0" );

//Тази функция заделя необходимата памет за числото представено в низа str
//и връща това число като резултат от тип longNumber,
//като прави проверка за валидност. Подразбиращата се стойност е 0.


longNumber CreateLong(const char* str = "0")
{
	unsigned long length = strlen(str);
	char check; //временна променлива, която ще използваме в проверката за валидност

	//при некоректна стойност на str ще връщаме числото 0
	if (str == NULL || length == 0)
	{
		longNumber result = new char[2];
		result[0] = '0';
		result[1] = '\0';
		return result;
	}

	unsigned long indexCounter;
	for (indexCounter = 0; indexCounter < length; indexCounter++)
	{
		check = str[indexCounter];
		if(check < '0' || check > '9')
		{
			//ако има символ, който не е цифра връщаме числото 0
			longNumber result = new char[2];
			result[0] = '0';
			result[1] = '\0';
			return result;
		}
	}

	//ако сме стигнали дотук, значи низа str е коректен и остава да го запишем
	//според логиката ни на представяне (отзад напред)
	longNumber result = new char[length + 1]; //заделяме необходимата памет
	for (indexCounter = 0; indexCounter < length; indexCounter++)
	{
		result[indexCounter] = str[length-1-indexCounter]; //копираме низа в обратен ред
	}
	result[indexCounter] = '\0'; //да не забравяме индикатора за край!

	while (result[--indexCounter] == '0')
	{
		if (indexCounter == 0)
		{
			break; // трябва да предвидим и числото 0
		}
	}
	result[indexCounter+1] = '\0'; //поставяме края на низа на новата позиция

	return result;
}
//Вижда се че горната функция винаги ще върне като резултат коректно
//дълго число. Тогава, ако използваме само нея за създаване на дълги
//числа, няма да има нужда да правим проверки за коректност при
//функциите за работа с дълги числа, които ще дефинираме по-долу.





//		void destroyLong( longNumber & );

//Тази функция освобождава паметта, заета от аргумента от тип longNumber &.


void destroyLong(longNumber & lnum)
{
	delete lnum;
	lnum = NULL; 
	//хубаво е когато работим с указатели да сме наясно със стойността им,
	//т.е. когато не сочат към нищо е добра практика да се нулират.
	//Така ако се опитаме да използваме lnum след извикването на destroyLong
	//ще възникне грешка. 
}





//		void add( const longNumber & , const longNumber & , longNumber & );

//Тази функция извършва събиране на числата представени в първите два аргумента
//и записва получения резултат в третия аргумент. Ако преди това в него е
//имало някаква стойност тя се изтрива и вместо нея се записва новата.


void add(const longNumber& longNum1, const longNumber& longNum2, longNumber & result)
{
	//Следващият блок проверява за стойности NULL първите два аргумента,
	//защото това означава че функцията add е извикана за вече унищожени
	//"обекти" от тип longNum. Това е грешка, която можем да обработим по различни
	//начини, според предпочитанията и логиката на програмата. Тук например
	//"унищожаваме" числото в result (задаваме стойност NULL) и изкарваме
	//съобщение в потока за грешки cerr (който стандартно е свързан с екрана);
	if (longNum1 == NULL || longNum2 == NULL)
	{
		delete result;
		result = NULL;
		cerr << "Error in addition of longNumbers at " << &longNum1 << " and " << &longNum2<<endl;
		return;
	}
	
	unsigned long int length1 = strlen(longNum1), length2 = strlen(longNum2);
	
	delete result;
	//крайният резултат ще бъде максимум с една цифра по-дълъг от max(length1, length2)
	//и затова заделяме памет за length + 2 символа (последният e крайният - '\0');
	result = new char[max(length1, length2)+2]; 
	
	//short countAdd - променлива, в която записваме колко "наум" имаме при текущото пресмятане;
	//short tempDigit - променлива, в която записваме текущо пресметнатата цифра;
	short countAdd = 0, tempDigit = 0;
	unsigned long int indexCounter = 0;
	
	//първоначално обхождаме двете числа паралелно, докато стигнем до края на по-късото;
	while (longNum1[indexCounter] != '\0' && longNum2[indexCounter] != '\0')
	{
		tempDigit = (longNum1[indexCounter] - '0') + (longNum2[indexCounter] - '0') + countAdd;
		if (tempDigit > 9)
		{
			tempDigit = tempDigit - 10;
			countAdd = 1;
		}
		else
		{
			countAdd = 0;
		}
		result[indexCounter] = (char)tempDigit + '0';
		indexCounter++;
	}

	//ако първото е било по-късо, дообхождаме второто;
	if (longNum1[indexCounter] == '\0')
	{
		while (longNum2[indexCounter] != '\0')
		{
			tempDigit = (longNum2[indexCounter] - '0') + countAdd;
			if (tempDigit > 9)
			{
				tempDigit = tempDigit - 10; countAdd = 1;
			}
			else
			{
				countAdd = 0;
			}
			result[indexCounter] = (char)tempDigit + '0';
			indexCounter++;
		}
	}
	//ако второто е било по-късо дообхождаме първото;
	else if (longNum2[indexCounter] == '\0')
	{
		while (longNum1[indexCounter] != '\0')
		{
			tempDigit = (longNum1[indexCounter] - '0') + countAdd;
			if (tempDigit > 9)
			{
				tempDigit = tempDigit - 10; countAdd = 1;
			}
			else
			{
				countAdd = 0;
			}
			result[indexCounter] = (char)tempDigit + '0';
			indexCounter++;
		}
	}
	
	//ако ни е останало 1 "наум" след пълното обхождане на числата трябва
	//да го добавим към резултата;
	if (countAdd == 1)
	{
		result[indexCounter] = '1';
		indexCounter++;
	}

	result[indexCounter] = '\0'; //остава да поставим индикатора за край;
}





//		void subtract( const longNumber & , const longNumber & , longNumber & );

//Тази функция извършва изваждане на числото представено във втория аргумент от числото
//представено в първия и записва получения резултат в третия аргумент. Ако преди това в
//него е имало някаква стойност тя се изтрива и вместо нея се записва новата.


void subtract(const longNumber& longNum1, const longNumber& longNum2, longNumber & result)
{
	
	//Тук правим проверка за "несъществуващи" аргументи, аналогична на проверката
	//във функцията add;
	if (longNum1 == NULL || longNum2 == NULL)
	{
		delete result;
		result = NULL;
		cerr << "Error in subtraction of longNumber at " << &longNum2
			 << " from longNumber at " << &longNum2<<endl;
		return;
	}
	
	unsigned long int length1 = strlen(longNum1), length2 = strlen(longNum2);
	
	delete result;
	result = new char[max(length1, length2)+2];

	//short countSub - променлива, в която записваме колко сме "взели" от предната
	//цифра на умаляемото;
	//short tempDigit - променлива, в която записваме текущо пресметнатата цифра;
	short countSub = 0, tempDigit = 0;
	unsigned long int indexCounter = 0;

	//тъй като не разглеждаме отрицателни числа ще считаме, че умаляемото е >= на умалителя;
	//обхождаме паралелно двете числа, докато достигнем до края на умалителя
	while(longNum2[indexCounter] != '\0')
	{
		tempDigit = (longNum1[indexCounter] - '0') - (longNum2[indexCounter] - '0') - countSub;
		if (tempDigit < 0)
		{
			tempDigit += 10;
			countSub = 1;
		}
		else
		{
			countSub = 0;
		}
		result[indexCounter] = tempDigit + '0';
		indexCounter++;
	}

	//продължаваме обхождането, докато достигнем до края на умаляемото
	while (longNum1[indexCounter] != '\0')
	{
		tempDigit = (longNum1[indexCounter] - '0') - countSub;
		if (tempDigit < 0)
		{
			tempDigit += 10;
			countSub = 1;
		}
		else
		{
			countSub = 0;
		}
		result[indexCounter] = tempDigit + '0';
		indexCounter++;
	}

	result[indexCounter] = '\0'; //не трябва да забравяме символа за край на низ
	
	//може обаче да се получи резултат, който съдържа нули в началото;
	//например 10000-9999=00001;
	//остава да се отървем от тези нули, които в нашето представяне са на края на низа,
	//като преместим символа за край на низ;
	while (result[--indexCounter] == '0')
	{
		if (indexCounter == 0)
		{
			break; // ако резултата от изваждането е 0 то трябва да имаме поне една цифра
		}
	}
	result[indexCounter+1] = '\0'; //поставяме края на низа на новата позиция
}





//		void multiplyDigitLong ( unsigned short digit, const longNumber & longNum, longNumber & result);

//Тази функция умножава цялото число в digit с числото представено в longNum и запазва 
//резултата в result. Ако преди това в result е имало някаква стойност тя се изтрива
//и вместо нея се записва новата.
//Счита се, че digit е число в интервала [0-10]. Ако е извън него при умножението
//се взема последната му цифра.

void multiplyDigitLong(unsigned short digit, const longNumber & longNum, longNumber & result)
{
	//отново правим проверка за "несъществуващи" аргументи;
	if(longNum == NULL)
	{
		delete result;
		result = NULL;
		cerr << "Error in multiplication of longNumber at " << &longNum << " by " << digit <<endl;
		return;
	}

	//коригираме стойността на входния аргумент digit ( да е в [0-10])
	if (digit>10)
	{
		digit%=10;
	}

	long int length = strlen(longNum);
	delete result;
	//крайният резултат ще бъде максимум с една цифра по-дълъг от longNum
	//и затова заделяме памет за length + 2 символа (последният e крайният - '\0');
	result = new char[length + 2];

	//short countMult - променлива, в която записваме колко "наум" имаме при текущото смятане
	//short tempDigit - променлива, в която записваме текущо пресметнатата цифра;
	short countMult = 0, tempDigit = 0;
	unsigned long indexCounter = 0;
	
	//обхождаме числото и умножаваме всяка цифра с digt по познатия ни начин
	while(longNum[indexCounter] != '\0')
	{
		tempDigit = (longNum[indexCounter] - '0') * digit + countMult;
		result[indexCounter] = tempDigit%10 + '0';
		countMult = tempDigit/10;
		indexCounter++;
	}

	//ако имаме нещо останало "наум" го добавяме
	if (countMult != 0)
	{
		result[indexCounter] = countMult + '0';
		indexCounter++;
	}

	result[indexCounter] = '\0';

	//при умножение с 0 ще се получи резултат 000...0, затова коригираме нулите
	while (result[--indexCounter] == '0')
	{
		if (indexCounter == 0)
		{
			break; // трябва да имаме поне една цифра
		}
	}
	result[indexCounter+1] = '\0'; //поставяме края на низа на новата позиция

}
//Тази функция може да се използва при реализиране на умножение на две дълги числа.
//Преимущество е че тя поддържа и умножение с 10.





//		void printLong( const longNumber & , char = ' ');

// Тази функция извежда на екрана числото записано в аргумента от тип longNumber,
//като групира цифрите със знака зададен като втори аргумент.
//По подразбиране това е интервал.


void printLong(const longNumber & longNum, char c = ' ')
{
	//отново правим проверка за "несъществуващ аргумент"
	if(longNum == NULL)
	{
		cerr << "Error in trying to print longNumber at " << &longNum <<endl;
		return;
	}
	
	//извеждаме низа в обратен ред за да получим числото
	unsigned long length = strlen(longNum);
	
	//за да групираме цифрите по тройки ще използваме делене на 3 с остатък
	unsigned short tripleCount = (short)length%3; 

	while(length--)
	{
		cout << longNum[length] - '0';
		if (tripleCount == 1 && length > 2) //защо е втората проверка?  
		{
			cout << c;
		}
		tripleCount = (short)length%3;
	}
}



//Ето една примерна main() функция, коята работи с дълги числа.

void main()
{
	cout << "Enter two long numbers, separated by a comma: ####,####" << endl;
	cout << "Make sure that the first is greater than the second." << endl;
	char s1[100], s2[100];
	cin.getline(s1,99,',');
	cin >> s2;
	
	
	longNumber l1 = CreateLong(s1), l2 = CreateLong(s2), l3 = CreateLong();
	
	cout << endl;

	printLong(l1,'\'');  //ще използваме символа ' като разделител
	cout << endl << "+" << endl;
	printLong(l2, '\'');
	cout << endl << "=" << endl;
	add(l1,l2,l3);
	printLong(l3, '\'');
	cout << endl << endl;

	printLong(l1);
	cout << endl << "-" << endl;
	printLong(l2);
	cout << endl << "=" << endl;
	subtract(l1,l2,l3);
	printLong(l3);

	cout << endl;
	unsigned short num;
	do
	{
		cout << "Enter a number in [0-10]: ";
		cin >> num;
	}
	while ( num<0 || num>10 );
	
	cout << endl;
	printLong(l1);
	cout <<" * " << num << " =" << endl;
	multiplyDigitLong(num,l1,l3);
	printLong(l3);
	cout << endl;

		
	destroyLong(l1);
	destroyLong(l2);
	destroyLong(l3);
}