Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <conio.h>
- #include <fstream>
- #include <string>
- #include <stack>
- using namespace std;
- struct Node
- {
- int x;
- Node *pNext;
- };
- //List có contructor mặc định và contructor sao chép đề sử dụng trong trường hợp dùng stack
- struct List
- {
- Node *pHead, *pTail;
- int Dau;
- List()
- {
- Dau = 1;
- }
- List operator = (const List& L)
- {
- Node *p = L.pHead, *p1;
- this->pHead = NULL;
- this->pTail = NULL;
- this->Dau = L.Dau;
- while (p != NULL)
- {
- p1 = new Node;
- if (!p1)
- exit(1);
- p1->pNext = NULL;
- p1->x = p->x;
- if (pHead == NULL)
- {
- pHead = pTail = p1;
- }
- else
- {
- pTail->pNext = p1;
- pTail = p1;
- }
- p = p->pNext;
- }
- return *this;
- }
- };
- //tạo list
- void CreateList(List &L)
- {
- L.pHead = L.pTail = NULL;
- }
- //tạo node
- Node* CreateNode(int x)
- {
- Node *p = new Node;
- if (p == NULL) exit(1);
- p->x = x;
- p->pNext = NULL;
- return p;
- }
- //thêm đầu
- void AddHead(List &L, Node *p)
- {
- if (L.pHead == NULL)
- {
- L.pHead = L.pTail = p;
- }
- else
- {
- p->pNext = L.pHead;
- L.pHead = p;
- }
- }
- //xóa cuối
- void DelHead(List &L)
- {
- Node *p;
- if (L.pHead == NULL) return;
- p = L.pHead;
- L.pHead = p->pNext;
- delete p;
- if (L.pHead == NULL) L.pTail = NULL;
- }
- //xóa cuối
- void DelTail(List &L)
- {
- Node *p = L.pHead;
- Node *pBef = NULL;
- if (p == NULL) return;
- if (L.pHead == L.pTail)
- {
- L.pHead = L.pTail = NULL;
- delete p;
- return;
- }
- while (p != L.pTail)
- {
- pBef = p;
- p = p->pNext;
- }
- pBef->pNext = NULL;
- L.pTail = pBef;
- }
- //Nhập bằng tay
- void Input(List &L)
- {
- int x;
- Node *p = NULL;
- cout << endl;
- cout << "nhap so nguyen: ";
- do
- {
- x = getch();
- if (L.pHead == NULL && x == '-')
- {
- cout << "-";
- L.Dau = -1;
- }
- if (x >= 48 && x <= 57)
- {
- x = x - 48;
- cout << x;
- p = CreateNode(x);
- AddHead(L, p);
- }
- else
- {
- if (x == 8)
- {
- if (L.pHead != NULL || L.Dau == -1)
- {
- if (L.pHead == NULL)
- {
- putch(8);
- putch(' ');
- putch(8);
- L.Dau = 1;
- continue;
- }
- putch(8);
- putch(' ');
- putch(8);
- p = L.pHead;
- L.pHead = L.pHead->pNext;
- delete p;
- }
- }
- }
- } while (x != 13);
- }
- //Xuất
- void Output(List &L)
- {
- Node *p = L.pHead;
- if (L.Dau == -1) cout << "-";
- while (p != NULL)
- {
- cout << p->x;
- p = p->pNext;
- }
- }
- //thêm cuối
- void AddTail(List &L, Node *p)
- {
- if (L.pHead == NULL)
- {
- L.pHead = L.pTail = p;
- }
- else
- {
- L.pTail->pNext = p;
- L.pTail = p;
- }
- }
- //Lấy độ dài list
- int ListLen(List L)
- {
- int dem = 0;
- Node *p = L.pHead;
- while (p != NULL)
- {
- dem++;
- p = p->pNext;
- }
- return dem;
- }
- //Hủy List
- void HuyList(List &L1)
- {
- Node *p1 = L1.pHead;
- while (L1.pHead != NULL)
- {
- L1.pHead = L1.pHead->pNext;
- delete p1;
- p1 = L1.pHead;
- }
- L1.pTail = NULL;
- }
- //So sánh 2 số nguyên cùng độ dài, và là 2 sô nguyên bị đảo ngược
- int SoSanhListCungDoDai(Node *p1, Node *p2)
- {
- int t;
- if (p1->pNext != NULL && p2->pNext != NULL)
- {
- t = SoSanhListCungDoDai(p1->pNext, p2->pNext);
- if (t != 0) return t;
- }
- if ((p1->pNext == NULL && p2->pNext == NULL) || t == 0)
- {
- if (p1->x > p2->x) return 1;
- if (p1->x < p2->x) return -1;
- return 0;
- }
- }
- int SoSanhList(List L1, List L2)
- {
- int len1 = ListLen(L1), len2 = ListLen(L2);
- if (len1 > len2) return 1;
- if (len1 == len2) return SoSanhListCungDoDai(L1.pHead, L2.pHead);
- if (len1 < len2) return -1;
- }
- //Cộng Trừ 2 BIGINT
- void CongList(List L1, List L2, List &L3)
- {
- Node *p1 = L1.pHead, *p2 = L2.pHead;
- Node *p3 = NULL;
- int r = 0;
- int x;
- while (p1 != NULL && p2 != NULL)
- {
- x = p1->x + p2->x + r;
- if (x >= 10)
- {
- r = 1;
- x = x - 10;
- }
- else
- r = 0;
- p3 = CreateNode(x);
- AddHead(L3, p3);
- p1 = p1->pNext;
- p2 = p2->pNext;
- }
- while (p1 != NULL)
- {
- x = p1->x + r;
- if (x >= 10)
- {
- r = 1;
- x = x - 10;
- }
- else
- r = 0;
- p3 = CreateNode(x);
- AddHead(L3, p3);
- p1 = p1->pNext;
- }
- while (p2 != NULL)
- {
- x = p2->x + r;
- if (x >= 10)
- {
- r = 1;
- x = x - 10;
- }
- else
- r = 0;
- p3 = CreateNode(x);
- AddHead(L3, p3);
- p2 = p2->pNext;
- }
- if (r == 1)
- {
- p3 = CreateNode(1);
- AddHead(L3, p3);
- }
- }
- void TruList(List L1, List L2, List &L3)
- {
- List L;
- int dau = 1;
- if (SoSanhList(L1, L2) == -1)
- {
- L.pHead = L1.pHead;
- L1.pHead = L2.pHead;
- L2.pHead = L.pHead;
- dau = -1;
- }
- Node *p1 = L1.pHead, *p2 = L2.pHead, *p3 = NULL;
- int r = 0, x;
- while (p1 != NULL && p2 != NULL)
- {
- x = p1->x - p2->x - r;
- if (x < 0)
- {
- r = 1;
- x = x + 10;
- }
- else
- r = 0;
- p3 = CreateNode(x);
- AddHead(L3, p3);
- p1 = p1->pNext;
- p2 = p2->pNext;
- }
- while (p1 != NULL)
- {
- x = p1->x - r;
- if (x < 0)
- {
- r = 1;
- x = x + 10;
- }
- else
- r = 0;
- p3 = CreateNode(x);
- AddHead(L3, p3);
- p1 = p1->pNext;
- }
- p3 = L3.pHead;
- while (L3.pHead != NULL)
- {
- if (L3.pHead->x == 0)
- {
- p2 = L3.pHead;
- L3.pHead = L3.pHead->pNext;
- delete p2;
- if (ListLen(L3) == 1)
- {
- if (L3.pHead->x == 0) dau = 0;
- break;
- }
- }
- else
- break;
- }
- if (L3.pHead) L3.Dau = dau;
- else
- CreateList(L3);
- }
- //các hàm phục vụ nhân chia bigint
- //Chèn số 0 vào đầu list
- void Chen(List &L)
- {
- AddHead(L, CreateNode(0));
- }
- //Sao chép bigint và đảo ngược chiều bigint lại
- void CopyList(List L, List &L1)
- {
- Node *p = L.pHead;
- while (p != NULL)
- {
- AddHead(L1, CreateNode(p->x));
- p = p->pNext;
- }
- }
- //Nhân BIGINT với 1 số nguyên
- void NhanListVoiMotSo(List L, List &L1, int x)
- {
- Node *p = L.pHead;
- int r = 0;
- int n;
- while (p != NULL)
- {
- n = p->x * x + r;
- if (n >= 10)
- {
- r = n / 10;
- n %= 10;
- }
- else
- r = 0;
- AddTail(L1, CreateNode(n));
- p = p->pNext;
- }
- if (r != 0)
- {
- AddTail(L1, CreateNode(r));
- }
- }
- //Đảo ngược list
- void DaoList(List &L)
- {
- Node *p1 = L.pHead;
- List L1;
- CreateList(L1);
- while (p1 != NULL)
- {
- AddHead(L1, CreateNode(p1->x));
- p1 = p1->pNext;
- }
- HuyList(L);
- L.pHead = L1.pHead;
- L.pTail = L1.pTail;
- CreateList(L1);
- }
- //Nhân 2 bigint
- void NhanList(List L1, List L2, List &L3)
- {
- if (L1.Dau * L2.Dau < 0) L3.Dau = -1;
- else L3.Dau = 1;
- Node *p1 = L1.pHead, *p2 = L2.pHead, *p3 = NULL;
- int x = 0;
- int r = 0;
- int dem = 0;
- List L, L4;
- CreateList(L);
- CreateList(L4);
- while (p2 != NULL)
- {
- NhanListVoiMotSo(L1, L, p2->x);
- for (int i = 0; i < dem; i++) Chen(L);
- CongList(L, L3, L4);
- HuyList(L);
- HuyList(L3);
- CopyList(L4, L3);
- HuyList(L4);
- p2 = p2->pNext;
- dem++;
- }
- DaoList(L3);
- }
- //Copy N Node từ node p trở đi. phục vụ hàm chia
- int CopyListNode(List &L, Node *&p, int n)
- {
- int i = 0;
- while (p && i < n)
- {
- AddHead(L, CreateNode(p->x));
- p = p->pNext;
- i++;
- }
- if (i < n) return 0;
- return 1;
- }
- //So sánh list theo
- int SoSanhListXuoi(List L1, List L2)
- {
- int len1 = ListLen(L1);
- int len2 = ListLen(L2);
- if (len1 > len2) return 1;
- if (len1 < len2) return -1;
- Node *p1 = L1.pHead;
- Node *p2 = L2.pHead;
- while (p1 && p2)
- {
- if (p1->x > p2->x) return 1;
- if (p1->x < p2->x) return -1;
- p1 = p1->pNext;
- p2 = p2->pNext;
- }
- if (p1 == NULL && p2) return -1;
- if (p1 && p2 == NULL) return 1;
- return 0;
- }
- //Chia list có độ dài chênh lệch 1 để lấy 1 số nguyên
- void ChiaListLay1So(List L1, List L2, int &KetQua)
- {
- //L1, L2 la list nguoc
- int t;
- List Tam;
- CreateList(Tam);
- List L;
- CreateList(L);
- CopyList(L2, L);
- List L3;
- CreateList(L3);
- CopyList(L1, L3);
- //Tam, L va L3 la list xuoi
- while (L3.pHead != NULL && L3.pHead->x == 0) DelHead(L3);
- DaoList(L);
- for (int i = 1; i <= 10; i++)
- {
- //dua vao list nguoc, tra ve list nguoc
- NhanListVoiMotSo(L, Tam, i);
- DaoList(Tam);
- t = SoSanhListXuoi(L3, Tam);
- if (t <= 0)
- {
- if (t == 0)
- {
- KetQua = i;
- }
- else
- KetQua = i - 1;
- return;
- }
- else
- HuyList(Tam);
- }
- }
- //chia 2 bigint
- void ChiaList(List L1, List &L2, List &L3)
- {
- if (L1.Dau * L2.Dau < 0) L3.Dau = -1;
- else L3.Dau = 1;
- //L1, L2 list nguoc
- int len = ListLen(L2);
- List Tam;
- CreateList(Tam);
- List L4;
- CreateList(L4);
- List L5;
- CreateList(L5);
- DaoList(L1);//L1 list xuoi
- Node *p1 = L1.pHead;
- int t = CopyListNode(Tam, p1, len);//list xuoi
- if (t == 0)
- {
- AddHead(L3, CreateNode(0));
- return;
- }
- //l2 list nguoc
- //tam là list nguoc
- while (1)
- {
- ChiaListLay1So(Tam, L2, t);
- NhanListVoiMotSo(L2, L4, t);//list cung chieu
- if (t)
- {
- while (L4.pHead != L4.pTail && L4.pTail->x == 0)
- DelTail(L4);
- TruList(Tam, L4, L5);
- //L5 xuoi
- if (L5.pHead && L5.pHead->x == 0)
- {
- HuyList(Tam);
- HuyList(L5);
- }
- else
- if (L5.pHead && L5.pHead->x > 0)
- {
- Tam.pHead = L5.pHead;
- Tam.pTail = L5.pTail;
- CreateList(L5);
- }
- DaoList(Tam);
- }
- HuyList(L4);
- AddTail(L3, CreateNode(t));
- if (p1 == NULL) break;
- AddHead(Tam, CreateNode(p1->x));
- p1 = p1->pNext;
- }
- DaoList(L2);
- if (L3.pHead->x == 0) DelHead(L3);
- }
- //đọc bigint
- void ReadFile(List &L, string path = "")
- {
- fstream f;
- f.open(path, ios::out | ios::in);
- char c;
- if (f)
- {
- while (!f.eof())
- {
- f >> c;
- if (f.eof()) break;
- AddHead(L, CreateNode(c - 48));
- }
- }
- else cout << "path error\n";
- f.close();
- }
- // đọc đa thức
- void DocDaThuc(string &DaThuc, string path = "")
- {
- fstream f;
- f.open(path, ios::in | ios::out);
- if (f)
- {
- while (!f.eof())
- getline(f, DaThuc);
- }
- f.close();
- }
- //Xét độ ưu tiên toán tử
- int UT(char c)
- {
- if (c == '+' || c == '-') return 1;
- if (c == '*' || c == '/') return 2;
- return 0;
- }
- //Xử lý trung tố sang hậu tố
- string XuLyDaThuc()
- {
- stack<char> s = {};
- string DaThuc = "";
- string HauTo = "";
- char a;
- DocDaThuc(DaThuc, "D:/DaThuc.txt");
- int len = DaThuc.size();
- for (int i = 0; i < len; i++)
- {
- if (DaThuc[i] >= '0' && DaThuc[i] <= '9')
- {
- while (DaThuc[i] >= '0' && DaThuc[i] <= '9')
- HauTo += DaThuc[i++];
- HauTo += ' ';
- }
- if (DaThuc[i] == '(')
- s.push(DaThuc[i]);
- if (DaThuc[i] == '+' || DaThuc[i] == '-' || DaThuc[i] == '*' || DaThuc[i] == '/')
- {
- while (!s.empty() && UT(s.top()) >= UT(DaThuc[i]))
- {
- HauTo += s.top();
- s.pop();
- }
- s.push(DaThuc[i]);
- }
- if (DaThuc[i] == ')')
- {
- while (!s.empty() && s.top() != '(')
- {
- HauTo += s.top();
- s.pop();
- }
- s.pop();
- }
- }
- while (!s.empty())
- {
- HauTo += s.top();
- s.pop();
- }
- return HauTo;
- }
- //Ghi kết quả vào file
- void GhiFile(List L)
- {
- fstream f;
- f.open("Output.txt", ios::out);
- if (L.pHead && L.Dau == -1) f << "-";
- Node *p = L.pHead;
- while (p)
- {
- f << p->x;
- p = p->pNext;
- }
- f.flush();
- f.close();
- system("Output.txt");
- }
- //Tính giá trị đa thức theo biểu thức hậu tố
- void TinhDaThuc(string DaThuc)
- {
- stack<List> SL;
- stack<char> s;
- List L;
- List a, b, c;
- CreateList(a);
- CreateList(b);
- CreateList(c);
- CreateList(L);
- int len = DaThuc.size();
- for (int i = 0; i < len; i++)
- {
- if (DaThuc[i] >= '0' && DaThuc[i] <= '9')
- {
- while (DaThuc[i] >= '0' && DaThuc[i] <= '9')
- {
- AddHead(L, CreateNode(DaThuc[i] - 48));
- i++;
- }
- SL.push(L);
- CreateList(L);
- }
- if (DaThuc[i] == '+' || DaThuc[i] == '-' || DaThuc[i] == '*' || DaThuc[i] == '/')
- {
- if (DaThuc[i] == '-')
- int a = 2;
- a = SL.top();
- SL.pop();
- b = SL.top();
- SL.pop();
- if (DaThuc[i] == '+')
- {
- if (b.Dau == -1 && a.Dau == -1)
- {
- CongList(b, a, c);
- c.Dau = -1;
- }
- if (b.Dau == 1 && a.Dau == -1)
- TruList(b, a, c);
- if (b.Dau == -1 && a.Dau == 1)
- TruList(a, b, c);
- if (b.Dau == 1 && a.Dau == 1)
- CongList(b, a, c);
- }
- if (DaThuc[i] == '-')
- {
- if (b.Dau == -1 && a.Dau == 1)
- {
- CongList(b, a, c);
- c.Dau = -1;
- }
- if (b.Dau == 1 && a.Dau == -1)
- CongList(b, a, c);
- if (b.Dau == -1 && a.Dau == -1)
- {
- TruList(a, b, c);
- }
- if (b.Dau == 1 && a.Dau == 1)
- TruList(b, a, c);
- }
- if (DaThuc[i] == '*')
- NhanList(b, a, c);
- if (DaThuc[i] == '/')
- ChiaList(b, a, c);
- DaoList(c);
- SL.push(c);
- CreateList(a);
- CreateList(b);
- CreateList(c);
- }
- }
- DaoList(SL.top());
- Output(SL.top());
- cout << endl;
- //GhiFile(SL.top());
- }
- //Lưu ý các file test đặt đúng đường dẫn và đúng tên
- //Hàm main1 kiểm tra phep + - * /
- void main1()
- {
- List L1, L2, L3, L4;
- ReadFile(L1, "D:/Update.txt");
- int dau;
- CreateList(L1);
- CreateList(L2);
- CreateList(L3);
- ReadFile(L1, "D:/SN1.txt");
- ReadFile(L2, "D:/SN2.txt");
- CongList(L1, L2, L3);
- cout << endl;
- cout << "Cong: ";
- Output(L3);
- HuyList(L3);
- TruList(L1, L2, L3);
- cout << endl;
- cout << "Tru: ";
- Output(L3);
- HuyList(L3);
- NhanList(L1, L2, L3);
- cout << endl;
- cout << "Nhan: ";
- Output(L3);
- HuyList(L3);
- ChiaList(L1, L2, L3);
- cout << endl;
- cout << "Chia: ";
- Output(L3);
- getchar();
- }
- //main2 test việc xử lý số âm, việc nhập thủ công
- void main2()
- {
- List L;
- CreateList(L);
- List L1;
- CreateList(L1);
- List L2;
- CreateList(L2);
- Input(L);
- Input(L1);
- NhanList(L, L1, L2);
- cout << endl;
- Output(L2);
- }
- //Tính giá trị đa thức. đa thức đặt trong ổ D tên file là DaThuc.txt
- void main3()
- {
- string HauTo = XuLyDaThuc();
- TinhDaThuc(HauTo);
- }
- void main()
- {
- //main1();
- main2();
- //main3();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement