#include <stdlib.h>
#include <string.h>
#define MAX_EXPONENT 100
#define MAX_POLYNOMIAL 100
typedef struct POLYNOMIAL_NODE {
unsigned int number;
short *coeff;
unsigned short *exp;
} polynomial_t;
polynomial_t* generate_from_list(short *exp_coeff, int len)
{
polynomial_t *ret = NULL;
short *coeffs;
unsigned short *exps;
int cnt = 0;
int i, j;
for (i = 0; i < len; i++)
{
if (exp_coeff[i] != 0)
{
cnt++;
}
}
if (cnt == 0)
{
cnt = 1;// return 0
}
ret = (polynomial_t *)calloc(sizeof(polynomial_t), 1);
if (NULL == ret)
{
return NULL;
}
coeffs = (short *)calloc(sizeof(short), cnt);
exps = (unsigned short *)calloc(sizeof(unsigned short), cnt);
if (NULL == coeffs || NULL == exps)
{
return NULL;
}
j = 0;
for (i = 0; i < len; i++)
{
if (exp_coeff[i] != 0)
{
coeffs[j] = exp_coeff[i];
exps[j++] = i;
}
}
ret->number = cnt;
ret->coeff = coeffs;
ret->exp = exps;
return ret;
}
polynomial_t* polynomial_multip(polynomial_t *p1, polynomial_t *p2)
{
short exp_coeff[MAX_EXPONENT] = { 0 };
int i, j;
for (i = 0; i < p2->number; i++)
{
for (j = 0; j < p1->number; j++)
{
exp_coeff[p1->exp[j] + p2->exp[i]] += p1->coeff[j] * p2->coeff[i];
}
}
return generate_from_list(exp_coeff, MAX_EXPONENT);
}
polynomial_t* polynomial_add(polynomial_t *p1, polynomial_t *p2)
{
short exp_coeff[MAX_EXPONENT] = { 0 };
int i, j;
for (i = 0; i < p1->number; i++)
{
exp_coeff[p1->exp[i]] += p1->coeff[i];
}
for (i = 0; i < p2->number; i++)
{
exp_coeff[p2->exp[i]] += p2->coeff[i];
}
return generate_from_list(exp_coeff, MAX_EXPONENT);
}
polynomial_t* polynomial_sub(polynomial_t *p1, polynomial_t *p2)
{
short exp_coeff[MAX_EXPONENT] = { 0 };
int i, j;
for (i = 0; i < p1->number; i++)
{
exp_coeff[p1->exp[i]] += p1->coeff[i];
}
for (i = 0; i < p2->number; i++)
{
exp_coeff[p2->exp[i]] -= p2->coeff[i];
}
return generate_from_list(exp_coeff, MAX_EXPONENT);
}
void polynomial_free(polynomial_t *p)
{
if (!p)
{
return;
}
if (p->exp)
{
free(p->exp);
}
if (p->coeff)
{
free(p->coeff);
}
free(p);
}
void polynomial_print(polynomial_t *p)
{
int i;
char sym;
char py[16];
if (!p)
{
return;
}
printf("polynomial<%p>, total %d:\n", p, p->number);
for (i = 0; i < p->number; i++)
{
memset(py, 0, 16);
if (p->coeff[i] < 0)
{
if (p->exp[i] == 0)
{
sprintf(py, "%d", p->coeff[i]);
}
else if (p->exp[i] == 1)
{
if (p->coeff[i] == -1)
{
sprintf(py, "-x");
}
else
sprintf(py, "%dx", p->coeff[i]);
}
else
{ if (p->coeff[i] == -1)
{
sprintf(py, "-x^%d", p->exp[i]);
}
else
sprintf(py, "%dx^%u", p->coeff[i], p->exp[i]);
}
}
else
{
char* tmp = py;
if (i > 0)
{
tmp[0] = '+';
tmp++;
}
if (p->exp[i] == 0)
{
sprintf(tmp, "%d", p->coeff[i]);
}
else if (p->exp[i] == 1)
{
if (p->coeff[i] == 1)
{
sprintf(tmp, "x");
}
else
sprintf(tmp, "%dx", p->coeff[i]);
}
else
{
if (p->coeff[i] == 1)
{
sprintf(tmp, "x^%d", p->exp[i]);
}
else
sprintf(tmp, "%dx^%d", p->coeff[i], p->exp[i]);
}
}
printf("%s", py);
}
printf("\n");
}
polynomial_t* polynomial_power(polynomial_t *p1, polynomial_t *p2)
{
short exp_coeff[MAX_EXPONENT] = { 0 };
int i, j;
int exp = 0;
polynomial_t *ret;
polynomial_t *tmp;
if (p2->number != 1)
{
printf("polynomial power only support number\n");
return NULL;
}
exp = p2->coeff[0];
if (exp == 0)
{
exp_coeff[0] = 1;
return generate_from_list(exp_coeff, MAX_EXPONENT);
}
else if (exp < 0)
{
printf("polynomial power only support positive exponal\n");
return NULL;
}
if (exp == 1)
{
return p1;
}
ret = p1;
tmp = NULL;
while (exp > 1)
{
ret = polynomial_multip(ret, p1);
if (tmp)
{
polynomial_free(tmp);
}
tmp = ret;
exp--;
}
return ret;
}
char* parse_polynomial(char *str, polynomial_t **ptr)
{
char *cur = str;
polynomial_t *ret = NULL;
short exp_coeff[2] = { 0 };
short coeff = 0;
if (*cur == 'x')
{
exp_coeff[1] = 1;
ret = generate_from_list(exp_coeff, 2);
*ptr = ret;
return ++cur;
}
while (*cur >= '0' && *cur <= '9')
{
coeff = coeff * 10 + (*cur - '0');
cur++;
}
exp_coeff[0] = coeff;
ret = generate_from_list(exp_coeff, 2);
*ptr = ret;
return cur;
}
polynomial_t* polynomial_comput(char *str)
{
char symstack[MAX_POLYNOMIAL] = { 0, };
int symhead = -1;
polynomial_t *pstack[MAX_POLYNOMIAL] = { NULL };
int phead = -1;
polynomial_t *opt1;
polynomial_t *opt2;
polynomial_t *ret;
char optch;
char *cur;
if (!str)
{
return NULL;
}
cur = str;
while (*cur != '\0')
{
if (*cur == 'x' || (*cur >= '0' && *cur <= '9'))
{
cur = parse_polynomial(cur, &pstack[++phead]);
continue;
}
else
{
switch (*cur)
{
case '(':
symstack[++symhead] = *cur;
break;
case '^':
if (symhead >= 0 && symstack[symhead] == '^')
{
optch = symstack[symhead--];
opt2 = pstack[phead--];
opt1 = pstack[phead--];
ret = polynomial_power(opt1, opt2);
pstack[++phead] = ret;
symstack[++symhead] = *cur;
polynomial_free(opt2);
polynomial_free(opt1);
}
else
{
symstack[++symhead] = *cur;
}
break;
case '*':
if (symhead >= 0 && (symstack[symhead] == '^' || symstack[symhead] == '*'))
{
optch = symstack[symhead--];
opt2 = pstack[phead--];
opt1 = pstack[phead--];
if (optch == '^')
ret = polynomial_power(opt1, opt2);
else
ret = polynomial_multip(opt1, opt2);
pstack[++phead] = ret;
symstack[++symhead] = *cur;
polynomial_free(opt2);
polynomial_free(opt1);
}
else
{
symstack[++symhead] = *cur;
}
break;
case '+':
case '-':
if (symhead >= 0 & symstack[symhead] != '(')
{
optch = symstack[symhead--];
opt2 = pstack[phead--];
opt1 = pstack[phead--];
if (optch == '^')
ret = polynomial_power(opt1, opt2);
else if (optch == '*')
{
ret = polynomial_multip(opt1, opt2);
}
else if (optch == '+')
{
ret = polynomial_add(opt1, opt2);
}
else if (optch == '-')
{
ret = polynomial_sub(opt1, opt2);
}
pstack[++phead] = ret;
symstack[++symhead] = *cur;
polynomial_free(opt2);
polynomial_free(opt1);
}
else
symstack[++symhead] = *cur;
break;
case ')':
while (symhead >= 0 && symstack[symhead] != '(')
{
optch = symstack[symhead--];
opt2 = pstack[phead--];
opt1 = pstack[phead--];
if (optch == '^')
ret = polynomial_power(opt1, opt2);
else if (optch == '*')
{
ret = polynomial_multip(opt1, opt2);
}
else if (optch == '+')
{
ret = polynomial_add(opt1, opt2);
}
else if (optch == '-')
{
ret = polynomial_sub(opt1, opt2);
}
pstack[++phead] = ret;
}
if (symstack[symhead] != '(')
{
printf("miss match of ')'\n");
return NULL;
}
symhead--;
break;
default:
break;
}
cur++;
}
}
while (symhead >= 0)
{
optch = symstack[symhead--];
opt2 = pstack[phead--];
opt1 = pstack[phead--];
if (optch == '^')
{
ret = polynomial_power(opt1, opt2);
}
else if (optch == '*')
{
ret = polynomial_multip(opt1, opt2);
}
else if (optch == '+')
{
ret = polynomial_add(opt1, opt2);
}
else if (optch == '-')
{
ret = polynomial_sub(opt1, opt2);
}
pstack[++phead] = ret;
polynomial_free(opt2);
polynomial_free(opt1);
}
if (phead != 0)
{
printf("error : %d\n", phead);
polynomial_print(pstack[phead]);
return NULL;
}
return pstack[0];
}
int main(int argc, char **argv)
{
polynomial_t *pyn;
char src[32] = "(x+1)^2^2-(x-x)^3+((x-1)*(x-1))";
pyn = polynomial_comput(src);
polynomial_print(pyn);
return 0;
}