#include <algorithm>
#include <iostream>
#include <list>
#include <sstream>
#include <string>
#include <string>
#include <utility>
using namespace std;

using Item = pair<double, double>;
using Poly = list<Item>;

Poly* Q = new Poly[0];
Poly* P = new Poly[0];

void PrintPolynom(Poly* pol) {
    bool firstTime = true;
    for (Item& p : *pol) {
        if (!firstTime)
            cout << " + ";
        cout << p.second << "x^" << p.first;
        firstTime = false;
    }
    cout << '\n';
}

string GetStringPolynom(Poly *pol)
{
    string str = "";
    bool firstTime = true;
    for (Item& p : *pol) {
        if (!firstTime)
            cout << " + ";
        str += to_string(p.second) + "x^" + to_string(p.first);
        firstTime = false;
    }
    return str;
}

void NormPolynom(Poly* pol) {
    auto bgn = begin(*pol);
    while (bgn != end(*pol)) {
        auto p = *bgn;
        double pwr = p.first;
        double cft = p.second;
        auto nxt = bgn; ++nxt;
        while (nxt != end(*pol)) {
            auto& q = *nxt;
            if (q.first != pwr)
                ++nxt;
            else {
                cft += q.second;
                nxt = pol->erase(nxt);
            }
        }
        if (cft == p.second)
            ++bgn;
        else {
            p.second = cft;
            auto del = bgn;
            bgn = pol->insert(bgn, p);
            pol->erase(del);
        }
    }
}

Poly* DerivativePolynom(Poly* pol) {
    Poly* dpol = new Poly;
    for (Item& p : *pol) {
        if (p.first != 0) {
            Item itm = make_pair(p.first - 1, p.second * p.first);
            dpol->emplace_back(itm);
        }
    }
    system("cls");
    cout << "Многочлен P: "; PrintPolynom(pol);
    cout << "Многочлен Q: "; PrintPolynom(dpol);
    Q = dpol;
    return dpol;
}

Poly* SumPolynom(Poly* pol1) {
    Poly* pol2 = DerivativePolynom(pol1);
    Poly* pol = new Poly;
    for (Item& p1 : *pol1) {
        Item itm = make_pair(p1.first, p1.second);
        pol->emplace_back(itm);
    }
    for (Item& p2 : *Q) {
        Item itm = make_pair(p2.first, p2.second);
        pol->emplace_back(itm);
    }
    NormPolynom(pol);
    cout << "Многочлен R: "; PrintPolynom(pol);
    cout << '\n';
    return pol;
}

void AddMonom(Poly* pol) {
    string line, str;
    double pwr, cft;
    cout << "Введите степень и коэффициент одночлена в виде p k, где p - степень, k - коэффициент:\n";
    while (!(cin >> pwr >> cft) || (cin.peek() != '\n')) {
        cin.clear();
        while (cin.get() != '\n');
        cout << "Неверный ввод\n";
    }
    pol->emplace_back(make_pair(pwr, cft));
    system("cls");
    cout << "Многочлен P: "; PrintPolynom(pol);
    cout << "\n";
}

void CalculatePolynom(Poly* pol) {
    double x, sum = 0;
    cout << "Введите X:\n";
    while (!(cin >> x) || (cin.peek() != '\n')) {
        cin.clear();
        while (cin.get() != '\n');
        cout << "Неверный ввод\n";
    }
    system("cls");
    for (Item& p : *pol)
        sum += pow(x, p.first) * p.second;
    system("cls");
    cout << "Многочлен P: "; PrintPolynom(pol);
    cout << "Многочлен в точке X = " << x << " равен " << sum << '\n';
    cout << '\n';
}

void DelMonom(Poly* pol) {
    auto bgn = begin(*pol);
    int pwr;
    cout << "Многочлен P: "; PrintPolynom(pol);
    cout << "Введите p - степень одночлена, который необходимо удалить:\n";
    while (!(cin >> pwr) || (cin.peek() != '\n')) {
        cin.clear();
        while (cin.get() != '\n');
        cout << "Неверный ввод\n";
    }
    for (auto it = begin(*pol); it != end(*pol);) {
        auto& p = *it;
        if (p.first == pwr) {
            it = pol->erase(it);
        }
        else {
            ++it;
        }
    }
    system("cls");
    cout << "Многочлен P: "; PrintPolynom(pol);
    cout << "\n";
}

Poly* GetPolynom(istream& in) {
    Poly* pol = new Poly;
    string line, str;
    double pwr, cft;
    bool first = true;
    getline(in, line, '\n');
    istringstream elm1(line);
    while (getline(elm1, str, ' ')) {
        istringstream elm2(str);
        if (first) {
            elm2 >> pwr;
            first = false;
        }
        else {
            elm2 >> cft;
            if (cft != 0)
                pol->emplace_back(make_pair(pwr, cft));
        }
        pwr--;
        if (pwr < 0) break;
    }
    return pol;
}

void ComparePolynoms(Poly* pol) {
    cout << "Многочлен P: "; PrintPolynom(pol);
    cout << "Многочлен Q: "; PrintPolynom(Q);

    if (GetStringPolynom(pol) == GetStringPolynom(Q))
        cout << "Многочлены P и Q равны\n\n";
    else
        cout << "Многочлены P и Q не равны\n\n";
}

int main() {
    setlocale(LC_ALL, "rus");
    cout << "Введите колличество одночленов многочлена и его коэффициенты в виде\ni a(n) a(n-1) a(n-2) ... a(1) a(0)\nГде i - кол-во одночленов, a - коэффициент n-го одночлена:\n";
    P = GetPolynom(cin);
    system("cls");
    cout << "Многочлен P: "; PrintPolynom(P);
    cout << "\n";
    while (true) {
        int choice;
        string line;
        cout << "1. Добавить одночлен к многочлену P\n";
        cout << "2. Удалить одночлен многочлена P\n";
        cout << "3. Построить многочлен Q - производная многочлена P\n";
        cout << "4. Построить многочлен R - сумма многочленов P и Q\n";
        cout << "5. Расчитать многочлен P в точке x\n";
        cout << "6. Привести подобные члены в многочлене P\n";
        cout << "7. Сравнить многочлены P и Q\n";
        cout << "8. Выход из программы\n";
        while (!(cin >> choice) || (cin.peek() != '\n')) {
            cin.clear();
            while (cin.get() != '\n');
            cout << "Неверный ввод\n";
        }
        switch (choice) {
        case 1:
            system("cls");
            AddMonom(P);
            break;
        case 2:
            system("cls");
            DelMonom(P);
            break;
        case 3:
            system("cls");
            DerivativePolynom(P);
            cout << "\n";
            break;
        case 4:
            system("cls");
            SumPolynom(P);
            break;
        case 5:
            system("cls");
            CalculatePolynom(P);
            break;
        case 6:
            system("cls");
            NormPolynom(P);
            cout << "Многочлен P: "; PrintPolynom(P);
            cout << "\n";
            break;
        case 7:
            system("cls");
            ComparePolynoms(P);
            break;
        case 8:
            return 0;
        default:
            system("cls");
            cout << "Неверное число\n";
            break;
        }
    }
}