#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <string>
using namespace std;

template <typename T>
struct stack {
	T* data;
	unsigned	realSize,
		allocatedSize;

	stack() {
		data = nullptr;
		realSize = allocatedSize = 0;
	};

	void resize() {
		if (allocatedSize == 0 || allocatedSize == 1) {
			allocatedSize++;
		}
		else {
			allocatedSize *= 1.5;
		}
		T* temp_data = nullptr;
		if (data) {
			temp_data = new T[realSize];
			memcpy(temp_data, data, sizeof(T) * realSize);
			delete[] data;
		}
		data = new T[allocatedSize];
		if (realSize) {
			memcpy(data, temp_data, sizeof(T) * realSize);
			delete[] temp_data;
		}
	};

	void push(T obj) {
		if (realSize >= allocatedSize) {
			resize();
		}
		data[realSize] = obj;
		realSize++;
	};

	T pop() {
		if (realSize) {
			realSize--;
			return data[realSize];
		}
		return -1;
	};

	void print() {
		for (int i = 0; i < realSize; i++) {
			cout << data[i] << " ";
		}
		cout << endl;
	};

	T last() {
		if (realSize) {
			return data[realSize - 1];
		}
		return -1;
	}

	bool is_empty() {
		if (!realSize)
			return true;
		else
			return false;
	}

	~stack() {
		delete[]data;
		realSize = allocatedSize = 0;
	};
};

struct deque {
	int data;
	deque* next = 0, * prev = 0;
	deque* last = 0, * first = 0;

	void push_back(int obj) {
		deque* adr = new deque;
		if (last) {
			adr->prev = last;
			last->next = adr;
		}
		adr->next = nullptr;
		adr->data = obj;
		last = adr;
		if (!first)
			first = adr;
	};

	void push_front(int obj) {
		deque* adr = new deque;
		if (first) {
			adr->next = first;
			first->prev = adr;
		}
		adr->prev = nullptr;
		adr->data = obj;
		first = adr;
		if (!last)
			last = adr;
	};

	int pop_back() {
		int res = last->data;
		if (last->prev) {
			last = last->prev;
			delete last->next;
			last->next = nullptr;
		}
		else {
			delete last;
			last = first = nullptr;
		}
		return res;
	};

	int pop_front() {
		int res = first->data;
		if (first->next) {
			first = first->next;
			delete first->prev;
			first->prev = nullptr;
		}
		else {
			delete first;
			first = last = nullptr;
		}
		return res;
	};

	void print() {
		deque* adr = first;
		while (adr) {
			cout << adr->data << " ";
			adr = adr->next;
		}
		cout << endl;
	}

	~deque() {
		if (first) {
			while (first->next) {
				first = first->next;
				delete first->prev;
			}
			delete first;
			first = last = nullptr;
		}
	}
};

bool isPriorityHigher(char entered, char lastInStack) {
	if (lastInStack == '(')
		return true;
	switch (entered) {
	case '^':
		return true;
	case '*':
	case '/':
		if (lastInStack == '+' || lastInStack == '-')
			return true;
	}
	return false;
}

string output(char ch) {
	string str{};
	switch (ch) {
	case 's':
		return "sin";
	case 'c':
		return "cos";
	case 'S':
		return "arcsin";
	case 'C':
		return "arccos";
	case 'T':
		return "tg";
	case 'G':
		return "ctg";
	default:
		return str + ch;
	}
}

int main()
{
	char task = 0, operation = 0;
	do {
		stack<int> intStack;
		deque deque;
		string str{};
		stack<char> operationsStack;
		bool digits = false;
		cout << "Choose ur destiny!\n" << "[1] - stack (int)\n" << "[2] - deque\n" << "[3] - postfix\n" << "[ESC] - exit\n";
		task = _getch();
		if (task != '1' && task != '2' && task != '3' && task != 27 /*esc*/) {
			system("cls");
			cout << "ERROR: BAD ENTER, TRY AGAIN!\n";
		}
		switch (task) {
		case '1' /*stack*/:
			system("cls");
			do {
				cout << "What do u want to do with ur stack?\n" << "[1] - push smt\n" << "[2] - pop last\n" << "[3] - display content\n" << "[ESC] - back\n";
				operation = _getch();
				if (operation != '1' && operation != '2' && operation != '3' && operation != 27 /*esc*/) {
					//system("cls");
					cout << "ERROR: BAD ENTER, TRY AGAIN!\n";
				}
				switch (operation) {
				case '1' /*put*/:
					int number;
					cout << "Enter what u want to push in stack: ";
					cin >> number;
					intStack.push(number);
					cout << number << " pushed successfully\n";
					system("pause");
					break;
				case '2' /*take last*/:
					if (intStack.realSize)
						cout << intStack.pop() << " popped succesfully\n";
					else
						cout << "ERROR: Stack is empty\n";
					system("pause");
					break;
				case '3' /*print*/:
					cout << "STACK CONTENT: ";
					intStack.print();
					system("pause");
					break;
				}
			} while (operation != 27 /*ESC*/);
			system("cls");
			break;
		case '2' /*deque*/:
			system("cls");
			do {
				cout << "What do u want to do with ur deque?\n" << "[1] - push back\n" << "[2] - push front\n" << "[3] - pop back\n" << "[4] - pop front\n" << "[5] - display content\n" << "[ESC] - back\n";
				operation = _getch();
				if (operation != '1' && operation != '2' && operation != '3' && operation != '4' && operation != '5' && operation != 27 /*esc*/) {
					//system("cls");
					cout << "ERROR: BAD ENTER, TRY AGAIN!\n";
				}
				switch (operation) {
				int number;
				case '1' /*push back*/:
					cout << "Enter what u want to push in ur deque back: ";
					cin >> number;
					deque.push_back(number);
					cout << number << " put successfully\n";
					system("pause");
					break;
				case '2' /*push front*/:
					cout << "Enter what u want to push in ur deque front: ";
					cin >> number;
					deque.push_front(number);
					cout << number << " put successfully\n";
					system("pause");
					break;
				case '3' /*pop back*/:
					if (deque.last)
						cout << deque.pop_back() << " popped successfully\n";
					else
						cout << "there is no last element\n";
					system("pause");
					break;
				case '4' /*pop front*/:
					if (deque.first)
						cout << deque.pop_front() << " popped successfully\n";
					else
						cout << "there is no front element\n";
					system("pause");
					break;
				case '5' /*print*/:
					cout << "DEQUE CONTENT: ";
					deque.print();
					system("pause");
					break;
				}
			} while (operation != 27 /*ESC*/);
			system("cls");
			break;
		case '3' /*postfix*/:
			system("cls");
			char ch = 0;
			short bracketLvl = 0;
			bool prevIsDigit = false, prevIsOp = true, prevIsLeftBracket = false, prevIsRightBracket = false, prevIsFactorial = false;
			cout << "Press ESC to exit or enter algebraic expression using: \ndigits \n( ) \n! \n+ \n- \n* \n/ \n^ (power) \nsin \ncos \narcsin \narccos \ntg \nctg\n" << "Entry field: ";
			while (ch != 13 && ch != -1 && ch != 27) {
				ch = _getch();
				if (ch == 's' && (prevIsOp || prevIsLeftBracket)) {
					cout << ch;
					ch = _getch();
					if (ch == 'i') {
						cout << ch;
						ch = _getch();
						if (ch == 'n') {
							cout << ch;
							operationsStack.push('s');
						}
						else {
							cout << "\nERROR: bad sin enter\n";
							system("pause");
							ch = -1;
						}
					}
					else {
						cout << "\nERROR: bad sin enter\n";
						system("pause");
						ch = -1;
					}
				}
				if (ch == 't' && (prevIsOp || prevIsLeftBracket)) {
					cout << ch;
					ch = _getch();
					if (ch == 'g') {
						cout << ch;
						operationsStack.push('T');
					}
					else {
						cout << "\nERROR: bad tg enter\n";
						system("pause");
						ch = -1;
					}
				}
				if (ch == 'c' && (prevIsOp || prevIsLeftBracket)) {
					cout << ch;
					ch = _getch();
					switch (ch) {
					case 'o':
						cout << ch;
						ch = _getch();
						if (ch == 's') {
							cout << ch;
							operationsStack.push('c');
						}
						else {
							cout << "\nERROR: bad cos enter\n";
							system("pause");
							ch = -1;
						}
						break;
					case 't':
						cout << ch;
						ch = _getch();
						if (ch == 'g') {
							cout << ch;
							operationsStack.push('G');
						}
						else {
							cout << "\nERROR: bad ctg enter\n";
							system("pause");
							ch = -1;
						}
						break;
					default:
						cout << "\nERROR: bad cos or ctr enter\n";
						system("pause");
						ch = -1;
					}
				}
				if (ch == 'a' && (prevIsOp || prevIsLeftBracket)) {
					cout << ch;
					ch = _getch();
					if (ch == 'r') {
						cout << ch;
						ch = _getch();
						if (ch == 'c') {
							cout << ch;
							ch = _getch();
							switch (ch) {
							case 'c':
								cout << ch;
								ch = _getch();
								if (ch == 'o') {
									cout << ch;
									ch = _getch();
									if (ch == 's') {
										cout << ch;
										operationsStack.push('C');
									}
									else {
										cout << "\nERROR: bad arccos enter\n";
										system("pause");
										ch = -1;
									}
								}
								else {
									cout << "\nERROR: bad arccos enter\n";
									system("pause");
									ch = -1;
								}
								break;
							case 's':
								cout << ch;
								ch = _getch();
								if (ch == 'i') {
									cout << ch;
									ch = _getch();
									if (ch == 'n') {
										cout << ch;
										operationsStack.push('S');
									}
									else {
										cout << "\nERROR: bad arcsin enter\n";
										system("pause");
										ch = -1;
									}
								}
								else {
									cout << "\nERROR: bad arcsin enter\n";
									system("pause");
									ch = -1;
								}
								break;
							default:
								cout << "\nERROR: bad arcsin or arccos enter\n";
								system("pause");
								ch = -1;
							}
						}
						else {
							cout << "\nERROR: bad arcsin or arccos enter\n";
							system("pause");
							ch = -1;
						}
					}
					else {
						cout << "\nERROR: bad arcsin or arccos enter\n";
						system("pause");
						ch = -1;
					}
				}
				if (ch == '!' && prevIsDigit) {
					prevIsFactorial = true;
					prevIsLeftBracket = prevIsRightBracket = prevIsOp = prevIsDigit = false;
					cout << ch;
					str += ch;
				}
				if ((ch >= '0' && ch <= '9') && (prevIsOp || prevIsLeftBracket || prevIsDigit)) {
					digits = true;
					prevIsDigit = true;
					prevIsLeftBracket = prevIsRightBracket = prevIsOp = prevIsFactorial = false;
					cout << ch;
					str += ch;
				}
				if ((ch == '+' || ch == '-' || ch == '/' || ch == '*' || ch == '^') && (prevIsDigit || prevIsRightBracket || prevIsFactorial)) {
					if (str[str.length() - 1] >= '0' && str[str.length() - 1] <= '9')
						str += ' ';
					prevIsOp = true;
					prevIsLeftBracket = prevIsRightBracket = prevIsDigit = prevIsFactorial = false;
					cout << ch;
					while (!operationsStack.is_empty() && !isPriorityHigher(ch, operationsStack.last())) {
						str += youtput(operationsStack.pop());
					}
					operationsStack.push(ch);
				}
				if (ch == '(' && (prevIsOp || prevIsLeftBracket)) {
					prevIsLeftBracket = true;
					prevIsRightBracket = prevIsOp = prevIsDigit = prevIsFactorial = false;
					cout << ch;
					bracketLvl++;
					operationsStack.push(ch);
				}
				if (ch == ')' && (prevIsDigit || prevIsRightBracket || prevIsFactorial) && bracketLvl > 0) {
					prevIsRightBracket = true;
					prevIsDigit = prevIsOp = prevIsLeftBracket = prevIsFactorial = false;
					cout << ch;
					bracketLvl--;
					while (operationsStack.last() != '(') {
						str += output(operationsStack.last());
						operationsStack.pop();
					}
					operationsStack.pop();
				}
			}
			if (!digits) {
				cout << "\nERROR: There is no numbers\n";
			} else
			if (bracketLvl > 0) {
				cout << "\nERROR with brackets\n";
			} else
			if (ch != -1 && ch != 27) {
				while (!operationsStack.is_empty()) {
					str += output(operationsStack.pop());
				}
				cout << "\nresult: " << str << endl;
			}
			system("pause");
			system("cls");
			break;
		}
	} while (task != 27 /*esc*/);
}