jjg.cpp

实现大整数加减法运算

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<math.h>
#include <iostream>
using namespace std;
#define MAX_SIZE (1024)

char answer[MAX_SIZE];
char answersign;
char t='+';

void bigadd(char * n1, char * n2);
void bigsub(char * n1, char * n2);
void bigmul(char * n1, char * n2);

void bigtrim(char * num, int length);
void bigsort(char * n1, char * n2, int maxlen);
void printnum(char * num);



void bigadd(char * n1, char * n2)          //加法运算
{
    int bit1, bit2, bit3, carry = 0,borrow=0;
    int i;
    char *n3;
	
	
       answersign = '+';
       if(t=='-')                        //负整数加上正整数，即为正整数减去正整数
	   {
		   if(strcmp(n1,n2)>0)           //使n1小于n2
		   {
			   n3=n1;
			   n1=n2;
			   n2=n3;               
		   }
		   else answersign = '-';         
		   for (i = 0; i < MAX_SIZE; i++)
		   {
				if (n1[i] >= '0' && n1[i] <= '9')        //把字符型转换成int型
				{
					bit1 = n1[i] - '0';
				} 
	    		else 
				{
					bit1 = 0;
				}
				if (n2[i] >= '0' && n2[i] <= '9')
				{
					 bit2 = n2[i] - '0';
				} 
	    		else 
				{
				bit2 = 0;
				}
				bit3 = (bit2 - bit1 - borrow + 10) % 10;
				borrow = (bit2 - bit1 - borrow < 0) ? 1 : 0;
				answer[i] = '0' + bit3;
				if (n1[i] == '\0' && n2[i] == '\0')
				{
					i++;
					break;
				}
			}
	   }
	   else                             //正整数加上正整数
	   {
			for (i = 0; i < MAX_SIZE; i++) 
			{
				if (n1[i] >= '0' && n1[i] <= '9')        //把字符型转换成int型
				{
				 bit1 = n1[i] - '0';
				}
    			else 
				{
					bit1 = 0;
				}
				if (n2[i] >= '0' && n2[i] <= '9') 
				{
					bit2 = n2[i] - '0';
				}
	    		else
				{
					bit2 = 0;
				}
				bit3 = (bit1 + bit2 + carry) % 10;
				carry = (bit1 + bit2 + carry >= 10) ? 1 : 0;
				answer[i] = '0' + bit3;
				if (n1[i] == '\0' && n2[i] == '\0') 
				{	
					i++;
					break;
				}
			}
	   }
    answer[i] = '\0';
    return;
}

void bigsub(char * n1, char * n2)          //减法运算
{
    int bit1, bit2, bit3,carry=0,borrow = 0;
    int i;
    if(t=='-')                            //负整数减去正整数，为其绝对值相加，再取负
	{
		for (i = 0; i < MAX_SIZE; i++) 
			{
				if (n1[i] >= '0' && n1[i] <= '9')      //把字符型转换成int型
				{
				 bit1 = n1[i] - '0';
				}
    			else 
				{
					bit1 = 0;
				}
				if (n2[i] >= '0' && n2[i] <= '9') 
				{
					bit2 = n2[i] - '0';
				}
	    		else
				{
					bit2 = 0;
				}
				bit3 = (bit1 + bit2 + carry) % 10;
				carry = (bit1 + bit2 + carry >= 10) ? 1 : 0;
				answer[i] = '0' + bit3;
				if (n1[i] == '\0' && n2[i] == '\0') 
				{	
					i++;
					break;
				}
			}
		answersign='-';
	}
	else{                            //正整数减去正整数
    for (i = 0; i < MAX_SIZE; i++)
	{
        if (n1[i] >= '0' && n1[i] <= '9')        //把字符型转换成int型
		{
            bit1 = n1[i] - '0';                  
        } 
	    	else 
			{
            bit1 = 0;
			}
        if (n2[i] >= '0' && n2[i] <= '9')
		{
            bit2 = n2[i] - '0';
        } 
	    	else 
			{
            bit2 = 0;
			}
        bit3 = (bit2 - bit1 - borrow + 10) % 10;
        borrow = (bit2 - bit1 - borrow < 0) ? 1 : 0;
        answer[i] = '0' + bit3;
        if (n1[i] == '\0' && n2[i] == '\0')
		{
            i++;
            break;
        }
    }
	}
    answer[i] = '\0';
    return;
}

void bigmul(char * n1, char * n2)        //乘法运算
{
    int bit1, bit2, bit3, carry;
    int len1, len2, maxlen;
    int i, j, k;
    char space[2][MAX_SIZE];
    
    answersign = '+';

    answer[0] = '0';
    answer[1] = '\0';

    for (i = 0; i < MAX_SIZE; i++) 
	{
        if (n1[i] == '\0') {
            break;
        }
        carry = 0;
		   for (j = 0; j < MAX_SIZE; j++)
		   {
		        if (n2[j] == '\0') {break;}
		        bit1 = n1[i] - '0';                //把字符型转换成int型
		        bit2 = n2[j] - '0';
			    bit3 = (bit1 * bit2 + carry) % 10;
			    carry = (bit1 * bit2 + carry) / 10;
				space[1][i + j] = '0' + bit3;
		    }
			  for (k = 0; k < i; k++) 
			  {
				   space[1][k] = '0';
			  }
        space[1][i + j] = '0' + carry;
        space[1][i + j + 1] = '\0';
        strcpy(space[0], answer);

        len1 = strlen(space[0]);
        len2 = strlen(space[1]);
        maxlen = (len1 > len2) ? len1 : len2;
        bigtrim(space[0], maxlen);
        bigtrim(space[1], maxlen);
        bigadd(space[0], space[1]);
    }
    return;
}
/* 比较2个大整数的大小,返回true表示前者大于等于后者*/
bool isBig(const string& str1, const string& str2)
{
		if ( str1.size() > str2.size() )
			{return true;}
		else 
			if ( str1.size() < str2.size() )
				{return false;}
		else 
			if ( str1.size() == str2.size() )
			{
				 for (int i = 0; i < str1.size(); ++i)
				{
					  if ( str1[i] > str2[i] ){return true;}
						else
							if ( str1[i] < str2[i] ){return false;}
				}
			}
			return true;
}

/* 翻转字符串 */
void reverseStr(string& str)
{
		for (int i = 0; i < str.size()/2; ++i)
		{
			 char tmp = str[i];
			 str[i] = str[str.size()-1 - i];
			 str[str.size()-1 -i] = tmp;
		}
}

/* 去除字符串起始多余的'0' */
string deleteZero(const string& str)
{
		string rst;
		int i = 0;
		while ( str[i] == '0' ){++i;}
		for (; i < str.size(); ++i)
		{
		  rst += str[i];
		}
		return rst; 
}

/* 2个大整数相减 */
string doSubtract(const string& str1, const string& str2)
{
		string rst;
		int c = 0; //最开始的借位
		int i;
		for (i = str2.size()-1; i >=0; --i)
		{
			  if ( str1[str1.size() - str2.size() +i] -c >= str2[i] )
			  {
			   rst += (str1[str1.size() - str2.size() +i] - str2[i] - c)%10 + '0';
			   c = 0;
			 }
			 else
			  {
				  rst += (str1[str1.size() - str2.size() +i] + 10 -str2[i] -c)%10 + '0';
				  c = 1;
				}
		}
				if ( int(str1.size() - str2.size() +i) >= 0 )
				{
				   rst += (str1[str1.size() - str2.size() +i] -'0' - c)%10 + '0';
				  --i;
				}
					while ( int(str1.size() - str2.size() + i) >= 0 )
					{
						rst += str1[str1.size() - str2.size() +i];
						--i;
					}	
				reverseStr(rst); //翻转过来
				rst = deleteZero(rst); //去除起始的0
				return rst;
}

/* 大整数的0~9倍 */
string multiply(const string& str, int n)
{
		string rst;
		int c = 0; //进位
		for (int i = str.size()-1; i >= 0; --i)
		{
			  rst += ((str[i]-'0') *n +c) % 10 + '0';
			  c = ( (str[i]-'0') *n +c ) / 10;
		}
		if ( c > 0 )
		{
			  rst += c + '0';
		}
		reverseStr(rst);
		return rst;
}

/* 大整数除法 */
string bigDiv(const string& str1, const string& str2, string& str3)
{
		string afterStr1 = deleteZero(str1); //被除数预处理后，去除起始可能的'0'
		string afterStr2 = deleteZero(str2); //除数与处理后，去除起始可能的'0'
		string rst; //保留商
		if ( isBig(afterStr1, afterStr2) == false ) //如果被除数本身就小于除数，直接返回
		{
			 str3 = afterStr2; //余数
			 rst = "0"; //商0
			 return rst;
		}

		string str; //和除数相同长度的串
		int i;
		for (i = 0; i < afterStr2.size(); ++i)
		{
		  str += afterStr1[i];
		}

		  do
			{
				 for ( int j = 9; j >= 1; --j)
				 {
					  if ( (isBig(str, multiply(afterStr2, j)) == false) &&
							  (isBig(str, multiply(afterStr2, j-1)) == true ) )
						 {
							 rst += j-1 + '0'; //本次商 j-1
							 str = doSubtract(str, multiply(afterStr2, j-1));
							 break;
						  }
				  }
  
				 int len = str.size();  
				 for (int k =0; (k < afterStr2.size() - len) && (i < afterStr1.size()); ++k)
					 {
						  str += afterStr1[i];
						  ++i;
						 if ( isBig(str, afterStr2) == false )
						 {
							   rst += '0'; //本次商 0
							}
					 }
				 if ( (isBig(str, afterStr2) == false) && (i < afterStr1.size()) ) //当被除数和除数位数相等但被除数小于除数时，补位
					 {
						  str += afterStr1[i];
						  ++i;
					  }
			}
			while ( i < afterStr1.size() );

			for ( int j = 9; j >= 1; --j)
			{
				 if ( (isBig(str, multiply(afterStr2, j)) == false) &&
				 (isBig(str, multiply(afterStr2, j-1)) == true ) )
				  {
					   rst += j-1 + '0'; //本次商 j-1
					  str = doSubtract(str, multiply(afterStr2, j-1));
					  break;
				 }
			}
			str3 = str; //最后的余数
			rst = deleteZero(rst);
			
			return rst;
}


void bigsort(char * n1, char * n2, int maxlen)  //使 n1 <= n2.
{
    int i, j;
    char temp;

    answersign = '+';

    for (i = maxlen - 1; i >= 0; i--)
    {
        if (n1[i] == n2[i]) {
            continue;
        }
        if (n1[i] > n2[i]) {
            for (j = 0; j < maxlen; j++) {
                temp = n1[j];
                n1[j] = n2[j];
                n2[j] = temp;
            }
            answersign = '-';
        }
        break;
    }
    return;
}

void bigtrim(char * num, int length)             //运算结果的存贮
{
    int len;
    int i, j, k;

    len = strlen(num);

    for (i = 0; i < len; i++) 
	{
        if (num[i] == '\0') {  break; }
    }
    for (j = i - 1; j >= 0; j--)
	{
        if (num[j] == '0') {
            num[j] = '\0';
        } 
		else {  break;  }
    }
    if (num[0] == '\0') 
	{
        num[0] = '0';
    }
    if (length > 0) 
	{
        for (k = i + 1; k <= length; k++) 
		{
            num[k] = '\0';
        }
    }
    return;
}

void printnum(char * num)        //输出函数
{
    int len;
    int i;   
    
    if (answersign == '-')        //运算结果为负值时
	{
        printf("-");
    }
	
    bigtrim(num, 0);              
    len = strlen(num);	        //计算出结果的长度
    for (i = len - 1; i >= 0; i--) {
        printf("%c", num[i]);
    }
    return;
}

int main()
{
    int index, place;
    int len, len1, len2, len3,len4,maxlen;
    int i,j,k=0,u=0;
	char t1='+';
	char t2='+';
    char input[MAX_SIZE * 2], num[2][MAX_SIZE];
	char r='*';
	char chu[2][1024];
	string str1;
	string str2;
	string rst; //保留商
	string str; //保留余数
	
	

    printf("\t\t\t大整数的加减乘除法运算\n");
	printf("\t本程序是一个大整数加减法运算，例如:\n\t加法运算，请输入1254+2654后回车，加减运算相同;\n\t乘除运算：直接输入123*456或者123*-456。\n\t当要退出时请输入0，谢谢使用本程序！\n");
		printf("开始：");

    void (* func)(char *, char *);
	
 
while (1) 
	{
        scanf("%s", &input);
		len = strlen(input);
		
		if(input[0]=='-')       //加减法运算出现 （负整值+整数）时
		{
            t='-';
			for(i=0;i<(MAX_SIZE * 2);i++)
			{

				input[i]=input[i+1];
			}
		}
		if(input[0]=='0'&&len==1)          //输入的表达式为0时，退出程序
		return 0;

        len = strlen(input);
        index = 0;
        place = 0;
        for (i = 0; i < len; i++)
		{
			if((input[i]=='*'||input[i]=='/')&&input[i+1]=='-')
			{
				t2='-';
				for(j = i; j < (MAX_SIZE * 2); j++)
				{

					input[j+1]=input[j+2];
				}
				len = strlen(input);
				
			}
			if(t2=='-')	break;
		}


        for ( i = len - 1; i >= 0; i--)
		{
            if (input[i] == '+' || input[i] == '-' || input[i] == '*'||input[i]=='/')//辨别乘以正整数还是负整数
			{
                if (input[i] == '+')
				{
                    func = bigadd;
                } 
				else
					if (input[i] == '-') 
					{
                        func = bigsub;
					}
					else 
						if (input[i] == '*') 
						{
							if(t=='-')
							{
								t1=t;                       //因为乘法要调用到加法，所以负整数的标志要先识别出来
								t='+';
							}

                            func = bigmul;
						}
						else
							if(input[i]=='/')
							{
								for( j = 0; j < len; j++)
								{
									if(r=='*'&&input[j]!='/')
									chu[0][j]=input[j];
									if(r=='*'&&input[j]=='/'){r='/';chu[0][j]='\0';}
									if(r=='/'&&input[j]!='/')
									{
										chu[1][k]=input[j];
											k++;
									}
								}
								chu[1][k]='\0';
								len1 = strlen(chu[0]);
								len2= strlen(chu[1]);
							    str1=chu[0];
								str2=chu[1];
								rst = bigDiv(str1, str2, str);
								printf("商为：");
								if(  t == '-'&&  t2 == '+')                    //判别乘除运算的结果是否为负整数
									printf("-");
								if(  t2 == '-'&&  t == '+')
									printf("-");
								j=0;
								while(rst[j]!='\0')
								{
									printf("%c",rst[j]);j++;
								}
								printf("\n");
								printf("余数为：");
								if(  t == '-'&&  t2 == '+')                    //判别除法运算余数是否为负整数
									printf("-");
								if(  t2 == '-'&&  t == '+')
									printf("-");
								j=0;
								while(str[j]!='\0')
								{
									printf("%c",str[j]);j++;
								}
								printf("\n");
								goto loop;
							}

				num[0][place] = '\0';
                index = 1;
                place = 0;
            }
			else 
			{
                num[index][place++] = input[i];
            }
        }
		
        num[1][place] = '\0';

        len1 = strlen(num[0]);
        len2 = strlen(num[1]);
        maxlen = (len1 > len2) ? len1 : len2;           //两个数的长度比较，取长的，循环时的次数标志
        bigtrim(num[0], maxlen);
        bigtrim(num[1], maxlen);
       
        if (func == bigsub) 
		{
            bigsort(num[0], num[1], maxlen);
        }
		
        func(num[0], num[1]);
		printf("值为：");
		if(  t1 == '-'&&  t2 == '+')                    //判别乘除运算的结果是否为负整数
			printf("-");
		if(  t2 == '-'&&  t1 == '+')
			printf("-");
        printnum(answer);
        printf("\n");
        t='+';
		t1='+';
		t2='+';
		
loop:   printf("");
		
    }
    
    return 0;
}