DSA Homework #1

dm4.cpp

#include <iostream>
#include <iomanip>
#include "dm4.h"

using namespace std;

poly::poly(double a_in[],int d_in) { 
    degree = d_in;
    a = new double[degree + 1];
    for (int i = 0; i <= degree; i++) {
        a[i] = a_in[i];
    }
}

poly::~poly() {
    delete[] a;
}

poly poly::operator+(const poly &p) {
    int max_degree;
    if (p.degree > degree) {
        max_degree = p.degree;
    } else {
        max_degree = degree;
    }

    double a_new[max_degree + 1];
    for (int i = 0; i <= max_degree; i++) {
        if (i > degree) {
            a_new[i] = p.a[i];
        } else if (i > p.degree) {
            a_new[i] = a[i];
        } else {
            a_new[i] = a[i] + p.a[i];
        }
    }

    // check if leading coefficient is 0
    while (max_degree > 0 && a_new[max_degree] - 0 < 0.00000000000000001) {
        max_degree--;
    }

    return poly(a_new, max_degree);
}

poly poly::operator-(const poly &p) {
    int max_degree;
    if (p.degree > degree) {
        max_degree = p.degree;
    } else {
        max_degree = degree;
    }

    double a_new[max_degree + 1];
    for (int i = 0; i <= max_degree; i++) {
        if (i > degree) {
            a_new[i] = -p.a[i];
        } else if (i > p.degree) {
            a_new[i] = a[i];
        } else {
            a_new[i] = a[i] - p.a[i];
        }
    }

    // check if leading coefficient is 0
    while (max_degree > 0 && a_new[max_degree] - 0 < 0.00000000000000001) {
        max_degree--;
    }

    return poly(a_new, max_degree);
} 

poly poly::operator*(const poly &p) {
    int new_degree = degree + p.degree;
    double a_new[new_degree + 1];

    for (int i = 0; i <= degree; i++) {
        for (int j = 0; j <= p.degree; j++) {
            a_new[i + j] += a[i] * p.a[j];
        }
    }

    // check if leading coefficient is 0
    while (new_degree > 0 && a_new[new_degree] - 0 < 0.00000000000000001) {
        new_degree--;
    }

    return poly(a_new, new_degree);
}

poly poly::operator/(const poly &p) {
    if (p.degree > degree) {
        return poly(new double[1], 0);
    }

    // prevent to modify a[]
    double a_clone[degree + 1];
    for (int i = 0; i <= degree; i++) {
        a_clone[i] = a[i];
    }

    int ans_degree = degree - p.degree;
    double a_new[ans_degree + 1];

    for (int i = 0; i <= ans_degree; i++) {
        double tmp = a_clone[degree - i] / p.a[p.degree];
        a_new[ans_degree - i] = tmp;
        for (int j = 0; j <= p.degree; j++) {
            a_clone[ans_degree - i + p.degree - j] -= tmp * p.a[p.degree - j];
        }

        // print
//         cout << "---" << endl;
//         for (int k = 0; k <= degree; k++) {
//             cout << a_clone[degree - k] << ' ';
//         }
//         cout << endl;
//         for (int k = 0; k <= p.degree; k++) {
//             cout << p.a_clone[p.degree - k] << ' ';
//         }
//         cout << endl;
//         for (int k = 0; k <= ans_degree; k++) {
//             cout << a_new[ans_degree - k] << ' ';
//         }
//         cout << endl;
        // print end
    }

    return poly(a_new, ans_degree);
}

poly poly::operator%(const poly &p) {
    if (p.degree > degree) {
        return poly(a, degree);
    }

    // prevent to modify a[]
    double a_clone[degree + 1];
    for (int i = 0; i <= degree; i++) {
        a_clone[i] = a[i];
    }

    int ans_degree = degree - p.degree;
    double a_new[ans_degree + 1];

    for (int i = 0; i <= ans_degree; i++) {
        double tmp = a_clone[degree - i] / p.a[p.degree];
        a_new[ans_degree - i] = tmp;
        for (int j = 0; j <= p.degree; j++) {
            a_clone[ans_degree - i + p.degree - j] -= tmp * p.a[p.degree - j];
        }
    }

    int mod_degree = degree;
    while (mod_degree > 0 && a_clone[mod_degree] - 0 < 0.00000000000000001) {
        mod_degree--;
    }

    return poly(a_clone, mod_degree);
}

void poly::show(){
    cout << fixed << setprecision(2) << a[0];
    for (int i = 1; i <= degree; i++) {
        cout << ' ' << fixed << setprecision(2) << a[i];
    }
    cout << endl;
}

dm4.h

class poly {
    public:
        int degree;
        double *a;
        poly(double a_in[], int d_in);
        ~poly();
        poly operator+(const poly &p);
        poly operator-(const poly &p);
        poly operator*(const poly &p);
        poly operator/(const poly &p);
        poly operator%(const poly &p);
        void show();
};

main.cpp

#include <iostream>
#include "dm4.h"
// #include "poly.h"
#define MAX (100000)
using namespace std;

int main(){
	int round;
	int d1,d2;
	double c1[MAX+1],c2[MAX+1];
	cin >> round;

	for(int r=0;r<round;r++){
		cin >> d1;
		for(int i=0;i<=d1;i++)
			cin >> c1[i];

		cin >> d2;
		for(int i=0;i<=d2;i++)
			cin >> c2[i];

		poly p1(c1,d1), p2(c2,d2);
		char op;
		cin >> op;
		switch(op){
			case '+':
				(p1+p2).show();
				break;
			case '-':
				(p1-p2).show();
				break;
			case '*':
				(p1*p2).show();
				break;
			case '/':
				(p1/p2).show();
				break;
			case '%':
				(p1%p2).show();
				break;
			default:
				cout << "unrecognized operation" << endl;
				break;
		}
	}
	return 0;
}

Makefile

main: poly.cpp main.cpp poly.h
	g++ dm4.cpp main.cpp -o poly
run:
	./poly < input