// HW3.cpp : 定義主控台應用程式的進入點。
//

#include <iostream>
using namespace std;

#define MAX_TERMS 10

typedef struct {
	int coef;
	int expo;
} polynomialTerm;

void clear(polynomialTerm t[])
{
	for (int i = 0; i < MAX_TERMS; i++) {
		t[i].coef = 0;
		t[i].expo = 0;
	}

	return;
}

void printArrayBasedPoly(polynomialTerm t[])
{
	if (t[0].coef == 0)
		return;

	if (t[0].expo == 0)
		cout << t[0].coef;
	else
		cout << t[0].coef << "X^" << t[0].expo;

	for (int i = 1; i < MAX_TERMS; i++) {
		if (t[i].coef == 0)
			return;

		if (t[i].expo == 0)
			cout << " + " << t[i].coef;
		else
			cout << " + " << t[i].coef << "X^" << t[i].expo;
	}
}

void inputTerm(polynomialTerm t[], int coef, int expo)
{
	for (int i = 0; i < MAX_TERMS; i++) {
		if (t[i].coef == 0) {
			t[i].coef = coef;
			t[i].expo = expo;
			return;
		}
		else if (t[i].expo == expo) {
			if (coef == 0) {
				for (int j = i; j < MAX_TERMS - 1; j++) {
					t[j] = t[j + 1];
				}
				t[MAX_TERMS - 1].coef = 0;
				return;
			}
			else {
				t[i].coef = coef;
				return;
			}
		}
		else if (t[i].expo < expo) {
			if (coef != 0) {
				for (int j = MAX_TERMS - 1; j > i; j--) {
					t[j] = t[j - 1];
				}
				t[i].coef = coef;
				t[i].expo = expo;
				return;
			}
		}
	}
}

void addArrayBasedPoly(polynomialTerm a[], polynomialTerm b[], polynomialTerm d[])
{
	int startA = 0, startB = 0, startD = 0;
	while (startA < MAX_TERMS && startB < MAX_TERMS) {
		if (a[startA].coef == 0 && b[startB].coef == 0)
			break;
        
		if (a[startA].expo > b[startB].expo) {
			d[startD].coef = a[startA].coef;
			d[startD++].expo = a[startA].expo;
			startA++;
		}
		else if (a[startA].expo < b[startB].expo) {
			d[startD].coef = b[startB].coef;
			d[startD++].expo = b[startB].expo;
			startB++;
		}
		else {
			int sum = a[startA].coef + b[startB].coef;
			if (sum != 0) {
				d[startD].coef = sum;
				d[startD++].expo = a[startA].expo;
			}
			startA++; startB++;
		}
	}

	for (; startA < MAX_TERMS; startA++) {
		if (startD >= MAX_TERMS)
			return;
		d[startD].coef = a[startA].coef;
		d[startD++].expo = a[startA].expo;
	}
	for (; startB < MAX_TERMS; startB++) {
		if (startD >= MAX_TERMS)
			return;
		d[startD].coef = b[startB].coef;
		d[startD++].expo = b[startB].expo;
	}

	return;
}


int main()
{
	polynomialTerm a[MAX_TERMS], b[MAX_TERMS], d[MAX_TERMS];
	int coef, expo;

	while (1) {
		clear(a); clear(b); clear(d);

		for (int i = 0; i < MAX_TERMS; i++) {
			cout << "\ninput a's coefficient and exponent: ";
			cin >> coef >> expo;

			if (expo == 0 && coef == 0)
				break;

			inputTerm(a, coef, expo);
		}

		cout << "\n\na = ";
		printArrayBasedPoly(a);
		cout << "\n";

		for (int i = 0; i < MAX_TERMS; i++) {
			cout << "\ninput b's coefficient and exponent: ";
			cin >> coef >> expo;

			if (expo == 0 && coef == 0)
				break;

			inputTerm(b, coef, expo);
		}

		cout << "\n\nb = ";
		printArrayBasedPoly(b);
		cout << "\n";

		// d =a + b, where a, b, and d are polynomials
		addArrayBasedPoly(a, b, d);
		cout << "\na + b = ";
		printArrayBasedPoly(d);
		cout << "\n";
	}

	return 0;
}

/*測資1:
0 5 3 0 7 1 1 1 -2 2 2 2 3 3 0 2 4 4 0 0
a = 4X^4 + 3X^3 + 1X^1 + 3
-3 0 0 7 8 1 -1 1 3 2 -2 2 -3 3 0 2 -4 4 0 0
b = -4X^4 + -3X^3 + -1X^1 + -3
a + b =

測資2:
7 3 2 5 1 7 4 8 2 3 5 5 1 0 0 3 0 0
a = 4X^8 + 1X^7 + 5X^5 + 1
2 5 -5 5 1 3 3 7 5 0 8 0 0 3 0 0
b = 3X^7 + -5X^5 + 8
a + b = 4X^8 + 4X^7 + 9

測資3:
8 8 7 7 6 6 3 3 4 4 5 5 2 0 1 9 0 0
a = 1X^9 + 8X^8 + 7X^7 + 6X^6 + 5X^5 + 4X^4 + 3X^3 + 2
-8 8 -7 7 -6 6 0 8 8 0 -8 8 9 9 0 0
b = 9X^9 + -8X^8 + -7X^7 + -6X^6 + 8
a + b = 10X^9 + 5X^5 + 4X^4 + 3X^3 + 10

測資4:
3 0 7 2 2 2 7 4 0 1 4 5 -8 9 -4 3 0 0
a = -8X^9 + 4X^5 + 7X^4 + -4X^3 + 2X^2 + 3
5 2 0 3 -5 2 -2 9 7 0 6 3 0 3 -7 4 2 1 0 0
b = -2X^9 + -7X^4 + -5X^2 + 2X^1 + 7
a + b = -10X^9 + 4X^5 + -4X^3 + -3X^2 + 2X^1 + 10

測資5:
0 9 0 7 0 3 0 1 2 0 0 0
a = 2
5 4 8 9 0 2 0 0
b = 8X^9 + 5X^4
a + b = 8X^9 + 5X^4 + 2
*/