大数加减3.cpp

可以实现两个大整数（不限数位）相加减！ 在C＋＋中

#include<stdio.h>
#include<stdlib.h>

struct letter
	{
	char let;
	struct letter *link;
};/*初始化等式输入的链表存储*/

struct jht
	{
	int *a;/*保存第一个操作数*/
	int *b;/*保存第二个操作数*/
	int am;/*记录数组a的元素个数初始化为0*/
	int bn;/*记录数组b的元素个数初始化为0*/
	char first;/*记录第一个操作数的符号*/
	char second;/*记录第二个操作数的符号*/
};/*由链表转换成实际数据处理的载体*/


void keyin(struct letter *head)
	{
	char temp;	/*临时字符元素*/
	struct letter *next;/*临时链表元素*/
	next=head;/*初始化next*/
	scanf("%c",&temp);/*读取第一个输入符*/
	while(temp=='+'||temp=='-'||(temp>='0'&&temp<='9'))/*判断temp的内容，符合式子的规定范围内的字符都可以输入只能是＋－与数字*/
		{
		next->let=temp;/*将符合要求的字符插入链表*/
		next=next->link=(struct letter *)malloc(sizeof(struct letter));/*为下一次插入申请空间*/
		next->link=NULL;/*新空间作为链表尾插入*/
		next->let='=';/*新空间的内容为＝表示为链表最后一个元素*/
		scanf("%c",&temp);/*读取字符*/
	}
}



void trans(struct letter *head,struct jht *head2)/*将得来的链表提取转换成可以操作的数组*/
	{
	struct letter *temp;/*临时链表元素*/
	int m=0,n=0;/*m，n分别记录第一，二个数组的元素个数*/
	temp=head;/*初始化*/
	head2->first='+';/*将表示第一个数组的符号标志初始化为＋，这是为了区别第一个数是正数还是负数，默认第一个操作数为正数，在输入上，一般也不输入正号*/
	
	if(temp->let=='+')/*允许第一个操作数带一个正号，并将正号记录*/
		{
		head2->first=temp->let;
		temp=temp->link;		
	}
	if(temp->let=='-')/*允许第二个操作数带一个负号，并将负号记录*/
			{
			head2->first=temp->let;
			temp=temp->link;			
		}		

	while(temp->let!='+'&&temp->let!='-'&&temp->let!='=')
		{
		m++;/*同时记录第一个操作数个数*/
		temp=temp->link;
	}/*读取第一个操作数以遇到的字符为=,+,-结束，因为在keyin的时候已经排除了非+-数字的输入。但由于建立链表的时候以＝结束，所以也都要区别出+-=*/
	

	if(!m||temp->let=='=')
		{
		m=0;/*第一个操作数输入出错，清0*/
		printf("keyin wrong\n");
		return;
	}/*如果读取第一个操作数后立刻遇到＝，证明错误输入式子，报告出错并返回*/

	if(temp->let=='+')/*这里估计第二个操作数前的符号有一到两个。对第二个操作数的符号处理，根据实际分为+-,-+,++,--四类*/
		{
		head2->second=temp->let;
		temp=temp->link;
		if(temp->let=='-')
			{
			head2->second='-';/*+-得-*/
			temp=temp->link;
		}
		else if(temp->let=='+')
			{
			head2->second='+';/*++得+*/
			temp=temp->link;
		}
	}
	else
		if(temp->let=='-')
			{
			head2->second=temp->let;
			temp=temp->link;
			if(temp->let=='+')
				{
				head2->second='-';/*-+得-*/
				temp=temp->link;
			}
			else if(temp->let=='-')
				{
				head2->second='+';/*--得+*/
				temp=temp->link;
			}
		}

	while(temp->let!='+'&&temp->let!='-'&&temp->let!='=')/*读取第二个操作数以遇到的字符为=,+,-结束，因为在keyin的时候已经排除了非+-数字的输入。但由于建立链表的时候以＝结束，所以也都要区别出+-=*/
		{
		n++;/*同时记录第二个操作数个数*/
		temp=temp->link;
	}

	if(temp->let=='+'||temp->let=='-')
		{
		printf("keyin wrong");
		n=0;/*第二个操作数输入出错，清0*/		
		return;
	}/*以+-结束第二个操作数，明显不符合式子要求（这里只做两数加减）*/

	if(temp->let=='=')
		if(temp->link)
			{
			printf("keyin wrong");
			n=0;/*第二个操作数输入出错，清0*/
			return;
		}/*本身创建链表以=结束，如果这个=号后继还有元素，则明显不是最后一个元素，式子输入出错*/

	
	head2->am=m;/*将第一个操作数元素个数保存入操作载体*/
	head2->bn=n;/*将第二个操作数元素个数保存入操作载体*/
	head2->a=(int *)malloc(m*sizeof(int));/*为操作数动态申请数组*/
	head2->b=(int *)malloc(n*sizeof(int));/*为操作数动态申请数组*/		

	for(temp=head,m=head2->am-1;m>=0;temp=temp->link)/*前面的处理确保了两个操作数之间以+-为分界，式子以=号结束*/
		if(temp->let!='+'&&temp->let!='-')/*将第一个操作数由字符还原为数字，保存入数组*/
			{/*由数组尾开始保存，是为了以后计算是，可以两个数组都有一段共同的起点，简化以后操作*/			
			head2->a[m]=temp->let-'0';
			m--;
	}

			
	for(n=head2->bn-1;temp!=NULL;temp=temp->link)/*将第二个操作数保存入数组，具体如上*/
		if(temp->let!='='&&temp->let!='+'&&temp->let!='-')
			{			
			head2->b[n]=temp->let-'0';
			n--;
	}
}

void add(int *a,int am,int *b,int bn,int *result,int max,int min,char *flag)
	{
	int *id;/*进位数组指针*/
	int temp;

	if(bn==max)/*希望第一个操作数数位不少于第二个，以简化操作，*/
		{
		if(max==min);
		else{/*发现第二个操作数位数多于第一个，交换参数位置调用自身，且调用完后直接退出函数*/
		add(b,bn,a,am,result,max,min,flag);
		return;
		}
	}	
	
	id=(int *)malloc((min+1)*sizeof(int));/*按照最小空间个数+1申请进位数组*/

	for(temp=0;temp<=min;temp++)
		id[temp]=0;
	for(temp=0;temp<=max;temp++)
		result[temp]=0;/*将得数数组和进位数组初始化为0*/

	for(temp=0;temp<=min-1;temp++)/*在最小个数数组的范围下（b数组），得数数组为，a,b,id数组之和*/
		{
		result[temp]=a[temp]+b[temp]+result[temp];
		if(result[temp]-10>=0)/*得数大于9，即要进位*/		
		{
		result[temp]-=10;/*还原个位*/
		result[temp+1]=1;/*将下一个操作数的进位记为1*/
		}
	}
	
		for(;temp<=max-1;temp++)/*b数组操作完，继续处理剩下的a数组，得数数组为剩下a,id数组之和*/
			{
			result[temp]=a[temp]+result[temp];
			if(result[temp]-10>=0)/*处理进位，同上*/
				{
				result[temp]-=10;
				result[temp+1]=1;
			}
		}

	temp=max;/*打印得数数组，并根据flag的符号判断是否输入-号*/

	if(*flag=='-')
		printf("=-");
	else printf("=");
	
	if(result[temp])/*遇头位的0不输出*/
		printf("%d",result[temp]);	

	for(temp=max-1;temp>=0;temp--)
		printf("%d",result[temp]);
	

		
}

void minus(int *a,int am,int *b,int bn,int *result,int max,int min,char *flag)
	{
	int *id;/*退位数组指针*/
	int temp;
	if(bn==max)/*希望第一个操作数数位不少于第二个，以简化操作，同时注意减法比加法的要求要严格，即系要做到大数减细数*/
		{
		for(temp=max-1;temp>=0;temp--)
			if(b[temp]>a[temp])/*数描a,b数组，如果b确实在高位大过a，则可知道b为大数，a为细数，*/
				{
				*flag='-';/*为确保交换位置后的符号正确性，将符号标志记为-*/
				minus(b,bn,a,am,result,max,min,flag);
				return;
			}
		
	}	
	
		id=(int *)malloc((max+1)*sizeof(int));
		for(temp=0;temp<=max;temp++)
			id[temp]=0;
		for(temp=0;temp<=max;temp++)
			result[temp]=0;/*为得数数组和退位数组初始化*/

		for(temp=0;temp<=min-1;temp++)/*在前面保证大数减细数的前提下,可以安心使用退位数组*/
			{	
			result[temp]=a[temp]-b[temp]+result[temp];/*得数数组为大数组减细数组再加上退位数组*/
			if(result[temp]<0)/*将负数还原为个位数*/
				{
				result[temp]+=10;
				result[temp+1]=-1;/*并在高1位退1*/
			}
		}
		for(;temp<=max-1;temp++)/*处理大数数组(即a数组)的剩余位*/
			{
			result[temp]=a[temp]+result[temp];
			if(result[temp]<0)/*处理退位*/
				{
				result[temp]+=10;
				result[temp+1]=-1;
			}
		}
		
		if(*flag=='-')			
			printf("=-");
		else{			
			printf("=");
		}
		temp=max-1;	/*减法的得数最多只能与大数数位相同,而且在肯定为大数减细数的情况下,高一位的退位不存在*/	
		for(;temp>=0;temp--)
			if(result[temp])
				break;
		if(temp==-1)/*若得数没有一个非0,则得数为0*/
			printf("0");
		else
			for(;temp>=0;temp--)
				printf("%d",result[temp]);
		
	
}

void duel()
	{
	struct letter sta;/*式子字符链表*/	
	struct jht head2;/*式子运算的载体结构*/
	struct jht *head=&head2;
	int *result;/*得数数组的指针*/
	int max,min;/*统计两个操作数组的元素个数，找出最大最小值*/
	char flag;/*根据两个操作数符号，初步估计结果符号，不可估计的情况置'0'*/

	system("cls");
	printf("本程序可对任意两个整数进行加减法运算.\n输入格式如下:45678+-65464\n");

	head2.am=0;/*对两个结构体初始化*/
	head2.bn=0;	
	sta.let='=';
	sta.link=NULL;

	keyin(&sta);/*输入式子*/	
	trans(&sta,&head2);	/*转换式子*/

	if(head2.am==0||head2.bn==0)
		return;

	max=(head->am>head->bn)?head->am:head->bn;/*求最大个数*/
	min=(head->am<head->bn)?head->am:head->bn;/*求最小个数*/
	result=(int *)malloc((max+1)*sizeof(int));/*以最大个数＋1申请结果数组（对于加法可能会有max+1位，减法可能会有max位）*/	
	

	
	if(head->first=='+')		
		if(head->second=='+')
			{
			flag='+';/*两正数相加肯定为正*/
			add(head->a,head->am,head->b,head->bn,result,max,min,&flag);
		}
		else 
			{
			flag='0';
			minus(head->a,head->am,head->b,head->bn,result,max,min,&flag);
		}
	
	else 		
		if(head->second=='+')
			{
			flag='0';
			minus(head->b,head->bn,head->a,head->am,result,max,min,&flag);
		}
		else 
			{
			flag='-';/*两负数相加肯定为负*/
			add(head->a,head->am,head->b,head->bn,result,max,min,&flag);
		}
	


}

void main()
	{
	char ch;
	while(1)
		{
		printf("\t\t\t大数加减\n");
		printf("*********************************************************\n");
		printf("(S)开始\n(E)离开\n请输入你的选择:");
		scanf("%c%*c",&ch);
		if(ch<='z'&&ch>='a')
			ch-=32;
		switch(ch)
			{
			case 'S':duel();printf("\n");system("pause");break;
			case 'E':return;
		}
		
		system("cls");
	}

}