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

#define BUFFSIZE 128

typedef struct _exp { //Integral expression
    int n; //Max of order
    int *k;//coefficient list(array)# k[0] as constant, k[n] as x^n
} Exp;


void print(Exp *exp);
const char *extract(const char *str, char *outbuff);
Exp *makeExp(const char *str);
void freeExp(Exp *exp);
Exp *convert(const char *str);
Exp *mul(Exp *a, Exp *b);
Exp *calc(const char *expStr);

int main(){
    char buff[BUFFSIZE];
    Exp *exp;
    printf("input expression Eg.(x+1)(x+3)\n>");
    fgets(buff, sizeof(buff)/sizeof(char), stdin);
    exp=calc(buff);
    print(exp);
    freeExp(exp);

    return 0;
}

void print(Exp *exp){
    int i, n = exp->n;
    for(i=n;i>=0;--i){
        int k = exp->k[i];
        if(k==0)continue;
        if(k<0)
            printf("-");
        if(k>0 && i!=n)
            printf("+");
        if(k<0) k*=-1;//k=|k|
        if(i!=0){
            if(k!=1)
                printf("%dx", k);
            else
                printf("x");
        }
        if(i>1)
            printf("^%d", i);
        if(i==0)
            printf("%d", k);
    }
    printf("\n");
}


const char *extract(const char *str, char *outbuff){
//pull out in parenthesis to outbuff, and remove space
    while(isspace(*str))
        ++str;
    if(*str=='\0') return NULL;
    while(*str!='(')++str;
    while(*++str!=')')
        if(!isspace(*str))
            *outbuff++=*str;
    *outbuff='\0';
    return ++str;
}

Exp *makeExp(const char *str){
    Exp *exp;
    char buff[BUFFSIZE];
    exp = (Exp*)malloc(sizeof(Exp));
    exp->n = 0;
    exp->k = (int*)calloc(1,sizeof(int));
    while(*str){
        int k,n;
        char *p;
        k=(int)strtol(str, &p, 10);
        if(k==0){//never constant zero e.g(x+0)is invalid, valid E.g (x)
            if(p[0]=='-'){
                k = -1;
                ++p;
            } else if(p[0]=='+') {
                k = 1;
                ++p;
            } else 
                k = 1;
        }
        if(*p=='\0'){
            exp->k[0]=k;//constant part
            break;
        }
        if(*p=='x'){
            n = (p[1]=='^') ? (int)strtol(&p[2], &p, 10):1;
            if(exp->n < n){
                int i;
                exp->k = (int*)realloc(exp->k, (n+1)*sizeof(int));
                for(i=n;i>exp->n;--i)
                    exp->k[i]=0;
                exp->n = n;
            }
            exp->k[n] = k;
            if(*p=='\0' || p[1]=='\0')break;
            else{
                str = (n!=1)? p:p+1;
            }
        } else {
            exp->k[0]=k;
            str = p;
        }
    }
    return exp;
}

void freeExp(Exp *exp){
    free(exp->k);
    free(exp);
}

Exp *convert(const char *str){
    Exp *exp;
    exp=makeExp(str);
    return exp;
}

Exp *mul(Exp *a, Exp *b){
    Exp *ret;
    int i,j;
    ret=(Exp*)malloc(sizeof(Exp));
    ret->n = a->n + b->n;
    ret->k = (int*)calloc(ret->n + 1, sizeof(int));
    for(i=0;i<=a->n;++i){
        for(j=0;j<=b->n;++j){
            ret->k[i+j] += a->k[i] * b->k[j];
        }
    }
    return ret;
}

Exp *calc(const char *expStr){
    Exp *exp;
    char buff[BUFFSIZE];
    const char *p=expStr;
    exp = (Exp*)malloc(sizeof(Exp));
    exp->n = 0;
    exp->k = (int*)malloc(sizeof(int));
   *exp->k = 1;
    while(NULL!=(p=extract(p, buff))){
        Exp *e,*wk;
        wk=exp;
        e=convert(buff);
        exp=mul(wk, e);
        freeExp(wk);
        freeExp(e);
    }
    return exp;
}