#include <bits/stdc++.h>

using namespace std;

struct node {
    int deg = 0;
    double koef = 0;
    node* next = nullptr;
    node* prev = nullptr;
};

struct polynomial {
    node* poly;
    polynomial* next = nullptr;
};


pair<int, int> read_koef(int i, string &main_str) {
    char c = main_str[i];
    int koef = 0;

    while('0' <= c && c <= '9') {
        koef *= 10;
        koef += (int) (c - '0');
        c = main_str[++i];
    }

    if (koef == 0 && main_str[i - 1] != '0') return {1, i};

    return {koef, i};
}

pair<string, int> read_name(int i, string &main_str) {
    char c = main_str[i];
    string dname = "";

    while( ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') ) {
        dname += c;
        ++i;
        c = main_str[i];
    }

    return {dname, i};
}

pair<int, int> read_deg(int i, string &main_str) {
    char c = main_str[i];

    if (c != '^') return {1, i};

    if (c == '^') {
        c = main_str[++i];
    }

    if (!('0' <= c && c <= '9') ) return {-1, i};

    int deg = 0;
    while('0' <= c && c <= '9') {
        deg *= 10;
        deg += (int) (c - '0');
        c = main_str[++i];
    }

    return {deg, i};
}

pair<string, int> read_sign(int i, string &main_str) {
    if (main_str[i] != '+' && main_str[i] != '-' && i == 0) {
        return {"+", i};
    }

    char c = main_str[i];
    string sg;

    sg = c;

    return {sg, i + 1};
}

bool sign_bool(char c) {
    if (c == '-') return 1;
    if (c == '+') return 1;
    if (c == '^') return 1;
    if (c == '*') return 1;
    return 0;
}

void create_node(node* &h, int koef, int deg) {
    h->deg = deg;
    h->koef = koef;
    h->next = nullptr;
    h->prev = nullptr;
    return;
}

void add_node(node* &head, int koef, int deg){
    if (koef == 0) return;
    if (head->prev == nullptr) {
        node* h = new (node);
        create_node(h, koef, deg);
        head->prev = h;
        h->next = head;
        return;
    }

    node* p = head->prev;
    node* h = new (node);
    create_node(h, koef, deg);

    if (p->deg < h->deg) {
        p->next = h;
        h->prev = p;
        h->next = head;
        head->prev = h;
        return;
    }

    while (p->prev != nullptr && p->deg > h->deg) {
        p = p->prev;
    }

    if (h->deg > p->deg) {
        p->next->prev = h;
        h->next = p->next;
        h->prev = p;
        p->next = h;
        return;
    }
    if (p->deg == h->deg) {
        if (p->koef + h->koef == 0) {
            if (p->prev == nullptr) {
                p->next->prev = nullptr;
                delete p;
            }
            else {
                p->next->prev = p->prev;
                p->prev->next = p->next;
                delete p;
            }
        }
        else p->koef += h->koef;
        delete h;
        return;
    }
    if (h->deg < p->deg) {
        p->prev = h;
        h->next = p;
        return;
    }
}

void print_node(node* head) {
    node *p = head->prev;

    //if (name == "") name = "x";
    string name = "x";

    if (p == nullptr) {
        cout << 0 << endl;
        return;
    }


    if (p->deg == 0) {
        cout << p->koef;
        p = p->prev;
    }
    else {
        if (p->deg == 1) {
            if (p->koef == -1) {
                cout << "-";
            }
            else cout << p->koef;
            cout << name;
        }
        else {
            if (p->koef == -1) {
                cout << "-";
            }
            else cout << p->koef;
            cout << name << "^" << p->deg;
        }

        p = p->prev;
    }

    while(p != nullptr) {
        if (p->koef == 1) {
            if (p->deg == 0) {
                cout << "+" << p->koef;
            }
            else cout << "+" << name << "^" << p->deg;
            p = p->prev;
            continue;
        }
        if (p->koef == -1) {
            if (p->deg == 0) {
                cout << "-" << p->koef;
            }
            else cout << "-" << name << "^" << p->deg;
            p = p->prev;
            continue;
        }


        if (p->koef > 0) cout << "+";
        if (p->deg == 0) {
            cout << p->koef;
        }
        else if (p->deg == 1) {
            cout << p->koef << name;
        }
        else {
            cout << p->koef << name << "^" << p->deg;
        }
        p = p->prev;
    }
        cout << endl;
}

void print_node_prev(node* head) {
    node *p = head;

    //if (name == "") name = "x";
    string name = "x";

    if (p == nullptr) {
        cout << 0 << endl;
        return;
    }


    if (p->deg == 0) {
        cout << p->koef;
        p = p->prev;
    }
    else {
        if (p->deg == 1) {
            if (p->koef == -1) {
                cout << "-";
            }
            else cout << p->koef;
            cout << name;
        }
        else {
            if (p->koef == -1) {
                cout << "-";
            }
            else cout << p->koef;
            cout << name << "^" << p->deg;
        }

        p = p->prev;
    }

    while(p != nullptr) {
        if (p->koef == 1) {
            if (p->deg == 0) {
                cout << "+" << p->koef;
            }
            else cout << "+" << name << "^" << p->deg;
            p = p->prev;
            continue;
        }
        if (p->koef == -1) {
            if (p->deg == 0) {
                cout << "-" << p->koef;
            }
            else cout << "-" << name << "^" << p->deg;
            p = p->prev;
            continue;
        }


        if (p->koef > 0) cout << "+";
        if (p->deg == 0) {
            cout << p->koef;
        }
        else if (p->deg == 1) {
            cout << p->koef << name;
        }
        else {
            cout << p->koef << name << "^" << p->deg;
        }
        p = p->prev;
    }
        cout << endl;
}


node* pol(string &main_str) {
    bool turn;
    string name = "";
    for (int i = 0; i < main_str.size(); i++) {
        if (!( ('0'<=main_str[i]&&main_str[i]<='9') || ('a'<=main_str[i]&&main_str[i]<='z') ||
               ('A'<=main_str[i]&&main_str[i]<='Z') || main_str[i] == '^' ||
                 main_str[i] == '+' || main_str[i] == '-' || main_str[i] == ' ')) {
                cout << "ERROR1!!!" << endl;
                main_str = "";
                name = "";
                return nullptr;
             }
    }

    for(int i = 0; i < main_str.size(); i++) {
        if(main_str[i] == '*') {
            main_str.erase(i, 1);
            i--;
        }
    }

    for (int i = 0; i < main_str.size(); i++) {
        if (i == 0) {
            if (('a'<=main_str[i]&&main_str[i]<='z') || ('A'<=main_str[i]&&main_str[i]<='Z')) turn = 1;
            else turn = 0;
        }
        else {
            if ( ('a'<=main_str[i]&&main_str[i]<='z' || 'A'<=main_str[i]&&main_str[i]<='Z') &&
                !('a'<=main_str[i - 1]&&main_str[i - 1]<='z' || 'A'<=main_str[i - 1]&&main_str[i- 1]<='Z') ) {
                if (turn == 1) {
                    cout << "ERROR2!!!" << endl;
                    main_str = "";
                    name = "";
                    return nullptr;
                }
                turn = 0;
            }
            else if (main_str[i] != ' ') {
                turn = 0;
            }
        }
    }

    for(int i = 0; i < main_str.size(); i++) {
            if(main_str[i] == ' ') {
                    main_str.erase(i, 1);
                    i--;
            }
        }

    if (main_str.size() == 0) {
        cout << "ERROR3!!!" << endl;
        main_str = "";
        name = "";
        return nullptr;
    }


    for (int i = 0; i < main_str.size(); i++) {

        if (i != 0 && sign_bool(main_str[i]) && sign_bool(main_str[i - 1])) {
            cout << "ERROR4!!!" << endl;
            main_str = "";
            name = "";
            return nullptr;
        }

        if (i != 0 && ('0'<=main_str[i]&&main_str[i]<='9') && (('a'<=main_str[i - 1]&&main_str[i - 1]<='z') ||
               ('A'<=main_str[i - 1]&&main_str[i - 1]<='Z')) ) {
            cout << "ERROR4!!!" << endl;
            main_str = "";
            name = "";
            return nullptr;
        }

        if (i != 1 && ('0'<=main_str[i - 2]&&main_str[i - 2]<='9') && main_str[i - 1] == '^' && ('0'<=main_str[i]&&main_str[i]<='9') ) {
            cout << "ERROR4!!!" << endl;
            main_str = "";
            name = "";
            return nullptr;
        }

    }

    if (main_str.size() == 0 || (main_str.size() == 1 && sign_bool(main_str[0]))) {
        cout << "ERROR5!!!" << endl;
        main_str = "";
        name = "";
        return nullptr;
    }

    //cout << main_str << endl << endl;

    node *head = new(node);


    for (int i = 0; i < main_str.size();) {
        int koef, deg;
        string dname, sg = " ";
        auto d1 = read_sign(i, main_str);
        sg = d1.first;
        i = d1.second;
        auto d2 = read_koef(i, main_str);
        koef = d2.first;
        i = d2.second;
        auto d3 = read_name(i, main_str);
        dname = d3.first;
        i = d3.second;
        auto d4 = read_deg(i, main_str);
        deg = d4.first;
        i = d4.second;
        if (dname == "") {
            deg = 0;
        }
        if (deg < 0) {
            cout << "ERROR4!!!" << endl;
            main_str = "";
            name = "";
            return nullptr;
        }
        if (sg != "-" && sg != "+") {
            cout << "ERROR5!!!" << endl;
            main_str = "";
            name = "";
            return nullptr;
        }
        //cout << sg << " " << koef << dname << "^" << deg << endl;
        if (sg == "-") koef = -koef;
        if (name == "") {
            name = dname;
        }
        else if (dname != name && dname != "") {
            cout << "ERROR6!!!" << endl;
            main_str = "";
            name = "";
            return nullptr;
        }
        add_node(head, koef, deg);
    }

    print_node(head);
    name = "";


    return head;
}

//#########################

void ins_after(int d,double k,node* &p,bool x) {
    node *q = new node;
    q->deg = d;
    q->koef = k;
    if (x) {
        p->prev = q;
        q->next = p;
    } else
        q->next = nullptr;
    p = q;
}

node* poly_num(polynomial* HEAD, int k) {
    polynomial *h = HEAD;
    node *L;
    for (int i = 0; i < k; i++)
        h = h->next;
    L = h->poly;
    return L;
}

node* sum(node* L1,node* L2) {
    node *head = new node;

    if (L1->prev != nullptr) {
        node *p = L1->prev;
        while (p != nullptr) {
            add_node(head, p->koef, p->deg);
            p = p->prev;
        }
        delete p;
    }

    if (L2->prev != nullptr) {
        node *p = L2->prev;
        while (p != nullptr) {
            add_node(head, p->koef, p->deg);
            p = p->prev;
        }
        delete p;
    }

    return head;
}

node* derivative(node* L, int n) {
    node *dL = new node;
    node *p = L->prev;

    while (p != nullptr) {
        if (p->deg > 0) add_node(dL, p->koef * p->deg, p->deg - 1);
        p = p->prev;
    }

    if (n > 1) {
        return derivative(dL, n - 1);
    }
    return dL;
}

int check(node* L,int i) {
    node *p = L;
    int sum = 0, x;
    while (p != nullptr) {
        x = 1;
        for (int j = 0; j < p->deg; j++)
            x *= i;
        sum += (x * (int) p->koef);
        p = p->prev;
    }
    return sum;
}

void roots(node *L) {
    node *p = L->prev;
    int free, x = 0;

    set<int> st;

    while (p->prev != nullptr)
        p = p->prev;
    if (p->deg > 0) {
        st.insert(0);
        x = 1;
    }
    free = (int) p->koef;
    for (int i = 1; i * 1.0 <= sqrt(abs(free * 1.0)); i++) {
        if (free % i == 0) {
            if (check(L, i) == 0) {
                //cout << i << " ";
                st.insert(i);
                x = 1;
            }
            if (check(L, -i) == 0) {
                //cout << -i << " ";
                st.insert(-i);
                x = 1;
            }
            if (i * i != free && check(L, free / i) == 0) {
                //cout << free / i << " ";
                st.insert(free/i);
                x = 1;
            }
            if (i * i != free && check(L, -free / i) == 0) {
                //cout << -free / i << " ";
                st.insert(-free/i);
                x = 1;
            }
        }
    }
    if (st.size() == 0) cout << "No roots";
    else {
        cout << "Roots: ";
        for (auto i: st) cout << i << " ";
    }
    cout << endl << endl;
}

node* division(node* L1,node* L2,node* L0,node* p0)//L0=p0=NULL
{
    node *L, *head = new node;
    int a;

    if (L1!=nullptr&&L1->deg >= L2->deg) {
        a = L1->koef / L2->koef;
        if (L0 == nullptr) {
            ins_after(L1->deg - L2->deg, a, L0, 0);
            p0 = L0;
        } else
            ins_after(L1->deg - L2->deg, a, p0, 1);

        if (L1->prev != nullptr) {
            node *p = L1/*->prev*/;
            while (p != nullptr) {
                add_node(head, p->koef, p->deg);
                p = p->prev;
            }
            delete p;
        }

        if (L2->prev != nullptr) {
            node *p = L2/*->prev*/;
            while (p != nullptr) {
                add_node(head, -p->koef * a, p->deg + L1->deg - L2->deg);
                p = p->prev;
            }
            delete p;
        }
        L = head->prev;

        division(L, L2, L0, p0);
        return L0;
    } else
        return L0;
}

node* multiplication(node* L1,node* L2) {
    node *head = new node;

    if (L1->prev != nullptr) {
        node *p = L1->prev;
        while (p != nullptr) {
            node *p1 = L2->prev;
            while (p1 != nullptr) {
                add_node(head, p->koef * p1->koef, p1->deg + p->deg);
                p1 = p1->prev;
            }
            delete p1;
            p = p->prev;
        }
        delete p;
    }

    return head;
}

void add_to_poly(polynomial* &E, node* L)
{
    polynomial* h=new polynomial;
    node* head = new node;
    h->poly=head;
    head->prev=L;
    L->next=head;
    E->next=h;
    E=h;
    h->next= nullptr;
}

void print_list(polynomial* HEAD){
    polynomial* h=HEAD->next;
    while(h!=nullptr) {
        print_node(h->poly);
        h = h->next;
    }
}

void del_node(node* L) {
    node *p = L, *p1 = L->prev;
    while (p1 != nullptr) {
        delete (p);
        p = p1;
        p1 = p1->prev;
    }
    delete (p);
}

bool del_H_node(polynomial* HEAD, polynomial* &END, int n) {
    polynomial *h = HEAD;
    for (int i = 0; i < n - 1 && h != nullptr; i++) {
        h = h->next;
    }
    if (h == nullptr || h->next == nullptr) return 0;

    polynomial *d = h->next->next;
    if (h->next == END) {
        END = h;
        del_node(h->next->poly->prev);
    }

    h->next = d;

    return 1;
}


polynomial *HEAD = new polynomial, *END = HEAD;


//#########################

void funcs_display(int x) {
    if (x == 5) {
        cout << "Enter number of function: ";
        return ;
    }
    system("cls");
    cout << endl << "LIST:" << endl;
    if (HEAD->next != nullptr) print_list(HEAD);
    cout << endl;

    cout << "Functions: " << endl;
    cout << "1: Enter polynomial" << endl;
    cout << "2: Delete polynomial" << endl;
    cout << "3: Integer roots of polynomial" << endl;
    cout << "4: Take the derivative" << endl;
    cout << "5: Summarize polynomial_1 and polynomial_2" << endl;
    cout << "6: Multiply polynomial_1 and polynomial_2" << endl;
    cout << "7: Divide polynomial_1 and polynomial_2" << endl;
    cout << endl;
    //cout << "Enter number of function: ";
    if (x == 1) cout << "Enter number of function: ";
    else if (x == 2) {
        cout << "ERROR IN INPUT" << endl;
        cout << "Enter number of function: ";
    }
    else if (x == 3) {
        cout << "POLYNOMIAL ADDED" << endl;
        cout << "Enter number of function: ";
    }
    else if (x == 4) {
        cout << "POLYNOMIAL DELETED" << endl;
        cout << "Enter number of function: ";
    }
}

void start(int flag) {
    funcs_display(flag);

    string type;
    getline(cin, type);
    node *head;


    if (type == "1") {
        int x = 3;
        cout << endl << "Enter polynomial: ";
        string main_str;
        while(getline(cin, main_str)) {
            if (main_str == "") continue;
            head = pol(main_str);
            break;
        }

        if (head == nullptr) {
            x = 2;
            cout << "ERROR IN INPUT" << endl;
        }
        else add_to_poly(END, head->prev);
        start(x);
    }
    else if (type == "2") {
        cout << endl << "Enter number of the polynomial: ";
        string NUMV;
        getline(cin, NUMV);

        bool YES_NO = del_H_node(HEAD, END, stoi(NUMV));
        if (YES_NO) start(4);
        else start(2);
    }
    else if (type == "3") {
        cout << endl << "Enter number of the polynomial: ";
        string NUMV;
        getline(cin, NUMV);

        roots(poly_num(HEAD, stoi(NUMV))->prev);
        start(5);
    }
    else if (type == "4") {
        cout << endl << "Enter number of the polynomial: ";
        string NUMV, ORDER;
        getline(cin, NUMV);

        cout << endl << "Enter the order of the derivative: ";
        getline(cin, ORDER);

        print_node(derivative(poly_num(HEAD, stoi(NUMV)), stoi(ORDER)));
        //derivative(poly_num(HEAD, stoi(NUMV))->prev, stoi(ORDER));
        start(5);
    }
    else if (type == "5") {
        cout << endl << "Enter numbers of the polynomial_1: ";
        string NUMV1, NUMV2;
        getline(cin, NUMV1);
        cout << "Enter numbers of the polynomial_2: ";
        getline(cin, NUMV2);

        print_node(sum(poly_num(HEAD, stoi(NUMV1)), poly_num(HEAD, stoi(NUMV2))));

        start(5);
    }
    else if (type == "6") {
        cout << endl << "Enter numbers of the polynomial_1: ";
        string NUMV1, NUMV2;
        getline(cin, NUMV1);
        cout << "Enter numbers of the polynomial_2: ";
        getline(cin, NUMV2);

        print_node(multiplication(poly_num(HEAD, stoi(NUMV1)), poly_num(HEAD, stoi(NUMV2))));
        start(5);
    }
    else if (type == "7") {
        cout << endl << "Enter numbers of the polynomial_1: ";
        string NUMV1, NUMV2;
        getline(cin, NUMV1);
        cout << "Enter numbers of the polynomial_2: ";
        getline(cin, NUMV2);

        print_node_prev(division( poly_num(HEAD, stoi(NUMV1))->prev, poly_num(HEAD, stoi(NUMV2))->prev, nullptr, nullptr ));
        start(5);
    }
    //start(1);
}


signed main() {
    start(1);

    return 0;
}