Juan Céspedes - Computing 

Solved problems from UVa Online Judge 

The Errant Physicist

126.c

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

struct pa {
	int n;
	int x;
	int y;
};

typedef struct {
	int num;
	struct pa part[80];
} line;

void
parse_line(char *buf, line *in) {
	int sign = 1;
	in->num = 0;

	while (1) {
		char *s;
		long int a;

		if (buf[0]=='\0' || buf[0]=='\r' || buf[0]=='\n') {
			break;
		}

		if (buf[0]=='+') {
			buf++;
		} else if (buf[0]=='-') {
			sign *= -1;
			buf++;
		}
		a = strtol(buf, &s, 10);
		if (s==buf) {
			a=1;
		}
		in->part[in->num].n = sign * a;
		buf = s;
		in->part[in->num].x = 0;
		in->part[in->num].y = 0;
		while (buf[0]=='x' || buf[0]=='y') {
			if (buf[0]=='x') {
				++buf;
				a=1;
				if (buf[0]>='0' && buf[0]<='9') {
					a = strtol(buf, &s, 10);
					if (s==buf) {
						a=1;
					}
					buf = s;
				}
				in->part[in->num].x += a;
			}
			if (buf[0]=='y') {
				++buf;
				a=1;
				if (buf[0]>='0' && buf[0]<='9') {
					a = strtol(buf, &s, 10);
					if (s==buf) {
						a=1;
					}
					buf = s;
				}
				in->part[in->num].y += a;
			}
		}
#if DEBUG
		printf("%d * x^%d * y^%d\n", in->part[in->num].n, in->part[in->num].x, in->part[in->num].y);
#endif
		in->num++;
		if (buf[0]=='+') {
			sign = 1;
			buf++;
		} else if (buf[0]=='-') {
			sign = -1;
			buf++;
		}
	}
}

void
multiply(line *in1, line *in2, line *out) {
	int i,j,k;

	out->num = 0;

	for (i=0; i<in1->num; i++) {
		for (j=0; j<in2->num; j++) {
			int done=0;
			for (k=0; k<out->num; k++) {
				if ((out->part[k].x == in1->part[i].x + in2->part[j].x) &&
						(out->part[k].y == in1->part[i].y + in2->part[j].y)) {
					out->part[k].n += in1->part[i].n * in2->part[j].n;
					done=1;
					break;
				}
			}
			if (!done) {
				out->part[out->num].n = in1->part[i].n * in2->part[j].n;
				out->part[k].x = in1->part[i].x + in2->part[j].x;
				out->part[k].y = in1->part[i].y + in2->part[j].y;
				out->num++;
			}
		}
	}
}

int
compar(const void *a, const void *b) {
	struct pa *pa1, *pa2;
	pa1 = (struct pa *)a;
	pa2 = (struct pa *)b;

	if (pa1->x != pa2->x) {
		return pa2->x - pa1->x;
	} else {
		return pa1->y - pa2->y;
	}
}

void
print(line *li) {
	int i;
	char line1[100];
	char line2[100];
	char buf[100];

	memset(line1, ' ', 100);
	line2[0] = '\0';

	qsort(&li->part[0], li->num, sizeof(struct pa), compar);
	if (li->part[0].n < 0) {
		sprintf(line2, "-");
	}
	for (i=0; i<li->num; i++) {
		struct pa *pa = &li->part[i];
		if (pa->n == 0) {
			continue;
		}
		if (i) {
			if (pa->n < 0) {
				strcat(line2, " - ");
			} else {
				strcat(line2, " + ");
			}
		}
		if (abs(pa->n) != 1 || (pa->x==0 && pa->y==0)) {
			sprintf(buf, "%d", abs(pa->n));
			strcat(line2, buf);
		}
		if (pa->x) {
			strcat(line2, "x");
			if (pa->x != 1) {
				sprintf(buf, "%d", pa->x);
				sprintf(line1+strlen(line2), "%s", buf);
				sprintf(line2+strlen(line2), "%*.*s", strlen(buf), strlen(buf), " ");
			}
		}
		if (pa->y) {
			strcat(line2, "y");
			if (pa->y != 1) {
				sprintf(buf, "%d", pa->y);
				sprintf(line1+strlen(line2), "%s", buf);
				sprintf(line2+strlen(line2), "%*.*s", strlen(buf), strlen(buf), " ");
			}
		}
#if 0
		printf(" %dx%dy%d", li->part[i].n, li->part[i].x, li->part[i].y);
#endif
	}
	for (i=0; i<strlen(line2); i++) {
		if (line1[i]=='\0') {
			line1[i]=' ';
		}
	}
	line1[strlen(line2)] = '\0';
	if (strlen(line2)==0) {
		printf(" \n0\n");
	} else {
		printf("%s\n", line1);
		printf("%s\n", line2);
	}
}

int
main(void) {
	char buf1[1024], buf2[1024];
	line in1, in2, out;

	while (1) {
		fgets(buf1, 1024, stdin);
		if (!buf1 || buf1[0]=='#') {
			return 0;
		}
		fgets(buf2, 1024, stdin);
		if (!buf2) {
			return 0;
		}
		parse_line(buf1, &in1);
		parse_line(buf2, &in2);
#if DEBUG
		printf("factor 1:\n");
		print(&in1);
		printf("factor 2:\n");
		print(&in2);
		printf("result:\n");
#endif
		multiply(&in1, &in2, &out);
		print(&out);
	}
}