讨论 / 求大神给AC代码~
水果狐工作室RQNOJ账号 2016-12-22 20:17:45
点我顶贴 收藏 删除
求代码求代码~
#1 Black God@2021-12-09 01:22:07
回复 删除
#include <stdio.h>

#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;

}

查看更多回复
提交回复