#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define Max 1000000
void BigNumsAdd(char *numa,char *numb);
void BigNumsSub(char *numa,char *numb);
void BigNumsMul(char *numa,char *numb);
int check(char *s);
clock_t start,end;

void inscanf(char c,char *&n1,char *&n2){
char t;
int i=0;
while(1){
t=getchar();
if(t==c && !(c=='-'&&i==0)) break;
n1[i++]=t;
}
n1[i]=0;
i=0;
while(1){
t=getchar();
if(t==10) break;
n2[i++]=t;
}
n2[i]=0;
putchar('=');
}

void switcher(char *n,int *num,int &weishu) //将字符数组转换为整形数组
{ //整形数组的低位至高位分别
int i; //储存数据的个位到高位数字
for(i=0;i<Max+1;i++) num[i]=0;
for(i=1;i<weishu;i++)
num[i]=n[weishu-i]-'0';
if(n[0]=='+' || n[0]=='-')
{
weishu--;
num[0]=n[0];
}
else num[weishu]=n[0]-'0';
}

void BigNumsAdd(char *numa,char *numb) //大整数的相加，其中两个参数分别为两个待输入的字符串
{
int *Num1=NULL,*Num2=NULL,*answer=NULL;
int weishu1,weishu2,wei;
int i,s=0;
if(numa[0]=='-' && numb[0]!='-') //两个数一正一负的时候，改变符号后转跳到相减
{
numa[0]='+';
BigNumsSub(numb,numa);
return;
}
if(numb[0]=='-' && numa[0]!='-')
{
numb[0]='+';
BigNumsSub(numa,numb);
return;
}
weishu1=strlen(numa);
Num1=(int*)malloc((Max+1)*sizeof(int));
weishu2=strlen(numb);
Num2=(int*)malloc((Max+1)*sizeof(int));
switcher(numa,Num1,weishu1);
switcher(numb,Num2,weishu2);
wei=(weishu1>weishu2)?weishu1:weishu2;
answer=(int*)malloc((wei+2)*sizeof(int)); //(wei+2)??防止相加后位数增1
for(i=0;i<wei+2;i++) answer[i]=0;
for(i=1;i<=wei;i++)
{
answer[i]+=(Num1[i]+Num2[i]);
if(answer[i]>=10) //逢十进一
{
answer[i]-=10;
answer[i+1]++;
}
}
if(numa[0]=='-' || numb[0]=='-') //注意负数的时候
printf("-");
if(answer[wei+1]!=0)
printf("%d",answer[wei+1]);
for(i=wei;i>=1;i--)
{
if(s==1)
printf("%d",answer[i]);
else if(answer[i]!=0)
{
s=1;
printf("%d",answer[i]);
}
}
if(s==0) printf("\r0");
printf("\n");
free(Num1);
free(Num2);
free(answer);
}
void BigNumsSub(char *numa,char *numb) //大整数的相减(numa-numb)
{
int *Num1=NULL,*Num2=NULL,*answer=NULL;
int weishu1,weishu2,wei,len,j=0;
int i,sign=0,s=0; //负数情况比正数稍麻烦，于是用sign作为答案的正负符号标志
if(numa[0]=='-' && numb[0]!='-') //两个数一正一负的时候，稍作调整后转跳到相加
{
len=strlen(numb);
numb[len+1]='\0';
for(j=0;j<len;j++){
numb[j+1]=numb[j];
}
numb[0]='-';
BigNumsAdd(numa,numb);
return;
}
if(numb[0]=='-' && numa[0]!='-')
{
numb[0]='+';
BigNumsAdd(numa,numb);
return;
}
weishu1=strlen(numa);
Num1=(int*)malloc((Max+1)*sizeof(int));
weishu2=strlen(numb);
Num2=(int*)malloc((Max+1)*sizeof(int));
switcher(numa,Num1,weishu1);
switcher(numb,Num2,weishu2);
wei=(weishu1>weishu2)?weishu1:weishu2;
answer=(int*)malloc((wei+2)*sizeof(int));
for(i=0;i<wei+2;i++) answer[i]=0;
for(i=1;i<=wei;i++)
{
answer[i]+=(Num1[i]-Num2[i]);
if(answer[i]<0) //借位
{
answer[i]+=10;
answer[i+1]--;
}
}
if(answer[wei+1]<0)
{
for(i=1;i<=weishu2;i++) Num1[i]=0;
for(i=1;i<=weishu2;i++)
{
answer[i]=Num1[i]-answer[i];
if(answer[i]<0)
{
answer[i]+=10;
answer[i+1]++;
}
}
answer[weishu2+1]=0;
sign++;
}
if(numa[0]=='-') sign++; //注意负数的时候
if(sign%2!=0)
printf("-");
for(i=wei;i>=1;i--)
{
if(s==1)
printf("%d",answer[i]);
else if(answer[i]!=0)
{
s=1;
printf("%d",answer[i]);
}
}
if(s==0) printf("\r0");
printf("\n");
free(Num1);
free(Num2);
free(answer);
}

void BigNumsMul(char *numa,char *numb) //大整数乘法
{
int *Num1=NULL,*Num2=NULL,*answer=NULL;
int weishu1,weishu2,wei;
int i,j;
int yu,s=0;
weishu1=strlen(numa);
Num1=(int*)malloc((Max+1)*sizeof(int));
weishu2=strlen(numb);
Num2=(int*)malloc((Max+1)*sizeof(int));
switcher(numa,Num1,weishu1);
switcher(numb,Num2,weishu2);
wei=weishu1+weishu2; //乘法结果的最大位数是两者位数和
answer=(int*)malloc((wei+1)*sizeof(int));
for(i=0;i<wei+1;i++) answer[i]=0;
for(j=1;j<=weishu1;j++)
{
for(i=1;i<=weishu2;i++)
{
answer[j+i-1]+=(Num1[j]*Num2[i]);
if((yu=answer[i+j-1]/10)!=0)
{
answer[i+j]+=yu;
answer[i+j-1]-=yu*10;
}
}
}
if((numa[0]=='-' && numb[0]!='-') || (numa[0]!='-' && numb[0]=='-'))
printf("-");
for(i=wei;i>=1;i--)
{
if(s==1)
printf("%d",answer[i]);
else if(answer[i]!=0)
{
s=1;
printf("%d",answer[i]);
}
}
if(s==0) printf("\r0");
printf("\n");
free(Num1);
free(Num2);
free(answer);
}


int check(char *s) //字符串检查，当格式错误时候返回1，整个数字为0的时候返回2（用于除法的余数），正常返回0
{
int i;
int l,sign=1;
l=strlen(s);
if(s[0]!='-' && s[0]!='+' && (s[0]>'9' || s[0]<'0'))
{
printf("ERROR:输入格式错误！\n");
return 1;
}
if(s[0]>='0' && s[0]<='9') sign=0;
for(i=1;i<l;i++)
{
if(s[i]!='0') sign=0;
if(s[i]>'9' || s[i]<'0')
{
printf("ERROR:输入格式错误！\n");
return 1;
}
}
if(sign==1) return 2;
else return 0;
}
int main()
{srand(time(NULL));

char *num1,*num2;
int i;
int tmp;
for(i=0;i<33;i++)
printf(" ");

num1=(char*)malloc(Max*sizeof(char));
num2=(char*)malloc(Max*sizeof(char));
while(1)
{
system("cls");
printf("\n");
printf("\t\t\t\t 大整数运算程序\n");
printf("\t\t\t\t\tMenu\n");
printf("\t\t\t**************************************\n");
printf("\t\t\t* *\n");
printf("\t\t\t* 1.大整数的加法 *\n");
printf("\t\t\t* 2.大整数的减法 *\n");
printf("\t\t\t* 3.大整数的乘法 *\n");
printf("\t\t\t* 4.退出 *\n");
printf("\t\t\t* *\n");
printf("\t\t\t**************************************\n");
printf("\n\n\t\t\t 请选择（1－4）：");
scanf("%d",&i);
while((tmp=fgetc(stdin))!='\n');
switch(i)
{
case 1:
printf("输入加法算式：");
inscanf('+',num1,num2);
if(check(num1)==1 || check(num2)==1)
break;
start=clock();
BigNumsAdd(num1,num2);
end=clock();
printf("时间是%f\n",(double)(end-start)/CLOCKS_PER_SEC/1000);
system("pause");
break;
case 2:
printf("输入减法算式：");
inscanf('-',num1,num2);
if(check(num1)==1 || check(num2)==1)
break;
start=clock();
BigNumsSub(num1,num2);
end=clock();
printf("时间是%f\n",(double)(end-start)/CLOCKS_PER_SEC/1000);
system("pause");
break;
case 3:
printf("输入乘法算式：");
inscanf('*',num1,num2);
if(check(num1)==1 || check(num2)==1)
break;
start=clock();
BigNumsMul(num1,num2);
end=clock();
printf("时间是%f\n",(double)(end-start)/CLOCKS_PER_SEC/1000);
system("pause");
break;
case 4:
free(num1);
free(num2);
return 0;
default:
printf("输入错误！\n");
}
printf("\n");
}
}