renjing.cpp~

#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "math.h"
#include "bits/stdc++.h"
//using namespace std;

#define maxn1 100 //最多能存储100个多项式
#define maxn2 1000 //每个多项式最多有1000项
#define esp 1e-6

//多项式:a0 + a1*x^1 + a2*x^2 + a3*x^3 + ... + an*x^n
int a[maxn1][maxn2];//系数数组,用来储存系数
int x[maxn1][maxn2];//阶数数组,用来储存阶数
int num=0;


//初始化界面
void initialization(){
    printf("----------");
    printf("Welcome to RenJing's Polynome-Home");
    printf("----------\n");
    printf("\n");

    printf("Here are some options for you:\n");
    printf("\n");

    printf("+   addition operation\n");
    printf("-   subtraction operation\n");
    printf("*   multiplication operation\n");
    printf("/   divsion operation\n");
    printf("d   differentiate operation\n");
    printf("e   evaluation operation\n");
    printf("f   factorisation operation\n");
    printf("q   quit Polynome-Home\n");
    printf("\n");
    
    printf("Please input corresponding operation(+,-,*,/,d,e,f,q),ending with pressing Enter-key:\n");
}
//循环读入并格式化poly字符串
bool format();

//加法运算
void addition();
//减法运算
void subtraction();
//乘法运算
void multiplication();
//除法运算
void divsion(double *quotient_a,int *quotient_x,bool is_output=true);
//微分运算
void differentiate();
//估算
double evaluation(double value);
//因式分解
void factorisation();
//退出程序
void quit();

//#define test
int main(){
#ifdef test
	freopen("data.txt","r",stdin);
#endif
	//界面
    initialization();
    while(1){
        memset(a,0,sizeof(a));//在进行任何操作前，都初始化系数数组
        memset(x,0,sizeof(x));//在进行任何操作前，都初始化阶数数组
        
        printf(">");
        //输入要进行的操作  
        char operation;
        scanf("%c",&operation);
        getchar();
//        cout << "input:" << operation << endl;
        switch(operation){
            case '+'://多个相加
		        printf("You can input at most 100 polynomes ending with 'EOF'\n");
				printf("Please input polynomes pressing Enter-key after each one:\n");
	   			num=0;//将多项式的个数初始化为0；
				for(int i=0;i<100;i++){//循环读入多个poly
					if(format()==false) break;//如果用来读入字符串的函数返回的是false,结束输入
				}
		        addition();break;
            
            case '-'://两个相减
            	printf("You can input at most 2 polynomes\n");
				printf("Please input polynomes pressing Enter-key after each one:\n");
		   		num=0;//将多项式的个数初始化为0；
				for(int i=0;i<2;i++){//循环读入2个poly
					if(format()==false) break;//如果用来读入字符串的函数返回的是false,结束输入
				} 
            	subtraction();break;
            	
            case '*'://多个相乘
            	printf("You can input at most 100 polynomes ending with 'EOF'\n");
				printf("Please input polynomes pressing Enter-key after each one:\n");
	   			num=0;//将多项式的个数初始化为0；
				for(int i=0;i<100;i++){//循环读入多个poly
					if(format()==false) break;//如果用来读入字符串的函数返回的是false,结束输入
				}
            	multiplication();break;
            case '/':
            	printf("You can input at most 2 polynomes\n");
				printf("Please input polynomes pressing Enter-key after each one:\n");
		   		num=0;//将多项式的个数初始化为0；
				for(int i=0;i<2;i++){//循环读入2个poly
					if(format()==false) break;//如果用来读入字符串的函数返回的是false,结束输入
				}
				double quotient_a[maxn2];
				int quotient_x[maxn2];
            	divsion(quotient_a,quotient_x);break;
                      
            case 'd'://单个估值运算
            	printf("You can input at most 1 polynomes\n");
				printf("Please input polynomes pressing Enter-key after each one:\n");
		   		num=0;//将多项式的个数初始化为0；
				for(int i=0;i<1;i++){//循环读入1个poly
					if(format()==false) break;//如果用来读入字符串的函数返回的是false,结束输入
				}
            	differentiate();break;
            	
            case 'e':          	
            	printf("You can input at most 1 polynomes\n");
				printf("Please input polynomes pressing Enter-key after it:\n");
		   		num=0;//将多项式的个数初始化为0；
		   		
				if(format()==false) break;//如果用来读入一个字符串的函数返回的是false,结束输入
				printf("Please input x=");
				double value;
				scanf("%lf",&value);
				getchar();
            	printf("The result is: %lf",evaluation(value));break; 	
            	
        	case 'f': 
        	
        		printf("You can input at most 1 polynomes\n");
				printf("Please input polynomes pressing Enter-key after it:\n");
		   		num=0;//将多项式的个数初始化为0；
		   		
		   		if(format()==false) break;//如果用来读入一个字符串的函数返回的是false,结束输入
            	factorisation();break;
            case 'q': 
            	quit();break;
            default: break;
        }
        printf("\nPlease input the next operation(+,-,*,/,d,e,f,q):\n");
    }
    return 0;
}

bool format(){

    //本部分用于读入poly，并预处理poly字符串
    char poly[maxn1*maxn2];//用来完整储存输入的多项式
    memset(poly,0,sizeof(poly));//清空ploy
    poly[0]='+';//在poly[0]的位置放置+，以便之后的处理
    int cnt=1;//格式化poly最后一个字符的位置
    int flag=0;//标记段
    int i,j,k;//循环的临时索引
    
    while(1){//循环读入字符串并进性格式化
        char ch;
        scanf("%c",&ch);//读入单个字符ch
        if(ch=='X') ch='X';
        if(ch=='e') ch='E';
        if(ch=='o') ch='O';
        if(ch=='f') ch='F';
        if(ch=='\n'){//如果ch是回车字符，那么结束输入

            if(poly[cnt-1]=='F'){
                flag=1;
            }

            if(poly[cnt-1]=='x'){
                poly[cnt++]='^';
                poly[cnt++]='1';
            }

            if(flag==0){
                poly[cnt++]='x';
                poly[cnt++]='^';
                poly[cnt++]='0';
            }

            poly[cnt]='\0';
            cnt++;
            break;
        }

        if(ch=='x'){
            flag=1;
        }
        
        if(ch==' ') continue;//如果ch是空白符，那么跳过处理，并进行下一次循环

        if((poly[cnt-1]=='+'&&ch=='-')||(poly[cnt-1]=='-'&&ch=='+')){//出现+-,-+,分别变成-,-
            poly[cnt-1]='-';
            continue;
        }else if((poly[cnt-1]=='+'&&ch=='+')||(poly[cnt-1]=='-'&&ch=='-')){//出现++,--分别变成+,+
            poly[cnt-1]='+';
            continue;
        }else if((poly[cnt-1]=='+'&&ch=='x')||(poly[cnt-1]=='-'&&ch=='x')){//出现+x,-x分别变成+1x,-1x
            poly[cnt++]='1';
            poly[cnt++]='x';
            continue;
        }else if((poly[cnt-1]=='x'&&ch=='+')||(poly[cnt-1]=='x'&&ch=='-')){//出现x+,x-分别变为x^1+,x^1-
        	flag=0;
            poly[cnt++]='^';
            poly[cnt++]='1';
            poly[cnt++]=ch;
            continue;       
        }

    
        if((ch=='+'&&flag==0)||(ch=='-'&&flag==0)){
            poly[cnt++]='x';
            poly[cnt++]='^';
            poly[cnt++]='0';
            flag=0;
        }
        if(ch=='+'||ch=='-'){
            flag=0;
        }

        poly[cnt++]=ch;
    }
    
    if(strcmp("+EOF",poly)==0){//输入EOF直接退出函数，并返回false
    	return false;
    }else if(strcmp("+x^0",poly)==0){//输入 回车  直接退出函数，并返回true
        return true;
    }

//    puts(poly);

    //本部分进行再处理,将字符串poly分隔成多段str，分别进行处理
    int temp_a[maxn2];//系数临时矩阵
    int temp_x[maxn2];//阶数临时矩阵
    memset(temp_a,0,sizeof(temp_a));
    memset(temp_x,0,sizeof(temp_x));
    int index=0;//记录项数
    
    
    for(i=0;i<strlen(poly);i++){
        char symbol;//用来存贮系数的正负号
        char str[maxn2];
        memset(str,0,sizeof(str));
        symbol=poly[i++];
//            cout << symbol << endl;        

        for(j=0;poly[i+j]!='-'&&poly[i+j]!='+'&&i+j<strlen(poly);j++);
        strncpy(str,poly+i,j);
        i=i+j-1;
        
//        puts(str);

        {//用来处理str，分割系数，阶数 example: 199x^10
            //阶数
            int times=1;//倍数
            for(k=strlen(str)-1;str[k]!='^';k--){
                temp_x[index]+=(str[k]-'0')*times;
                times*=10;
            }

            //系数
            times=1;
            for(k=k-2;k>=0;k--){
                temp_a[index]+=(str[k]-'0')*times;
                times*=10;
            }
            if(symbol=='-') temp_a[index]=-temp_a[index];//如果系数符号是-，那么取反

            index++;
        }
    }
    
    
    //本部分将temp_a,temp_x分别转存到a,x数组中，并且合并同阶项，从小到大升幂排列
    //num表示当前poly的标号，初始化是0；'
    
    for(i=0;temp_a[i]!=0;i++);
    for(j=i;j>0;j--){//将temp_a,temp_x数组整体后移一位
        temp_a[j]=temp_a[j-1];
        temp_x[j]=temp_x[j-1];
    }
    temp_a[0]=i;//temp_a[0]，存储多项式项数
    temp_x[0]=i;//同上

    for(i=1;i<=temp_x[0];i++){//阶数从大到小排列
        for(j=i;j<=temp_x[0];j++){
            if(temp_x[i]<temp_x[j]){
                int t;
                t=temp_x[i];
                temp_x[i]=temp_x[j];
                temp_x[j]=t;

                t=temp_a[i];
                temp_a[i]=temp_a[j];
                temp_a[j]=t;

            }
        }
    }

//        for(i=1;i<=temp_a[0];i++) cout << temp_x[i] << ' ';
    a[num][1]=temp_a[1];
    x[num][1]=temp_x[1];
    for(i=2,j=1;i<=temp_x[0];i++){
        if(temp_x[i]==x[num][j]){
            a[num][j]+=temp_a[i];
        }else{
            j++;
            a[num][j]=temp_a[i];
            x[num][j]=temp_x[i];
        }
    }
    a[num][0]=j;x[num][0]=j;
//    for(i=1;i<=a[num][0];i++) cout << a[num][i] << "x^" << x[num][i] << endl;

    num++;//多项式个数+1，进行下一次输入
    
    return true;
}


void addition(){
    
    //开始进行加法运算，累加下标0->num-1的多项式,并将结果放到result数组当中
    int i,j,k;
    int temp[maxn2];
    int result_a[maxn2];//记录系数结果
    int result_x[maxn2];//记录阶数结果
    memset(temp,0,sizeof(temp));
    temp[0]=1;
    for(i=0;i<num;i++){
        for(j=1;j<=x[i][0];j++){
            int flag=0;
            for(k=1;k<=temp[0];k++){
                if(x[i][j]==temp[k]){
                    flag=1;
                    break;
                }
            }
            if(!flag){
                temp[++temp[0]]=x[i][j];
            }

        }
    }

    sort(temp+1,temp+temp[0]+1);//将阶数从大到小排序

//    for(i=0;i<=temp[0];i++) cout << temp[i] << ' ';
//    cout << endl;

    result_a[0]=temp[0];result_x[0]=temp[0];
    for(i=1;i<=temp[0];i++) result_x[i]=temp[i];
    
    for(i=1;i<=result_x[0];i++){
        for(j=0;j<num;j++){
            for(k=1;k<=x[j][0];k++){
                if(x[j][k]==result_x[i]){
                    result_a[i]+=a[j][k];
                }
            }
        }

    }
    
    printf("The result is:\n");
    for(i=1;i<=result_x[0];i++){
    	if(result_a[i]==0) continue;//系数为0,跳过不输出
    	 printf("%dx^%d",result_a[i],result_x[i]);
    	 if(result_a[i+1]>0){
    	 	printf("+");
    	 }
    }
    printf("\n");

}

void subtraction(){
    //第二个多项式取反,调用加法运算即可
    for(int i=1;i<=x[1][0];i++){
    	a[1][i]=-a[1][i];
    }
    
    addition();
}

void multiplication(){
	int temp_a[maxn2];//临时系数矩阵
	int temp_x[maxn2];//临时阶数矩阵
	int result_a[maxn2];//结果系数矩阵
	int result_x[maxn2];//结果阶数矩阵
	
	memset(temp_a,0,sizeof(temp_a));
	memset(temp_x,0,sizeof(temp_x));
	temp_a[0]=1;
	temp_x[0]=1;
	
	memset(result_a,0,sizeof(result_a));
	memset(result_x,0,sizeof(result_x));
	result_a[0]=1;result_a[1]=1;
	result_x[0]=1;result_x[1]=0;
	
	for(int i=0;i<num;i++){
		int cnt=0;
		for(int j=1;j<=x[i][0];j++){
			for(int k=1;k<=result_x[0];k++){
				cnt++;
				temp_a[cnt]=a[i][j]*result_a[k];
				temp_x[cnt]=x[i][j]+result_x[k];
			}
		}
		
		result_a[0]=cnt;
		result_x[0]=cnt;
		temp_a[0]=cnt;
		temp_x[0]=cnt;
		for(int j=1;j<=cnt;j++){
			result_a[j]=temp_a[j];
			result_x[j]=temp_x[j];
		}
//		cout << "cnt" << cnt << endl;
	}
	
	//阶数从小到大排列
	for(int i=1;i<=temp_x[0];i++){
//		cout << temp_x[0] << endl;
        for(int j=i;j<=temp_x[0];j++){
            if(temp_x[i]>temp_x[j]){
                int t;
                t=temp_x[i];
                temp_x[i]=temp_x[j];
                temp_x[j]=t;

                t=temp_a[i];
                temp_a[i]=temp_a[j];
                temp_a[j]=t;

            }
        }
    }

//        for(i=1;i<=temp_a[0];i++) cout << temp_x[i] << ' ';
    result_a[1]=temp_a[1];
    result_x[1]=temp_x[1];
    int i,j;
    for(i=2,j=1;i<=temp_x[0];i++){
        if(temp_x[i]==result_x[j]){
            result_a[j]+=temp_a[i];
        }else{
            j++;
            result_a[j]=temp_a[i];
            result_x[j]=temp_x[i];
        }
    }
    result_a[0]=j;
    result_x[0]=j;
    
    printf("The result is:\n");
    for(i=1;i<=result_x[0];i++){
    	if(result_a[i]==0) continue;//系数为0,跳过不输出
    	 printf("%dx^%d",result_a[i],result_x[i]);
    	 if(result_a[i+1]>0){
    	 	printf("+");
    	 }
    }
    printf("\n");   
}

void divsion(double *quotient_a,int *quotient_x,bool is_output){//is_output用来控制函数是否输出商，余数
	memset(quotient_a,0,sizeof(quotient_a));
	memset(quotient_x,0,sizeof(quotient_x));

	//quotient用来存储商
	quotient_a[0]=0;
	quotient_x[0]=0;
	
	//dividend存储被除数
	int dividend_a[maxn2];
	int dividend_x[maxn2];
	memset(dividend_a,0,sizeof(dividend_a));
	dividend_a[0]=a[0][0];
	dividend_x[0]=x[0][0];
	
	
	//divisor存储除数
	int divisor_a[maxn2];
	int divisor_x[maxn2];
	memset(dividend_a,0,sizeof(divisor_a));
	divisor_a[0]=a[1][0];
	divisor_x[0]=x[1][0];
	
	//dividend阶数从高到低
	for(int i=1;i<=x[0][0];i++){
		dividend_a[i]=a[0][i];
		dividend_x[i]=x[0][i];
		
	}
	
//	for(int i=1;i<=dividend_x[0];i++) cout << dividend_a[i] << "x^" << dividend_x[i] << ' ';
//	cout << endl;
	
	//divisor阶数从高到低
	for(int i=1;i<=x[1][0];i++){
		divisor_a[i]=a[1][i];
		divisor_x[i]=x[1][i];
	}
	
	memset(a,0,sizeof(a));
	memset(x,0,sizeof(x));
	
	//remainder存储余数
	double remainder_a[maxn2];
	memset(remainder_a,0,sizeof(remainder_a));
	int remainder_x[maxn2];
	
	//余数初始化=被除数
	for(int i=0;i<=dividend_x[0];i++){
		remainder_a[i]=dividend_a[i];
		remainder_x[i]=dividend_x[i];
	}	
	
	//temp临时变量,用来储存临时 商和除数 乘积
	double temp_a[maxn2];
	int temp_x[maxn2];
	temp_a[0]=1.0*divisor_a[0];
	temp_x[0]=divisor_x[0];
	

	int flag=0;
	while(1){
//		for(int i=1;i<=remainder_x[0];i++){
//			cout << remainder_a[i] << "x^" << remainder_x[i];
//			if(remainder_a[i]>0){
//				cout << "+";
//			}
//		}
//		cout << endl;
		if(remainder_x[1]==0||remainder_a[1]==0){//整除停止循环
			flag=1;
			break;
		}
		if(remainder_x[1]<divisor_x[1]) break;//没整除，但是余数最高项小于除数最高项，停止循环
		
		quotient_x[0]++;quotient_a[0]++;
		quotient_a[quotient_x[0]]=remainder_a[1]/divisor_a[1]*1.0;//商的系数 
		quotient_x[quotient_x[0]]=remainder_x[1]-divisor_x[1];//商的阶数
		
		//用temp来储存
		for(int i=1;i<=divisor_x[0];i++){
			temp_a[i]=quotient_a[quotient_x[0]]*divisor_a[i]*1.0;
			temp_x[i]=quotient_x[quotient_x[0]]+divisor_x[i];
		}
		
		//remainder=remainder-temp初步产生新的remainder
		for(int i=1;i<=temp_x[0];i++){
			int length=remainder_x[0];
			int flag=0;//记录是否有同类项，假设不存在flag=0
			for(int j=1;j<=length;j++){
				if(temp_x[i]==remainder_x[j]){//如果当前项存在同类项
					flag=1;
					remainder_a[j]=remainder_a[j]-temp_a[i];//合并同类项系数
					break;//终止内循环，检查下一项
				}
			}
			if(!flag){//当前项不存在同类项
				length++;
				remainder_a[length]=-temp_a[i];
				remainder_x[length]=temp_x[i];
				
				remainder_a[0]++;
				remainder_x[0]++;
			}
		}
		
		//对上一步初步产生的remainder消除系数为0的项
		for(int i=1;i<=remainder_x[0];){
			if(remainder_a[i]!=0) i++;//如果当前位不等于0，i++检查下一位
			else{
				for(int j=i;j<remainder_x[0];j++){//第i位等于0，数组第i之后的所有整体前移一位
					remainder_a[j]=remainder_a[j+1];
					remainder_x[j]=remainder_x[j+1];
				}
				remainder_x[0]--;//更新remainder长度
				remainder_a[0]--;
			}
		}
		
		//对上一步产生的remainder进行，阶数从大到小
		for(int i=1;i<=remainder_x[0];i++){
			for(int j=i;j<=remainder_x[0];j++){
				if(remainder_x[i]<remainder_x[j]){//交换值
					double t1;//临时变量
					t1=remainder_a[i];
					remainder_a[i]=remainder_a[j];
					remainder_a[j]=t1;
					
					int t2;
					t2=remainder_x[i];
					remainder_x[i]=remainder_x[j];
					remainder_x[j]=t2;
				}
			}
		}
		
	}
	
	if(is_output){//参数is_putout==true,那么执行输出操作
		printf("The quotient is: ");
		if(quotient_x[0]==0){
			printf("0");
		}else{
			for(int i=1;i<=quotient_x[0];i++){
				printf("%dx^%d",quotient_a[i],quotient_x[i]);
				if(quotient_a[i+1]>0){
					printf("+");
				}
			}
		}
		printf("\n");
		printf("The divisor is: ");
		if(remainder_x[0]==0){
			printf("0");
		}else{
			for(int i=1;i<=remainder_x[0];i++){
				printf("%dx^%d",remainder_a[i],remainder_x[i]);
				if(remainder_a[i+1]>0){
					printf("+");
				}
			}
		}
		printf("\n");
	}	

}

void differentiate(){
	//求导
	for(int i=1;i<=x[num-1][0];i++){
		a[num-1][i]=a[num-1][i]*x[num-1][i];
		x[num-1][i]--;
	}
	
	//输出结果
	printf("The result is:\n");
    for(int i=1;i<=x[num-1][0];i++){
    	if(x[num-1][i]<0) continue;  			
		printf("%dx^%d",a[num-1][i],x[num-1][i]);
		if(a[num-1][i+1]>0){
		 	printf("+");
		}
    }
    printf("\n");
}

double evaluation(double value){
	
	//将x赋值value，并进行运算
	double result=0;
	for(int i=1;i<=x[0][0];i++){
		result+=1.0*a[0][i]*pow(value,x[0][i]);
		
	}
	return result;
	
}

void factorisation(){

	//保存分解因式之后剩余的部分
	double quotient_a[maxn2];//阶数从高到低
	int quotient_x[maxn2];
	
	//a[0],x[0]保存的是需要分解的因式,从高到低
	//a[1],x[1]用来保存当前要处理因式，从高到低
	//temp[maxn][2]来保存所有的因式
	int temp[maxn2][2];
	int cnt=0;//记录因式的数量
	int flag=1;//标记是否分解完全
	while(flag){
		flag=0;
		
		if(x[0][x[0][0]]>0){
			a[1][0]=1;
			a[1][1]=1;
			x[1][0]=1;
			x[1][1]=x[0][x[0][0]];
			temp[cnt][0]=x[0][x[0][0]];
			temp[cnt][1]=0;
			cnt++;
			divsion(quotient_a,quotient_x,false);
			flag=1;
		}else{
			for(int i=abs(a[0][1]);i>=-abs(a[0][1]);i--){
				if(i!=0&&a[0][1]%i==0){
					for(int j=abs(a[0][x[0][0]]);j>=-abs(a[0][x[0][0]]);j--){
						if(j!=0&&a[0][x[0][0]]%j==0){
							double value=-j/i*1.0;
//							cout << i << j << endl;
							if(abs(evaluation(value))<esp){
								flag=1;
								temp[cnt][0]=i;
								temp[cnt][1]=j;
								cnt++;
								a[1][0]=2;x[1][0]=2;							
								a[1][1]=i;x[1][1]=1;
								a[1][2]=j;x[1][2]=0;
								divsion(quotient_a,quotient_x,false);
							}
						}
						if(flag) break;
					}
				}
				if(flag) break;
			}
		}
		
		if(flag){
			memset(a,0,sizeof(a));
			memset(x,0,sizeof(x));
			for(int i=0;i<=quotient_x[0];i++){
				a[0][i]=(int)quotient_a[i];
				x[0][i]=quotient_x[i];
			}
		}	
	}
	
	for(int i=0;i<cnt;i++){
		if(temp[i][1]==0){
//			cout << "(x^" << temp[i][0] << ")*";
			printf("(x^%d)",temp[i][0]);
		}else{
//			cout << "(" << temp[i][0] << "x";
			printf("(%dx",temp[i][0]);
			if(temp[i][1]>0){
				printf("+");
			}
//			cout << temp[i][1] << ")*";
			printf("%d)*",temp[i][1]);
		}
	}
	
	if(a[0][0]>0){
		printf("(");
		for(int i=1;i<=x[0][0];i++){			
//		cout << a[0][i] << "x^" << x[0][i];
			printf("%dx^%d",a[0][i],x[0][i]);
			if(a[0][i+1]>0){
			 	printf("+");
			}
		}
		printf(")");
	}
	
	printf("\n");
}

void quit(){
    printf("Goodbye!\nYou have quit Polynome-Home!\n");
    exit(0);
}