#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();
}