#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>

typedef struct node {
    int coef;
    int exp;
    struct node* rlink;
    struct node* llink;
} node;
node *head, *tail, *current, *prev, *temp;

void init_f() {
    head = (node *)malloc(sizeof(node));
    tail = (node *)malloc(sizeof(node));
    head->rlink = tail;
    tail->llink = head;
}

void read_poly(char str[] ){
	int argCount ;
	while (1) {

    	node* newNode = (node*)malloc(sizeof(node));
    	
        argCount = sscanf(str, "%dx^%d%s", &newNode->coef, &newNode->exp, str);
        
        if (argCount >= 2) {  // 成功讀取係數和指數
        
            newNode->llink = tail->llink;  
		    newNode->rlink = tail;         
		    tail->llink->rlink = newNode;  
		    tail->llink = newNode;

            if (argCount == 2) {
				break ;
			}
				
        } else {
        	if(!isdigit(newNode->coef)){
        		newNode->exp = 0;
        		
				newNode->llink = tail->llink;  
			    newNode->rlink = tail;         
			    tail->llink->rlink = newNode;  
			    tail->llink = newNode;
			    
			    break ;
			    
			}else{
//				printf("newNode->coef = %d\n",newNode->coef);
//				printf("isdigit(newNode->coef) = %d",isdigit(newNode->coef));
				
				free(newNode);
            	break ;
			}
            
        }
	}
}

void clear_node(){
	 // 釋放記憶體
    current = head->rlink;
    while (current != tail) {
        temp = current;
        current = current->rlink;
        free(temp);
    }
    free(head);
    free(tail);
}


void show(int p[], int n, int mode){
	int i;
	if(mode == 0){
		printf("\n方程式p(x)= ");
		current = head->rlink;
		while (current != tail) {
			if(abs(current->coef)>1){
				printf("%s%d", current->coef > 1? "":"\b",current->coef);
			}else if(current->coef == -1){
				printf("%s", current->exp == 0? "\b-1":"\b-");
			}
			switch(current->exp){
				case 0: 
					if(current->coef == 1 ) printf("1+");
					else printf("+");
					break;
				case 1:
					printf("x+");
					break;
				default:
					printf("x^%d+",current->exp);
			}
	        current = current->rlink;
	    }
	    printf("\b ");		
	    
	}else { /* mode==1，顯示所得解 */ 
		for (i = 0; i < n; i++) printf("%d、",p[i]);
		if (n > 0) printf("\b\b  ");
	}
	
}

int findRoot(int q[]) /* 找根，所得解存入q[]，回傳根的個數 */ 
{
	int r, c = 0, i, j, k, sum;
	int sign[2] = {1,-1};
	
	current = tail->llink;
	r = abs(current->coef);				/* 取出最低階項之係數 */
	
	if (current->exp != 0) { /* 最低階項的指數 >= 1，則0為可能解 */ 
		if ((i = current->exp) > 0) q[c++] = 0;	/* 最低階項的指數設為i */
		current = head->rlink;
		while(current!=tail){
			current->exp -= i; /* 所有項次的指數減去i */ 
			current = current->rlink;
		}
	}
	
	
//	r = abs(p[2*p[0]]);				/* 取出最低階項之係數 */

	for (i = 1; i <= r; i++) {		/* 考慮能整除r的因數i，須注意正負號 */ 
		if (r%i != 0) continue;		/* 不能整除r的i將略過，繼續考慮下一個i */ 
		
		for (j = 0; j < 2; j++) {	/* j為0，代表考慮+i的情境；j為1，代表考慮-i的情況 */
			for (sum = 0, current = head->rlink ; current!= tail ; current = current->rlink)	/* 計算每一項的結果值(係數*x^指數)並累加到sum之中 */ 
				sum += current->coef *(int)(pow(sign[j]*i,current->exp));
			if (sum == 0) q[c++] = sign[j]*i;  /* bingo! 發現合乎條件的整數根，將其寫入q陣列 */ 
		}
	}
	
	return c;
}


int main() {
    char str[100];
    int poly_num , *q ,c , high;
    init_f();

    printf("\n*** 解多項式之整數根 ***\n\n輸入多項式 ==> ");
    
    if (fgets(str, sizeof(str), stdin) == NULL) {
        printf("輸入錯誤！\n");
        return 1;
    }


/*	
		1x^2-100x^0
		1x^3-2x^2-1x^1+2x^0
		1x^3-7x^2+4x^1+12x^0
		1x^4+3x^3-66x^2+52x^1+120x^0
		3x^4+9x^3-198x^2+156x^1+360x^0
		1x^2-1x^1
		2x^ 3 -201 x^2+ 97 x^1 +300
		2x^12-195x^11-500x^10
		6x^4 - 1x^3 -25x^2 + 4x^1 + 4 
		1x^5-1x^3-1x^2-1x^1+1x^0
		1x^5+1x^3+1x^2+1x^1+1x^0
		1x^3+1x^0
*/ 
	
    read_poly(str);
    
    current = head->rlink;
	high= current->exp;
    
	show(q,c,0);
	
	q = (int *)malloc((high + 1) *sizeof(int)); /* p[1]紀錄最高階項之指數，依此值創建足夠元素空間的陣列存放所求得的整數根 */ 
	
	c = findRoot(q);
	
	if (c > 0) {
		printf("\n\n解得整數根為：");
		show(q,c,1);  
	}
	else
		printf("\n\n整數根不存在\n");
		
    
    
	clear_node();
   

    return 0;
}