#include <iostream>

using namespace std;

struct el {
    double koef;
    int pot;
    struct el *sljedeci;
};

struct el * dodaj_posle (struct el *const tekuci_el, struct el *const novi_el) {
    if (novi_el != NULL && tekuci_el != NULL) {
        novi_el->sljedeci = tekuci_el->sljedeci;
        tekuci_el->sljedeci = novi_el;
    }
    return novi_el;
}

struct el * kopiraj_jedan (const struct el *const lista, struct el *const novi_el) {
    novi_el->pot = lista->pot;
    novi_el->koef = lista->koef;
    novi_el->sljedeci = NULL;
    return lista->sljedeci;
}

void obrisi_listu (struct el *lista) {
    struct el *priv;
    while (lista != NULL) {
        priv = lista;
        lista = lista->sljedeci;
        delete priv;
    }
}

class Polinomi {

private:

    struct el *pocetak_liste;

public:

    Polinomi () {
        pocetak_liste = NULL;
    }

    Polinomi (const Polinomi& p) {
        pocetak_liste = NULL;
        struct el *zadnji_el = NULL;
        struct el *isp;

        for (isp = p.pocetak_liste; isp != NULL; isp = isp->sljedeci) {
            struct el *novi_el = new struct el;
            novi_el->koef = isp->koef;
            novi_el->pot = isp->pot;
            zadnji_el = dodaj_posle(zadnji_el, novi_el);
            if (pocetak_liste == NULL) pocetak_liste = zadnji_el;
        }
    }

    Polinomi (int st, istream& is) {
        pocetak_liste = NULL;
        struct el *novi_element = NULL;
        struct el *zadnji_el = NULL;

        for (int i = 0; i <= st; i++) {
            int koef;
            is >> koef;
            if (koef != 0.0)
            {
                novi_element = new struct el;
                novi_element->koef = koef;
                novi_element->pot = i;
                novi_element->sljedeci = NULL;
                zadnji_el = dodaj_posle(zadnji_el, novi_element);
                if (pocetak_liste == NULL) pocetak_liste = zadnji_el;
            }
        }
    }

    ~Polinomi () {
        obrisi_listu(pocetak_liste);
    }

    friend ostream& operator<< (ostream &os, const Polinomi& p) {
        const struct el *isp;

        for (isp = p.pocetak_liste; isp != NULL; isp = isp->sljedeci) {
            os << isp->koef << "*x^" << isp->pot;
            if (isp->sljedeci != NULL)
                os << " + ";
        }

        return os;
    }

    friend const Polinomi operator+ (const Polinomi &a, const Polinomi &b) {
        struct el *lista_a = a.pocetak_liste;
        struct el *lista_b = b.pocetak_liste;
        Polinomi c;
        struct el *zadnji_c = NULL;

        // Ideja je ici naizmenicno kroz liste a i b: Dok god je potencija u
        // listi a manja od one u b, potencija i koeficijent samo se kopiraju
        // u zbirnu listu i lista a gurne se jedan element unapred (i obrnuto
        // za listu b). Kada su potencije jednake, koeficijenti se saberu u
        // zbirnoj listi, a lista a i lista b gurnu se jedan element unapred.

        while (lista_a != NULL || lista_b != NULL) {
            struct el *zbir_el = new struct el;

            if (lista_a != NULL && lista_b != NULL)
                if (lista_a->pot < lista_b->pot)
                    lista_a = kopiraj_jedan(lista_a, zbir_el);
                else if (lista_b->pot < lista_a->pot)
                    lista_b = kopiraj_jedan(lista_b, zbir_el);
                else { // lista_a->pot == lista_b->pot
                    zbir_el->pot = lista_a->pot; // isto kao i lista_b->pot
                    zbir_el->koef = lista_a->koef + lista_b->koef;
                    zbir_el->sljedeci = NULL;
                    lista_a = lista_a->sljedeci;
                    lista_b = lista_b->sljedeci;
                }
            else if (lista_a != NULL)
                lista_a = kopiraj_jedan(lista_a, zbir_el);
            else // lista_b != NULL
                lista_b = kopiraj_jedan(lista_b, zbir_el);

            zadnji_c = dodaj_posle(zadnji_c, zbir_el);
            if (c.pocetak_liste == NULL)
                c.pocetak_liste = zadnji_c;
        }

        return c;
    }
};

int
main ()
{
    cout << "Unesite koeficijente polinoma a, 3. stupnja: ";
    Polinomi a(3, cin);
    cout << "a = " << a << endl;

    cout << "Unesite koeficijente polinoma b, 2. stupnja: ";
    Polinomi b(2, cin);
    cout << "b = " << b << endl;

    cout << "Zbir je: ";
    cout << "a + b = " << a + b << endl;

    return 0;
}