large.cpp

大数的加减乘除运算

/*
 * Name:	 large.cpp
 * Date:     2009-02-20
 * Function: 给定一些整数（其位数可能上百位），对其可完成加、减、乘和整除运算。
	输入描述
     
	输入若干组数据，每组数据由一个运算符（＋，－，*，/）和两个整数构成，整数的范围在（-10^150～10^150），如果遇到符号"@"，则输入结束。
	输出描述
 	对于输入的每组数据，输出其运算序号和运算结果，每个结果独占一行；
 	如果计算结果超200位，则输出"Too Large Number."；
 	如果运算符不是上述四种之一，则输出"Illegal Operator."；
 	如果除0，则输出"Divide By Zero."。

  输入样本
	/
	100 0
	*
	12345678901234567890 54321
	*
	12 21
	@
	"	输出样本
	1 Divide By Zero.
	2 670629623593962962352690
	3 252

* CopyRight: 电控 
 * Modify:
 */

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

#define  MAXLENGTH   512
#define  RESULTLENGTH 512
#define  MAXPAIR    256


char *sub(char *num1,char *num2);
char *add(char *num1,char *num2);
char *mul(char *num1,char *num2);
char *div(char *num1,char *num2);

void  clearZero(char *r); //清除字符串前0
void  DelFlag(char *r) ; //删除字符串前面的负号
char * AddFlag(char *r) ;//加负号
int cmp(char *r,char *t);//比较两个字串 

int main(int argc,char **argv)
{
	char flag; //符号
	char *num1;
	char *num2;
	char *result[MAXPAIR];
	int t = 0;
	num1 = (char*)malloc(MAXLENGTH * sizeof(char));
	if(num1 == NULL)
	{
		cout << "内存分配失败"<<endl;
		return -1;
	}
	num2 = (char*)malloc(MAXLENGTH * sizeof(char)) ;
	if(num2 == NULL)
	{
		cout << "内存分配失败"<<endl;
		return -1;
	}
	cout <<" 输入样本 :"<<endl;
	while(1)
	{
		cin >> flag;
		if(flag == '@')
		{
			break;
		}
		result[t] = (char*)malloc(2*MAXLENGTH * sizeof(char));
		if(result[t] == NULL)
		{
			cout << "内存分配失败"<<endl;
			return -1;
		}
		for(int i = 0 ;i<2*MAXLENGTH ;i++)
		{
			result[t][i] = '\0';
		}
		cin >> num1;
		cin >> num2; 
		switch(flag)
		{
			case '-':
				{
					strcpy(result[t], sub(num1,num2));
				}
				break;
			case '+':
				{
					strcpy(result[t], add(num1,num2));
				}
				break;
			case '*':
			{
				strcpy(result[t],mul(num1,num2)) ;
				 
			}
			break;
			case '/':
			{
				strcpy(result[t], div(num1,num2));
			}
			break;
			default :
			{
				strcpy(result[t],"Illegal Operator");
			}
			break;
			
		}
		++t;
	}
	cout << "输出结果:"<<endl;
	for (int i = 0; i < t; i++)
	{
		cout << i+1<<"\t"<<result[i]<<endl;
	}
	free(num1);
	free(num2);
	for(i = 0; i < t; i++)
	{
		free(result[i]) ;
	}
	return 0;
}

////////////数组前清零//////////////////////////////////////////////////////////////

void  clearZero(char *r)
{
	int lr;  
	int i=0, j; 
	lr=strlen(r);  
	while(r[i] == '0') 
	{
		++i;
	}
	if(i > 0) 
	{
		for(j = 0; j < lr-i; ++j)
		{
			r[j] = r[j+i];
		}
		for(j = lr-i; j < lr; ++j) 
		{
			 r[j] = '\0'; 
		}
		
	}
	
	 if(r[0] == '\0')
	 {
		  r[0] = '0';
	 } 

}
//////////////删除符号////////////////////////////////////////////////////////////

void  DelFlag(char *r)  //删除字符串前面的负号
{
	int lr;
	lr = strlen(r) ;
	int i  ;
	for(i = 0;i<lr-1;i++)
	{
		r[i] = r[i+1];
	}
	r[lr-1] = '\0' ;
}

///////////增加符号///////////////////////////////////////////////////////////////

char * AddFlag(char *r) //加负号
{
	int lr ;
	lr = strlen(r) ;
	char *p = (char*)malloc((lr+1)*sizeof(char));
	if(p == NULL)
	{
		cout << "内存分配出错"<<endl ;
		exit(0) ;
	}
	memset(p,'\0',lr+1);
	p[0] = '-' ;
	strcat(p,r) ;
	return p ;
}

//////////////////乘法////////////////////////////////////////////////////////

char *mul(char *num1,char *num2)
{
	char *temp ; //存结果
	char c = '0' ; //暂存符号num1
	char d = '0'; //暂存符号num2
	int i,j; 
	int len1 = strlen(num1);  
	int len2 = strlen(num2);
	temp = (char*)malloc((RESULTLENGTH)*sizeof(char));
	if(temp == NULL)
	{
		cout << "内存分配出错"<<endl;
		exit(-1) ;
	}
	//初始化结果数组
	for(i = 0 ;i<len1+len2;i++)
	{
		temp[i] = '0' ;
	}
	temp[i] = '\0' ;
	c = num1[0] ;
	d = num2[0];
	if(c == '-')
	{
		DelFlag(num1);
		len1 = strlen(num1);
	}
	if(d == '-')
	{	
		DelFlag(num2);
		len2 = strlen(num2);
	}

	int  carry = 0; //进位初时设为0 
	int h ;
	for(i=len1-1; i>=0; --i) 
	{ 
		carry = 0; 
		for(j=len2-1; j>=0; --j) 
		{ 
			int lp = i+j+1;
			h = (num1[i] - '0')*(num2[j] - '0')+(temp[i+j+1] - '0') + carry; //x - '0' 将字符转化为数字 
			
			carry = h / 10 ;
			h = h %10 ;
			temp[i+j+1] = h+'0';
		} 
		if(carry > 0)
		{
			temp[i+j+1] = carry + '0' ;
		}
	} 
	
	clearZero(temp) ;

	if((c == '-'&&d != '-' ) || (c != '-' &&d == '-'))
	{
		int len = strlen(temp);
		temp[len-1] = '\0';
		strcpy (temp,AddFlag(temp));
		
	}
	else if (c == '-' && d == '-')
	{
		int len = strlen(temp);
		temp[len-2] = '\0';

	}
	int len = strlen(temp) ; //计算结果位数
	if(len > 200)
	{
		strcpy(temp,"Too Large Number.");
		return temp;
	}
	else
	{
		return temp;
	}
}

//////////////加法 //////////////////////////////////////////////////////////


char *add(char *num1,char *num2)
{
	int len1;
	int len2;
	int mid; //交换用
	int carry = 0;//进位 
	char *result;
	char *p ;
	int temp;
	char tt;

	len1 = strlen(num1);
	len2 = strlen(num2);

	result = (char*)malloc((len1+len2)*sizeof(char));
	if( result == NULL)
	{
		cout << "分配内存错误 "<<endl;
		exit(-1);
	}
	for(int m = 0 ;m < len1+len2; m++)
	{
		result[m] = '0' ;
	}
	result[m] = '\0' ;
	char c,d;
	c = num1[0];
	d = num2[0];
	if((c == '-') && (d!= '-'))
	{
		DelFlag(num1);
		return(sub(num2,num1)); ////直接调用减法
	}
	if((d == '-')&&(c != '-'))
	{
		DelFlag(num2);
		return (sub(num1,num2)); //直接调用减法
	}
	if((c == '-')&&(d == '-'))
	{
		DelFlag(num1);
		DelFlag(num2);
		strcpy (result,AddFlag(add(num1,num2))); //递归调用 
	}
	else
	{
		//如果第一个数字长度比第2个大  ，交换两个字串  
		if(len2 > len1)
		{
			p = num1;  
			num1 = num2 ;
			num2 = p;
			mid = len1;
			len1 = len2;
			len2 = mid ;
		}
		int i;
		for(i=0; i<len1; ++i) 
		{ 
			mid = num1[len1-i-1] -'0' + num2[len2-i-1] -'0' + carry; 
			if(mid > 9) 
			{ 
				carry = 1;
				mid = mid - 10; 
			} 
			else 
			{
				carry = 0;
			}
			result[i] = mid + '0';  
		} 
		for(i = len2; i < len1; ++i) 
		{ 
			mid = num1[len1-i-1] - '0' + carry; 
			if(mid > 9) 
			{ 
				carry = 1; 
				mid = mid - 10; 
			} 
			else 
			{
				carry = 0;
			}
			result[i] = '0' + mid;  
		} 
		if(carry > 0) 
		{ 
			 result[i] = carry + '0'; 
			 temp = i; 
		} 
		else 
		{
			temp = i - 1;
		}
		for(i = temp + 1; i < len1 + 2; ++i) 
        {
			result[i]='\0';
		}
		for(i=0; i<(temp+1)/2; ++i) 
		{ 
			tt = result[i]; 
			result[i] = result[temp-i]; 
			result[temp-i] = tt; 
		} 
	}
	int len = strlen(result) ;
	if(len > 200)
	{
		strcpy(result,"Too Large Number.");
		return result;
	}
	else
	{
		return result;
	}
	
}

////////减法/////////////////////////////////


char *sub(char *num1,char *num2)
{
	int len1;
	int len2;
	int mid;
	int carry = 0;
	int flag = 0; //大小标志 
	char c,d;//暂存符号
	char hc;
	len1 = strlen(num1);
	len2 = strlen(num2);
	char *p; //交换字符串
	char *result ;
	result = (char*)malloc((len1+len2)*sizeof(char));
	if(result == NULL)
	{
		cout << "内存分配失败"<<endl ;
		exit(-1);
	}
    //清空result
	for(int m = 0 ;m < len1+len2; m++)
	{
		result[m] = '0' ;
	}
	result[m] = '\0' ;

	c = num1[0];
	d = num2[0];
	if(c == '-' && d != '-')
	{
		strcpy(num2,AddFlag(num2));
		strcpy (result,(add(num1,num2))); //调用 加法 并在结果加负号
		return result;
	}
	if(c != '-' && d == '-')
	{
		DelFlag(num2);
		strcpy (result,add(num1,num2));  //变为加
		return result;
	}
	if(c == '-' && d == '-')
	{
		DelFlag(num2);
		return (add(num2,num1));//递归调用，num2 - num1 为结果
	}
	else
	{	
		if(cmp(num1,num2) < 0)
		{	
			flag = 0xff;
			p = num1;
			num1 = num2;
			num2 = p;
			mid = len1;
			len1 = len2 ;
			len2 = mid;
		}
		int i;
		for(i=0; i<len2; ++i) 
		{
			mid = num1[len1-i-1] - num2[len2-i-1] - carry; 
			if(mid < 0) 
			{
				carry = 1; 
				mid = mid + 10;
			} 
			else 
			{
				carry = 0; 
			}
			result[i] = mid + '0';
		    hc = mid + '0';
		} 
		for (i=len2; i<len1; ++i) 
		{ 
			mid = num1[len1-i-1] - '0' - carry;
			if(mid < 0) 
			{
				carry = 1; 
				mid += 10; 
			} 
			else 
            {
				carry = 0;
			}
			 result[i] = '0' + mid; 
			hc = '0' + mid;
		}
		int temp ;
		result[i] = '\0';
		temp = i-1;
		while(result[temp] == '0' && temp != 0)
		{
			result[temp] = '\0';
			temp--; 
		}

		for(i=0; i<(temp+1)/2; ++i) 
	    { 
			hc = result[i]; 
			result[i] = result[temp-i]; 
			result[temp-i] = hc; 
		} 

	}
	int len = strlen(result) ;
	if(len > 200)
	{
		strcpy(result,"Too Large Number.");
		return result;
	}
	else
	{
		if(flag == 0xff)
		{
			strcpy(result,AddFlag(result));
		}
		return result;
	}
}

///////////////整除///////////////////

char *div(char *num1,char *num2)
{
	char *result;
	char *remain;
	int len1;
	int len2;
	len1 = strlen(num1);
	len2 = strlen(num2);
	char c,d;//暂存符号
	result = (char*)malloc((len1+len2)*sizeof(char));
	if(result == NULL)
	{
		cout << "内存分配失败 "<<endl;
		exit(-1);
	}

	for(int m = 0 ;m < len1+len2; m++)
	{
		result[m] = '\0' ;
	}

	remain = (char*)malloc((len1+len2)*sizeof(char));
	if(remain == NULL)
	{
		cout << "内存分配失败 "<<endl;
		exit(-1);
	}

	for(m = 0 ;m < len1+len2; m++)
	{
		remain[m] = '\0' ;
	}

	c = num1[0];
	d = num2[0];

	if(d != '-')
	{
		clearZero(num2);
		if(num2[0] == '0') //判断除数 0
		{
			strcpy(result,"Divide By Zero.");
			free(remain);
			return result;
		}
	}
	if(d == '-')
	{
		DelFlag(num2);
		
		if(num2[0] == '0') 
		{
			strcpy(result,"Divide By Zero.");
			free(remain);
			return result;
		}
	}
	if(c == '-')
	{
		DelFlag(num1);
	}
	
	int i ;
	int temp;
	int remainlength ;
	if(cmp(num1,num2) < 0)
	{
		strcpy(result,"0");
		free(remain);
		return result;
	}
	for(i=0; i < len1; ++i) 
    { 
	   clearZero(remain);
	   remainlength = strlen(remain);
	   remain[remainlength] = num1[i];
	   remain[remainlength +1 ] = '\0';
       temp = 0; 
	   clearZero(num2);
	   clearZero(remain);
       while(cmp(remain,num2) >= 0) 
       { 
		   if(remain[0] == '-')
		   {
			   break;
		   }
            strcpy(remain,sub(remain, num2)); 
            ++temp; 
       } 
        result[i] = temp + '0'; 
    }  
	
    clearZero(result);
	int len;
	if((c == '-'&& d != '-') || (c != '-' && d == '-'))
	{
		strcpy(result,AddFlag(result));
		free(remain);
		len = strlen(result);
		if(len > 200)
		{
			strcpy(result,"Too Large Number.");
			return result;
		}
		else
		{
			return result;
		}
	}
	else
	{
		free(remain);
		if(len > 200)
		{
			strcpy(result,"Too Large Number.");
			return result;
		}
		else
		{
			return result;
		}
	}

}

//比较两字串 大小
int cmp(char *r,char *t)
{
	int lenr;
	int lent;
	lenr = strlen(r);
	lent = strlen(t);
	if(lenr > lent )
	{
		return 1;

	}
	else if(lenr < lent)
	{
		return -1;
	}
	else
	{
		return (strcmp(r,t));
	}
}