Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- };
- polynomial *HEAD = new polynomial, *END = HEAD;
- 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;
- }
- 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->prev;
- }
- node* derivative(node* L1, int n) {
- node *L, *p, *p1 = L1->prev;
- if (L1 != nullptr && L1->deg > 0) {
- ins_after(p1->deg - 1, p1->koef * p1->deg, L, 0);
- p1 = p1->prev;
- p = L;
- while (p1 != nullptr && p1->deg > 0) {
- ins_after(p1->deg - 1, p1->koef * p1->deg, p, 1);
- p1 = p1->prev;
- }
- p->prev = nullptr;
- } else
- L = nullptr;
- if (n > 1)
- derivative(L, n - 1);
- else
- return L;
- }
- 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->prev;
- }
- 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*& E, int n) {
- polynomial *h = HEAD, *h1;
- if (HEAD->next != nullptr)
- h1 = HEAD->next;
- for (int i = 0; i < n - 1&&h1->next!= nullptr; i++) {
- h = h1;
- h1 = h1->next;
- }
- if(h1->next!= nullptr) {
- if(h1==E)
- E=h;
- h->next = h1->next;
- del_node(h1->poly->prev);
- return 1;
- }
- return 0;
- }
- //#########################
- 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") {
- }
- else if (type == "5") {
- }
- else if (type == "6") {
- }
- else if (type == "7") {
- }
- else if (type == "8") {
- }
- //start(1);
- }
- signed main() {
- start(1);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement