Demo entry 6356430

lll

   

Submitted by anonymous on Apr 18, 2017 at 13:54
Language: C++. Code size: 19.6 kB.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<stdbool.h>
#include<string.h>

#define INTEGER 2
#define REALNUM 1
#define NORMAL 0
#define LONGLONG 222
#define DOUBLE 111

struct Node {
	double coeffi;
	int order;
	struct Node* next;
}**Polyhead;

typedef long long LL;

int Transform(char* expr, int num);
int prior(char ch);
void AddSub(struct Node*, struct Node*, struct Node*, int);
double *multiplication(const double *p, const double *q, int n);
void MultiplicationNTT(struct Node* polya, struct Node* polyb, struct Node* result);
void PrintLink(struct Node* poly);
void input(struct Node* poly);
void AddSub(struct Node* polya, struct Node* polyb, struct Node* result, int Mode);
LL mod(LL a, LL b, LL m);
int bit_reverse(int n, int len);
void Index_ini(LL *poly, int len);
void IterativeNTT(LL *poly, int len, int on);
void Convolution(LL *polya, LL *polyb, int length);
double *add(const double *a, const double *b, double *c, int n);
double *sub(const double *a, const double *b, double *c, int n);
void Multiplicationlg3(struct Node* polya, struct Node* polyb, struct Node* result);
void Execute(char *expr, int exprind);
void SolveExpression(void);
void LinktoArrayLL(struct Node* polya, struct Node* polyb, LL* poly1, LL* poly2, LL length);
void LinktoArrayDL(struct Node* polya, struct Node* polyb, double* poly1, double* poly2, LL length);
void Order(struct Node* head);


const int DIGITNUM = 40;
const int PRIME = (479 << 21) + 1;//to implement the NTT
const int PRIM_ROOT = 3;    //the primitive root we choose

//2 is NTT which need integer coefficient
//1 is a O(n^lg3) algorithm which receive nonnegtive exponential
//0 is a normal multiplication
int NUMMODE;


//print the linked list
void PrintLink(struct Node* poly)
{
	int count = 0;
	while (poly != NULL) {
		if (count != 0)
			printf("+ ");
		if (poly->coeffi == 0) {
			poly = poly->next;
			continue;
		}
		else if (poly->order == 0)
			printf("%.2lf ", poly->coeffi);
		else
			printf("%.2lfx^%d ", poly->coeffi, poly->order);
		poly = poly->next;
		++count;
		//every ninth element end a line
		if (count % 6 == 0)
			putchar('\n');
	}
	//when all the coefficients are 0
	if (count == 0)
		printf("0\n");
	putchar('\n');
}
//read the input and store them in a linked list
void input(struct Node* poly)
{
	char ch;
	while (scanf("%lf%d", &poly->coeffi, &poly->order)) {
		//ch is used to determine whether the input come to the end
		ch = getchar();
		if (ch == '\n') {
			poly->next = NULL;
			break;
		}
		else {
			poly->next = (struct Node*)malloc(sizeof(struct Node));
			poly = poly->next;
		}
	}
}
//Implement the addition and subtraction operation.When Mode is 1,it's addition,0 otherwise
void AddSub(struct Node* polya, struct Node* polyb, struct Node* result, int Mode)
{
	for(int i=0;;++i){
		if (polya != NULL&&polyb != NULL) {
			//Choose the values of order and coefficient which are to be assigned
			result->order = polya->order > polyb->order ? polya->order : polyb->order;
			result->coeffi = polya->order > polyb->order ? polya->coeffi :
				polya->order == polyb->order ? (Mode ? polya->coeffi + polyb->coeffi : polya->coeffi - polyb->coeffi) :
				Mode ? polyb->coeffi : -polyb->coeffi;
			if (polya->order == polyb->order) {
				polya = polya->next;
				polyb = polyb->next;
			}
			else if (polya->order > polyb->order)
				polya = polya->next;
			else if (polyb->order > polya->order)
				polyb = polyb->next;
		}
		//one linked list come to the end
		else if (polya != NULL&&polyb == NULL) {
			result->order = polya->order;
			result->coeffi = polya->coeffi;
			polya = polya->next;
		}
		else if (polya == NULL&&polyb != NULL) {
			result->order = polyb->order;
			result->coeffi = Mode ? polyb->coeffi : -polyb->coeffi;
			polyb = polyb->next;
		}
		//come to the end and end the loop
		if (polya == NULL&&polyb == NULL) {
			if (i)
				result = NULL;
			else
				result->next = NULL;
			break;
		}
		//allocate memories for the new element
		else {
			result->next = (struct Node*)malloc(sizeof(struct Node));
			result = result->next;
			result->next = NULL;
		}
	}
}

/////////////////////////////////////////////////////////////////////////////////////////
//Multtiplication using Fast Fourier Transformation based on Number Theory Transformation
//Because it's somewhat difficult to implement the array of complex number
//NTT's time complextity is nlgn

//The main step.We know the multiplication of polynomials is equal to compute the
//convolution of coefficients.
void Convolution(LL *polya, LL *polyb, int length)
{
	IterativeNTT(polya, length, 1);
	IterativeNTT(polyb, length, 1);
	for (int i = 0; i < length; i++)
		polya[i] = polya[i] * polyb[i] % PRIME;
	IterativeNTT(polya, length, -1);
}
//find the a^b modulo m
LL mod(LL a, LL b, LL m)
{
	LL ans = 1;
	a %= m;
	while (b) {
		if (b & 1) {
			ans = ans * a % m;
			b--;
		}
		b >>= 1;
		a = a * a % m;
	}
	return ans;
}
//To reverse the bits that represent the n.For example,4 is 100,and its reverse is 001
int bit_reverse(int n, int len)
{
	int re = 0;
	while (len > 1) {
		re = (re << 1) | n & 1;
		n >>= 1;
		len >>= 1;
	}
	return re;
}
//To rearrange the order to implement the iterative version of FTT
void Index_ini(LL *poly, int len)
{
	int *list;
	list = (int *)calloc(len, sizeof(int));
	for (int i = 0; i < len; ++i) {
		if (list[i])
			continue;
		int re = bit_reverse(i, len);
		//swap poly[i] and poly[re]
		LL tp = poly[i];
		poly[i] = poly[re];
		poly[re] = tp;
		list[re] = 1;
	}
}
//
void IterativeNTT(LL *poly, int len, int on)
{
	//rearrange the order of data
	Index_ini(poly, len);
	for (int h = 2; h <= len; h <<= 1) {
		//the initial modulus value
		int wn = mod(PRIM_ROOT, (PRIME - 1) / h, PRIME);
		for (int j = 0; j < len; j += h) {
			LL w = 1;
			for (int k = j; k < j + h / 2; k++) {
				LL u = poly[k] % PRIME;
				LL t = w * poly[k + h / 2] % PRIME;
				poly[k] = (u + t) % PRIME;
				poly[k + h / 2] = (u - t + PRIME) % PRIME;
				w = w * wn % PRIME;
			}
		}
	}
	//To implement the inverse operation
	if (on == -1) {
		for (int i = 1; i < len / 2; i++) {
			LL tp = poly[i];
			poly[i] = poly[len - i];
			poly[len - i] = tp;
		}
		LL inv = mod(len, PRIME - 2, PRIME);
		for (int i = 0; i < len; i++)
			poly[i] = poly[i] * inv % PRIME;
	}
}

void MultiplicationNTT(struct Node* polya, struct Node* polyb, struct Node* result)
{
	struct Node* pp = result;
	LL length, *poly1, *poly2, ini = 1;
	int count = 0;
	length = polya->order > polyb->order ? polya->order : polyb->order;
	//in order to implement NTT,we need length which is the power of 2
	while (length > ini)
		ini <<= 1;
	length = ini * 2;
	poly1 = (LL*)malloc(sizeof(LL)*length);
	poly2 = (LL*)malloc(sizeof(LL)*length);
	LinktoArrayLL(polya, polyb, poly1, poly2, length);
	//compute
	Convolution(poly1, poly2, length);
	//transform the information to linked list
	for (int i = length - 1; i >= 0; --i)
		if (poly1[i] != 0) {
			result->order = i;
			result->coeffi = poly1[i];
			result->next = (struct Node*)malloc(sizeof(struct Node));
			result = result->next;
			++count;
		}
	//let the final element points to NULL
	for (int i = 0; i < count - 1; ++i)
		pp = pp->next;
	if (count) {
		free(pp->next);
		pp->next = NULL;
	}
	else
		*result = { 0,0,NULL };
}
///////////////////////////////////////////////////////
//To solve the multiplication when coefficients are real number,we choose a O(n^lg3) algorithm
//given (Ax+B)(Cx+D),the main idea is to compute AC,BD and (A+B)(C+D)
//Thus the recursive fomula is T(n)=3T(n/2)+O(n)

//add a and b,return the value in c
double *add(const double *a, const double *b, double *c, int n)
{
	for (int i = 0; i < n; ++i)
		c[i] = a[i] + b[i];
	return c;
}
//substract a by b,return the value in c
double *sub(const double *a, const double *b, double *c, int n)
{
	for (int i = 0; i < n; ++i)
		c[i] = a[i] - b[i];
	return c;
}
double *multiplication(const double *p, const double *q, int n)
{
	if (n == 1) {
		double *x;
		x = (double*)malloc(sizeof(double));
		*x = *p**q;
		return x;
	}
	int m = n - n / 2;
	double *e, *f;
	e = (double*)malloc(sizeof(double)*m);
	f = (double*)malloc(sizeof(double)*m);
	const double *a = m + p, *b = p, *c = m + q, *d = q;
	double *tmp1, *tmp2, *tmp3, *final;
	final = (double*)calloc(2 * n - 1, sizeof(double));
	//compute (A+B)(C+D)
	tmp1 = multiplication(add(a, b, e, m), add(c, d, f, m), n - m);
	//compute AC
	tmp2 = multiplication(a, c, n - m);
	//compute BD
	tmp3 = multiplication(b, d, m);
	//the final expression which is more clear in pesudocode
	add(final + n, tmp2, final + n, 2 * (n - m) - 1);
	add(final, tmp3, final, 2 * m - 1);
	add(final + m, sub(sub(tmp1, tmp2, tmp1, 2 * (n - m) - 1), tmp3, tmp1, 2 * (n - m) - 1), final + m, 2 * (n - m) - 1);
	return final;
}
void Multiplicationlg3(struct Node* polya, struct Node* polyb, struct Node* result)
{
	int length = polya->order > polyb->order ? polya->order : polyb->order, ini = 1;
	//count is in order to find the last element in list
	int count = 0;
	struct Node* pp = result;
	while (length > ini)
		ini <<= 1;
	length = ini;
	//transform the information to array
	double *poly1, *poly2, *re;
	poly1 = (double*)malloc(sizeof(double)*length);
	poly2 = (double*)malloc(sizeof(double)*length);
	LinktoArrayDL(polya, polyb, poly1, poly2, length);
	//compute the result
	re = multiplication(poly1, poly2, length);
	//transform the information to linked list
	for (int i = 2 * length - 2; i >= 0; --i) {
		if (re[i] != 0) {
			result->order = i;
			result->coeffi = re[i];
			result->next = (struct Node*)malloc(sizeof(struct Node));
			result = result->next;
			++count;
		}
	}
	//find the last element
	for (int i = 0; i < count - 1; ++i)
		pp = pp->next;
	if (count) {
		free(pp->next);
		pp->next = NULL;
	}
	else
		*result = { 0,0,NULL };
}
////////////////////////////////////////////////////////////
//A normal multiplication
void NormalMultiplication(struct Node* polya, struct Node* polyb, struct Node* result) {
	struct Node* Initial = result;
	struct Node* Inipolyb = polyb;
	bool first = false;
	while (polya != NULL) {
		//relocate the polyb and result to their head
		polyb = Inipolyb;
		result = Initial;
		while (polyb != NULL) {
			int neworder = polya->order + polyb->order;
			int newcoef = polya->coeffi*polyb->coeffi;
			while (first == true && result->next != NULL&&neworder < result->next->order)
				result = result->next;
			//because the imformation in linked list is in a decreasing order,so the first is max.
			if (first == false) {
				result->coeffi = newcoef;
				result->order = neworder;
				result->next = NULL;
				first = true;
			}
			//the latter is always less than the first
			else if (neworder < result->order) {
				//skip the element
				while (result->next != NULL&&neworder > result->next->order)
					result = result->next;
				if (result->next != NULL) {
					//if next element is equal to neworder
					if (result->next->order == neworder) {
						result = result->next;
						result->order = neworder;
						result->coeffi = newcoef;
					}
					//if next element is less than neworder
					else if (neworder > result->next->order) {
						struct Node* tp = result->next;
						result->next = (struct Node*)malloc(sizeof(struct Node));
						result->next->next = tp;
						result = result->next;
						result->coeffi = newcoef;
						result->order = neworder;
					}
				}
				//if next element is NULL
				else if (result->next == NULL) {
					result->next = (struct Node*)malloc(sizeof(struct Node));
					result = result->next;
					result->next = NULL;
					result->coeffi = newcoef;
					result->order = neworder;
				}
			}
			//next polyb
			polyb = polyb->next;
		}
		//next polya
		polya = polya->next;
	}
}
//release the memories of list
void FreeList(struct Node* poly) {
	while (poly!= NULL) {
		if (poly->next != NULL) {
			struct Node* tmp = poly->next;
			free(poly);
			poly = tmp;
		}
		else {
			free(poly);
			poly = NULL;
		}
	}
}
//use postfix to determine the order of operation
void Execute(char *expr, int exprind)
{
	int *digit, digitnum = 0;
	digit = (int*)malloc(sizeof(int) * DIGITNUM);
	for (int i = 0; i < exprind; ++i) {
		//if expr[i] is digit,store it in a stack
		if (isdigit(expr[i]))
			digit[digitnum++] = expr[i] - '0';
		else {
			struct Node *tp = NULL;
			tp = (struct Node*)malloc(sizeof(struct Node));
			if (expr[i] == '+')
				AddSub(Polyhead[digit[digitnum - 2]], Polyhead[digit[digitnum - 1]], tp, 1);
			else if (expr[i] == '-')
				AddSub(Polyhead[digit[digitnum - 2]], Polyhead[digit[digitnum - 1]], tp, 0);
			else if (expr[i] == '*') {
				//choose the multiplication mode
				if (NUMMODE == REALNUM)
					Multiplicationlg3(Polyhead[digit[digitnum - 2]], Polyhead[digit[digitnum - 1]], tp);
				else if (NUMMODE == INTEGER)
					MultiplicationNTT(Polyhead[digit[digitnum - 2]], Polyhead[digit[digitnum - 1]], tp);
				else if (NUMMODE == NORMAL)
					NormalMultiplication(Polyhead[digit[digitnum - 2]], Polyhead[digit[digitnum - 1]], tp);
			}
			//After operation,the number of digits in stack should decrease by 1
			--digitnum;
			//replace last two digit with 0 which is the result
			digit[digitnum - 1] = 0;
			//release memory
			FreeList(Polyhead[0]);
			Polyhead[0] = tp;
		}
	}
}
void SolveExpression(void)
{
	char expr[100], ch;
	bool iscorrect = true;
	while ((ch = getchar()) != 'q') {
		int exprind = 1;
		expr[0] = ch;
		//ch store the infix information
		while ((ch = getchar()) != '\n') {
			expr[exprind++] = ch;
			//examine whether the exprssion is true
			if (!isdigit(ch) && (ch != '+' && ch != '-' && ch != '*'&&ch != '('&&ch != ')')) {
				iscorrect = false;
				while ((ch = getchar()) != '\n');
				break;
			}
		}
		if (iscorrect == false) {
			printf("The expression is false!Enter the next.\n");
			iscorrect = true;
			continue;
		}
		//transform infix to postfix and substract exprind by the number of '(' and ')'
		exprind = Transform(expr, exprind);
		Execute(expr, exprind);
		//print the result
		PrintLink(Polyhead[0]);
	}
}
int main(void)
{
	printf("Enter the number of the polynomials you want(less than 9)\n");
	int n;
	scanf("%d", &n);
	printf("If your coefficients are integers and nonnegetive and exponentials are nonnegtive,enter 2\n");
	printf("If your coefficients are real numbers and nonnegtive and exponentials are nonnegtive,enter 1\n");
	printf("Otherwise enter 0\n");
	scanf("%d", &NUMMODE);
	Polyhead = (struct Node**)malloc(sizeof(struct Node*)*(n + 1));
	for (int i = 0; i < n + 1; ++i)
		Polyhead[i] = (struct Node*)malloc(sizeof(struct Node));
	Polyhead[0] = NULL;
	printf("Please enter the polynomials.\n");
	printf("Ensure the polynomial is ordered.\n");
	printf("Each item end with an enter\n");
	printf("To end your input, press enter twice.\n");
	printf("For example: 5 10 3 6 -2 3 6 0 7 -4(enter)\n");
	printf("Which means \"5x10 + 3x6 - 2x3 + 6 + 7x(-4)\"\n");
	for (int i = 1; i <= n; ++i) {
		input(Polyhead[i]);
		//sort the input
		Order(Polyhead[i]);
		if (i < n)
			printf("Now enter the other\n");
	}
	printf("Now enter the operations you want.\n");
	printf("Just like 1+2 or (1+2)*3, i means the ith polynomial.\n");
	printf("Enter q to quit.\n");
	SolveExpression();
}

//tranform the information in linked list to array of long long type
void LinktoArrayLL(struct Node* polya, struct Node* polyb, LL* poly1, LL* poly2,LL length) {
	for (int i = length - 1; i >= 0; --i) {
		if (polya != NULL&&polya->order == i) {
			poly1[i] = polya->coeffi;
			polya = polya->next;
		}
		else
			poly1[i] = 0;
		if (polyb != NULL&&polyb->order == i) {
			poly2[i] = polyb->coeffi;
			polyb = polyb->next;
		}
		else
			poly2[i] = 0;
	}
}
////tranform the information in linked list to array of double type
void LinktoArrayDL(struct Node* polya, struct Node* polyb, double* poly1, double* poly2, LL length) {
	for (int i = length - 1; i >= 0; --i) {
		if (polya != NULL&&polya->order == i) {
			poly1[i] = polya->coeffi;
			polya = polya->next;
		}
		else
			poly1[i] = 0;
		if (polyb != NULL&&polyb->order == i) {
			poly2[i] = polyb->coeffi;
			polyb = polyb->next;
		}
		else
			poly2[i] = 0;
	}
}
//return the priority of '-' ,'+' and '*'
int prior(char ch)
{
	if (ch == '-' || ch == '+')
		return 1;
	else if (ch == '*')
		return 2;
}


//Transform infix into postfix which is easier to operate
//e.g. 1+3*(4-5)  ->  1345-*+
int Transform(char* expr, int num)
{
	int count = num;
	char *re, *opelist;
	re = (char*)malloc(sizeof(char)*num);
	opelist = (char*)malloc(sizeof(char)*num);
	int numind = 0, opeind = 0;
	for (int i = 0; i < num; ++i) {
		if (isdigit(expr[i]))
			re[numind++] = expr[i];
		else {
			//the list is empty
			if (opeind == 0)
				opelist[opeind++] = expr[i];
			//store '(' in stack
			else if (expr[i] == '(') {
				opelist[opeind++] = expr[i];
				--count;
			}
			else if (expr[i] == ')') {
				//read all the information until meet '('
				while (opelist[opeind - 1] != '(')
					re[numind++] = opelist[opeind-- - 1];
				--opeind;
				--count;
			}
			//if it's priority is larger than the previous one,store it in stack
			else if (prior(expr[i]) > prior(opelist[opeind - 1]))
				opelist[opeind++] = expr[i];
			//if it's priority is equal to the previous one,put the previous one 
			//in the result and store it in stack
			else if (prior(expr[i]) == prior(opelist[opeind - 1])) {
				re[numind++] = opelist[opeind - 1];
				opelist[opeind - 1] = expr[i];
			}
			//if it's priority is less than previous one,
			else if (prior(expr[i]) < prior(opelist[opeind - 1])) {
				while (opelist[opeind - 1] != '('&&opeind)
					re[numind++] = opelist[opeind-- - 1];
				opelist[opeind++] = expr[i];
			}
		}
	}
	//if opeind is larger than 0,store the remaining information in stack to result
	if (opeind)
		while (opeind)
			re[numind++] = opelist[opeind-- - 1];
	//let the value in expr equal to result
	for (int i = 0; i < num; ++i)
		expr[i] = re[i];
	return count;
}

void Order(struct Node* head)
{
	struct Node* ptr;
	struct Node temp;//the temporary struct
	struct Node* toDelete;//store the deleted node
	int flag;
	//if there is only one element
	if (head->next == NULL)
		return;
	while (1){
		flag = 0;
		ptr = head;
		//bubble sort
		while (1){
			if (ptr->order < ptr->next->order)
			{
				flag++;
				temp.order = ptr->next->order;
				temp.coeffi = ptr->next->coeffi;
				ptr->next->order = ptr->order;
				ptr->next->coeffi = ptr->coeffi;
				ptr->order = temp.order;
				ptr->coeffi = temp.coeffi;
				ptr = ptr->next;
			}
			else
				ptr = ptr->next;
			if (ptr->next == NULL)
				break;
			else;
		}
		if (flag == 0)
			break;
	}
	//幂次相同的项合并
	ptr = head;
	while (1){
		if (ptr->order == ptr->next->order){
			ptr->coeffi = ptr->coeffi + ptr->next->coeffi;
			toDelete = ptr->next;
			ptr->next = ptr->next->next;
			free(toDelete);
		}
		else{
			ptr = ptr->next;
		}

		if (ptr == NULL || ptr->next == NULL)
			break;
		else;
	}
}

This snippet took 0.05 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).