include stdio include conio include string Constants define STR_INPUT_

#include <stdio.h>
#include <conio.h>
#include <string.h>

//* *********
//* Constants
//* *********

#define STR_INPUT_FILE  "Input.txt"
#define STR_OUTPUT_FILE "Output.txt"
#define STR_BUFFER_SIZE 128

//* ****************
//* Type definitions
//* ****************

typedef struct list
{
	float koeff;
	char * variables;
	float * powers;
	list * next;
} element;

//* ********************
//* Function definitions
//* ********************
//* List methods

inline element * NewList(void)
{ return NULL; }

void DeleteList(element * source)
{
	element * p;
	while(source)
	{
		p=source;
		source=source->next;
		delete [] p->variables;
		delete [] p->powers;
		delete p;
	}
}

void PrintList(element * source,FILE * fpout)
{
	int i, len;
	fprintf(fpout,"// --- Echo ---\n");
	if(!source) fprintf(fpout,"! List is empty\n");
	else 
		while(source)
		{
			fprintf(fpout,"*  Koeff: %+3.2f, Variables: %s, Powers: (",source->koeff,source->variables);
			len=strlen(source->variables);
			for(i=0; i<len; i++)fprintf(fpout," %3.2f",source->powers[i]);
			fputs(" )\n",fpout);
			source=source->next;
		}
	fprintf(fpout,"// --- ---- ---\n");
}

element * NewElement(element * source, float koeff, char * variables, float * powers)
{
	element * ptr=new element;
	ptr->koeff=koeff;
	ptr->variables=variables;
	ptr->powers=powers;
	if(source)
	{
		ptr->next=source->next;
		source->next=ptr;
	} else
		ptr->next=NULL;
	return ptr;
}

element * NewElementEx(element ** source, float koeff, char * variables, float * powers)
{
	element * ptr=new element;
	ptr->koeff=koeff;
	ptr->variables=variables;
	ptr->powers=powers;
	ptr->next=*source;
	*source=ptr;
	return ptr;
}

void DeleteElement(element * source)
{
	element * h=source->next;
	source->next=h->next;
	delete [] h->variables;
	delete [] h->powers;
	delete h;
}

void DeleteElementEx(element ** source)
{
	element * h=*source;
	*source=h->next;
	delete [] h->variables;
	delete [] h->powers;
	delete h;
}

//* Parse & process methods

bool FloatArrayCompare(float * ptr1, float * ptr2, int size)
{
	bool result=true;  
	if(ptr1!=ptr2)							 // Same address in pointers - return true
	while(--size>=0 && result)
		if(ptr1[size]!=ptr2[size])
			result=false;
	return result;
}

int FloatArrayFindValue(float * ptr, float value, int size)
{
	while(--size>=0 && ptr[size]!=value);
	return size;                            // Returns -1 if there is no same element in array
}

void Process(element ** source, float koeff, char * variables, float * powers)
{
	int len = strlen(variables),i,j;
	char ch;
	float f;

	if(koeff==0) return;

	// Cut same symbols and sum their powers
	for(i=0; i<len; i++)
		for(j=i+1; j<len; )
			if(variables[i]==variables[j])
			{
				powers[i]+=powers[j];
				variables[j]=variables[len-1];
				powers[j]=powers[len-1];
				variables[len-1]='\0';
				len--;
			} else j++;
		
	// If any zero powers were found - erase them
	for(i=0; i<len;)
		if(powers[i]==0.)
		{
			powers[i]=powers[len-1];
			variables[i]=variables[len-1];
			variables[len-1]='\0';
			len--;
		} else i++;

	// Sort arrays. The key is a variable letter
	for(j=len-1; j>0; j--)
		for(i=0; i<len-1; i++)
			if(variables[i]>variables[i+1]) 
			{
				ch=variables[i];
				variables[i]=variables[i+1];
				variables[i+1]=ch;

				f=powers[i];
				powers[i]=powers[i+1];
				powers[i+1]=f;
			}


	// Search for existing elements
	bool found = false;
	element * current = *source;

	while(current && !found)
	{
		if(!strcmp(current->variables,variables) && FloatArrayCompare(current->powers,powers,len))
		{
			current->koeff+=koeff;
			found=true;
		}
		current=current->next;
	}
	if(!found)
	{
		char * str = new char [len+1];
		float * ptr = new float [len];
		strcpy(str,variables);
		while(--len>=0)
			ptr[len]=powers[len];
		NewElementEx(source,koeff,str,ptr);
	}
}

element * Parse(void)
{
	element * ptr=NewList();
	FILE * fpin=fopen(STR_INPUT_FILE,"r");
	if(fpin)
	{
		char  str[STR_BUFFER_SIZE]="";
		float pow[STR_BUFFER_SIZE];
		float koeff=1.0,
			  f;
		char  buff=fgetc(fpin),
			  sign='+';
		int i=0;

		// Check for any +/- before first member or for empty file
		while(buff==' ') buff=fgetc(fpin);
		if(buff==EOF) koeff=0.; 
		else if(buff=='-' || buff=='+') sign=buff;
		else fseek(fpin,-1,1);

		// Main parse loop
		buff=fgetc(fpin);
		while(buff!=EOF)
		{			
			if(buff!=' ' && buff!=EOF && buff!='*')
			if(buff=='-' || buff=='+')
			{
				if(sign=='-') koeff *= -1;
				Process(&ptr,koeff,str,pow);
				// Set defaults
				koeff=1.0;
				str[0]='\0';
				i=0;
				sign=buff;
			}
			else if(buff=='.' || buff>='0' && buff<='9')
			{
				fseek(fpin,-1,1);	
				fscanf(fpin,"%f",&f);
				koeff*=f;
			}
			else if(buff=='^')	fscanf(fpin,"%f",&pow[i-1]);
			else {
				str[i]=buff;
				str[i+1]='\0';
				pow[i++]=1.0;
			}
			buff=fgetc(fpin);
		}

		if(sign=='-') koeff *= -1;
		Process(&ptr,koeff,str,pow);

		fclose(fpin);
	} else perror("! Can not open source file");
	return ptr;
}

//* Output method

int Output(element * source)
{
	FILE * fpout=fopen(STR_OUTPUT_FILE,"w");
	if(fpout)
	{
		int i;
		char * str;
		float * ptr;
		while(source)
		{
			if(source->koeff)
			{
				str=source->variables;
				ptr=source->powers;
				fprintf(fpout," % +.2f",source->koeff);
				for(i=0; str[i]!='\0'; i++)
				{
					fprintf(fpout,"*%c",str[i]);
					if(ptr[i]!=1.)
						fprintf(fpout,"^%.2f",ptr[i]);
				}
			}
			source=source->next;
		}
		if(!ftell(fpout)) fputc('0',fpout);
		fclose(fpout);
	} else perror("! Can not write output file");	
	return fpout!=NULL;
}


//* *************
//* Main function
//* *************

int main()
{
	element * h=Parse();
	Output(h);
	DeleteList(h);
	return 0x0;
}