#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

//zero vector , used for comparing with zero
vector <int> zer(1);

/*assign takes as an input an <int> vector to hold the number and a str containing the number to be assigned
 *returns an integer . 1 if the number is valid , -1 otherwise
 */
int assign(vector<int> &v, string str){

	v.resize(str.size()); 
	//placing the string holding the number to the temproray vector
	long i = str.size() - 1;
	long j = 0; 
	
	while(i >= 0 )
	{	//checks if the char represents a valid asci number (withing the range 47 and 57) or a negative sign for the first character
		if(str.at(j) > 46 && str.at(j) <58  || str.at(j) == 45 && j == 0 )
		{	
			char c = str.at(j++);
			if (c == '-')
			v[i] = c;
			else
			v[i] = (atoi(&c));			
		}
		else
		return -1; 
		i--;
	}
		//succeed 
		return 1;
	
}

/*setSign takes as an input an <int> vector and a sign 
 *Places a a negative sign to the number assuming it is not zero 
 */
void setSign(vector<int> &v, int sign)
{
	if(sign == 1 && !(v.size()== 1 && v[0] == 0))
	{	
	v.resize(v.size()+1); 
	v[v.size()-1] = 45; 
	}			
}


/*reset : takes as an input an <int> vector represented by vector   
 *	  sets the number to 0 . 
 */
void reset(vector<int> &v)
{
	v.resize(1); 
	v[0] = 0; 
}

/*clean takes as an input an <int> vector and a sign 
 *Removes any leading zeros . and then calls setSign to place the sign 
 */
void clean(vector<int> &v, int sign)
{
	int resize = 0; 
	
	for(int i = v.size()-1 ; i > 0; i--)
	{
		if(v[i] == 0 ) 
		resize++;
		else
		break;
	}

	if(resize!= 0 )
		v.resize(v.size() - resize); 
	
	setSign(v, sign); 
}


/*print displays the content of the vector or invalid if err is set to 1
 */
 
void print(vector<int> v) 
{

	cout<<"Value: ";	
	for(int i = v.size()-1; i >= 0; i--)
	{
		if(v[i] == 45 ) 
		cout<<"-"; 
		else
		cout<<v[i]; 
	}
	cout<<endl;
	
}

/*cmp compares the magnitude of two <int> vectors a and b
 *returns 0 if a == b 
 *	  1 if a > b 
 *        2 if b > b
 */
int cmp (vector<int> a , vector<int> b)
{		
	

	int s1 = a.size()-1; 
	int s2 = b.size()-1; 
	
	//Since we are comparing the magnitude we do not need to count the negative sign
	if(a[a.size() - 1] > 9 ) 
		--s1;	 	
	
	if(b[b.size() - 1] > 9 ) 
		--s2; 
	if(s1 > s2) 
		return 1; 
	else if(s2 > s1 ) 
		return 2;
	else 
	{
		for(int i = s1; i >= 0; i--)
		{
			if(a[i] > b[i]) return 1;
			else if(a[i] < b[i]) return 2; 
		
		}	 
		return 0; 
	}

}



/*sub subtracts takes two <int> vectors v1 and v2 , order and the resultant sign 
 *if order is 1 or 0  v2 is subtracted from v1 else v1 is subtracted from v2
 *the result is stored in v1 . 
 */
void sub(vector <int> &v1 , vector<int> v2, int order, int sign)
{
	
	vector<int> a1; 
	vector<int> a2; 

	//order < 2 means v1 >= v2 
	//order 2 means v2 > v1
	if(order < 2 )
	{ 
		a1.assign(v1.begin(), v1.end()); 
		a2.assign(v2.begin(), v2.end()); 		
		
	}
	else 
	{
		a1.assign(v2.begin(), v2.end()); 
		a2.assign(v1.begin(), v1.end());  
		
	}
	
	//The size of the two operands should be identical 
	v1.resize(a1.size()); 
	a2.resize(a1.size()); 

	

	int loop = 1; 
	for(int i=0 ; i < a1.size(); i++) 
	{

			if(a1[i] >= a2[i]) 
				v1[i] = a1[i] - a2[i];					
			
			else
			{	
				int j = i+1;

				while(loop)
				{
					if( a1[j] > 0 ) 
							{ 
								a1[j]--; 
								for(int k = i+1 ; k < j; k++)
									a1[k] = 9;
									
								loop = 0;  
							}
					++j;
				}

				v1[i] = a1[i] + 10 - a2[i];
				loop = 1;
			}
	}	


	clean(v1, sign);
	

}




/* add takes two unsigned numbers as <int> vectors and a sign for the resultant 
 * The result is stored in v1 
 */
void add(vector<int> &v1, vector<int> &v2, int sign)
{ 
	
	
	if(cmp(v1,v2) == 2)
		v1.resize(v2.size()); 
	else 
		v2.resize(v1.size()); 

	//temproray variable needed to hold the sum and passing it to operand 1 
	int num;
	//Carry	
	int c = 0;  

	//Looping through operand 2 and performing addition
	//the result is stored in v1 . 
	for(int i = 0; i < v2.size(); i++) 
	{	
		num = v1[i] + v2[i] + c; 
		if(num >= 10 ) 
		 c = 1; 
		else
		 c = 0;
		v1[i] = num; 
		
		
		if(v1[i] >= 10 ) 
			v1[i] = v1[i] - 10; 
	}
		if(c == 1) 
		{
		v1.resize(v1.size()+ 1);
		v1[v1.size() - 1] = 1; 
		}	

		//removing any leading zeros as a result of resizing one of the operands. 
		clean(v1, sign); 
	
	
	

}


/* mul takes two unsigned numbers as <int> vectors and a sign for the resultant 
 * multiplies v1 and v2 and stores the result in v1
 */
void mul(vector<int> &v1, vector<int> &v2, int sign)
{


	vector<int> v(v1.size() + v2.size() + 1); 
	
	int i =0; 
	for(i = 0; i <v2.size(); i++)
	{
			vector<int> m(v1.size() + i + 1) ; 
	
			int cr = 0;  int b; 
			int j =0;
				for(j =0; j <v1.size(); j++)
				{	b = v1[j] * v2[i] + cr; 
						if(b > 9 )
						{	cr = b/10 ; 
							b =  b - cr * 10;
						}
						else 
						cr = 0; 

						m[j + i] = b;
						
				}
				if(cr != 0 )
					m[j + i] = cr; 

				add(v,m,0);
	}


clean(v, sign); 
v1.assign( v.begin(), v.end() );      



}

/*init Array takes as an input a vector of vectors , and another vector
 *arr contains vectors holding number 1 to 9 . 
 *the func calls mul to multiply v2 with each vector from 1 to 9  
 *this function is used by the division . 
 */
void initArray(vector< vector<int> > &arr, vector<int> v2)
{	
	
	for(int i = 0 ; i < 9; i ++)
		mul(arr[i], v2, 0);
}


/*findIndex takes as an input a vector v and array of vectors arr . 
 *the function returns the index of the smallest number in arr that is larger than v. 
 */
int findIndex(vector<int> v , vector< vector<int> > arr)
	{
	
		for(int i =0; i < 9; i++) {
			if( cmp(arr[i], v) == 1 )
				return i; 

			}
		return 9; 
	}


/*div takes two <int> vectors v1 and v2 , and the resultant sign 
 *the function divides the two numbers represented as vectors and 
 *stores the result back in v1. 
 */
void div(vector<int> &v1 , vector<int> &v2, int sign)
{

	vector<int>r(0); 
	int index; 

	

	if(cmp(v1,v2) == 2 ||v1.size() == 1 && v1[0] == 0 || v2.size() == 1 && v2[0] == 0 )
		{
			reset(v1); 
		         return; 
		} 
	
	vector< vector<int> > arr(10); 
	 
	for(int loop = 0; loop < 9; loop++)
	    arr[loop].push_back(loop+1); 

		initArray(arr,v2); 

		int i = v1.size() - 1; 
		vector<int>a(0);

	while(i >= 0 )
	{



	int insert = 0; 

	
	
	while(a.size() < v2.size() && i > -1 )
	{	
			
		a.insert(a.begin(), 1, v1[i--]); 
		
	
			
					
		if(insert++ > 0)		
		r.insert(r.begin(), 1,0); 
		
			

	}
	
	clean(a,0); 
	
	if(cmp(v2, a) == 1  && i > -1 && cmp(zer,a) != 0) {
	a.insert(a.begin(),1,v1[i--]); 
	if(insert > 0)		
	r.insert(r.begin(), 1,0); 
	
	}
	

	if( cmp(a, v2) == 2)
	r.insert(r.begin(), 1,0);	
	else{
	index = findIndex(a, arr); 		
	r.insert(r.begin(), 1,index);
	}

	sub(a,arr[index-1],1, 0); 
		

	//we need to modify the size if the result is 0 
	if(a.size() == 1 && a[0] == 0)
		a.resize(0);   
	
	

	}

	
	
	clean(r, sign); 
	v1.assign(r.begin(), r.end()); 	
 

		
}


/* findOperation takes as an input two signed numbers represented as <int> vectors and the <int> operation to be performed
 * operation 0 for addition.
 * operation 1 for subtraction. 
 * operation 2 for multiplication. 
 * operation 3 for division 
 */ 
void findOperation(vector<int> &v1, vector<int> &v2, int operation)
{



	
	
	//initialize temproray variables
	int sign1 = 0 , sign2 = 0 , s = 0 , cm = 0;
	
	//removes the sign from the two input numbers 
	if(v1.at(v1.size() - 1) == 45 )
	{ sign1  = 1; v1.resize(v1.size() - 1);}

	if(v2.at(v2.size() - 1) == 45 ) 
		{sign2  = 1; v2.resize(v2.size() - 1);}
	
	//compares the magnitude of the two input operands 
	cm = cmp(v1, v2) ;
		
	//operation is either addition or subtraction 															
	if(operation < 2 )       
	{
		//do addition 
		if(sign1 == sign2 && operation == 0 || sign1 != sign2 && operation == 1 ) 
		add(v1, v2, sign1); 
		
		//do subtraction and compute the resultant sign 		
		else
		{ 	 
			if(sign1 == sign2)  					
				{
				   if(sign1 == 0 )
					{
					if(cm < 2)			   
					sub(v1,v2,cm,0); 		 
					else
					sub(v1,v2,cm,1); 
					}
				   else
				        {
					if(cm < 2)			   
					sub(v1,v2,cm,1); 		 
					else
					sub(v1,v2,cm,0); 
					}					
				}			
				else 
			        {
				if(cm < 2)			   
				sub(v1,v2,cm,sign1); 		 
				else
				sub(v1,v2,cm,sign2); 
				}			 
		}
	}
	//operation is either multiplication or divison
	else
	{
		if (sign1 != sign2) s = 1; 
			
			if(operation == 2 ) 
				mul(v1,v2,s);
			else			
			div(v1,v2,s);
			
	
		 
	}		
}


int main() 
{

	//v will hold the accumulator 
	vector<int> v(0); 

	vector<int> temp(0); 
	int valid;
	v.push_back(0); 
	


	string s,s2; 
	
	while(1)
	{

		print(v);
		cout<<"Enter: ";				 
		cin >> s;  
				
		
		

		if(assign(temp,s.substr(1)) == 1)
		{
		switch(s.at(0))
		{
		case '=': 
			  v.assign(temp.begin(), temp.end()); 		  		
		  	  break;					
		case '+': findOperation(v,temp,0);
			  break; 		
		case '-': findOperation(v,temp,1); 
			  break; 
		case '*' : findOperation(v,temp,2); 
			  break;
		case '/' :findOperation(v,temp,3);
			   break;
		case 'E' : return 1; 
			   break; 
		case 'C' : reset(v); 
			   break; 
		default  :cout<<"Invalid input\n"; 
				
		}
		}
		else
		cout<<"Invalid input\n"; 																																																																																																																																																																																																																																																																																																																																																																																																																														 
		
		 
	 		
	}
	
	
	return 1; 


}