//////////////////////////////////////////
//	Data structure project				//
//	calculatin infix expression			//
//	seyed mohammad hoseini	871412306	//
//////////////////////////////////////////
//	ex : 25*(-2*(1+1))-20/2 = -110

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

template <class x> class Stack {
public:
	Stack	(int m);
	~Stack	();
	int		StackIsFull();
	int		StackIsEmpty();
	void	Push(x e);
	void	Pop(x& e);
	void	PrintStack();
private:
	int		maxsize;
	int		top;
	x*		p;
};

int main(){
	cout << "Data structure project - Calculating infix expression\nseyed mohammad hoseini - 871412306\n_____________________________________________________\n\n";
	string again;
	do{
		Stack<string> s1(64),sout(64),s2(64),sc(64);
		string f, e, eprev;
		cout << "Enter an infix expression to calculate\n";
		cin >> f;
		int i=0, num=0, Operator=1;
		while(f[i] != '\0')
		{
			if (f[i] == '(' || f[i] == '{' || f[i] == '['){
				e = f[i];
				s1.Push(e);
				num = 0;
				Operator=1;
			}
			else if (f[i] == ')' || f[i] == '}' || f[i] == ']'){
				while(!s1.StackIsEmpty()){
					s1.Pop(e);
					if (e != "(" && e != "{" && e != "[")
						sout.Push(e);
					else
						break;
				}
				num = 0;
				Operator=0;
			}
			else if (f[i] == '+' || f[i] == '-'){
				if (Operator == 1 && f[i] == '-'){
					e = f[i];
					sout.Push(e);
					num = 1;
				}
				else {
					while(!s1.StackIsEmpty()){
						s1.Pop(e);
						if (e != "(" && e != "{" && e != "[")
							sout.Push(e);
						else{
							s1.Push(e);
							break;
						}
					}
					e = f[i];
					s1.Push(e);
					num = 0;
					Operator=1;
				}
			}
			else if (f[i] == '*' || f[i] == '/'){
				while(!s1.StackIsEmpty()){
					s1.Pop(e);
					if (e != "(" && e != "{" && e != "[" && e != "+" && e != "-")
						sout.Push(e);
					else{
						s1.Push(e);
						break;
					}
				}
				e = f[i];
				s1.Push(e);
				num = 0;
				Operator=1;
			}
			else{
				if(num == 1){
					e = f[i];
					sout.Pop(eprev);
					e = eprev + e;
					sout.Push(e);
				}
				else {
					e = f[i];
					sout.Push(e);
				}
				num = 1;
				Operator=0;
			}

			i++;
		}
		
		while(!s1.StackIsEmpty()){
			s1.Pop(e);
			sout.Push(e);
		}

		while(!sout.StackIsEmpty()){
			sout.Pop(e);
			s2.Push(e);
		}

		string e1,e2;
		int	i1,i2,i3;
		stringstream ss;
		while(!s2.StackIsEmpty()){
			s2.Pop(e);
			if (e == "+" || e == "-" || e == "*" || e == "/"){
				ss.clear();
				sc.Pop(e2);
				sc.Pop(e1);
				ss << e2;
				ss >> i2;
				ss.clear();
				ss << e1;
				ss >> i1;

				if (e == "+")
					i3 = i1 + i2;
				else if (e == "-")
					i3 = i1 - i2;
				else if (e == "*")
					i3 = i1 * i2;
				else if (e == "/")
					i3 = i1 / i2;

				ss.clear();
				ss << i3;
				ss >> e;
				sc.Push(e);
			}
			else {
				sc.Push(e);
			}
		}

		sc.Pop(e);
		cout << e << endl;
		cout << "Try again? (y/n) ";
		cin >> again;
	}while(again == "y");
	return 0;
}

template <class x> Stack<x>::Stack(int m){
	maxsize = m;
	top = -1;
	p = new x[maxsize];
}

template <class x> Stack<x>::~Stack(){
	delete [] p;
}

template <class x> int Stack<x>::StackIsFull(){
	if (top == maxsize - 1)
			return 1;
	return 0;
}

template <class x> int Stack<x>::StackIsEmpty(){
	if (top == -1)
			return -1;
	return 0;
}

template <class x> void Stack<x>::Push(x e){
	if (!StackIsFull()){
		top++;
		p[top] = e;
	}
}

template <class x> void Stack<x>::Pop(x& e){
	if (!StackIsEmpty()){
		e = p[top];
		top--;
	}
}

template <class x> void Stack<x>::PrintStack(){
	x e;
	if (!StackIsEmpty()){
		Pop(e);
		PrintStack();
		cout << e << endl;
		Push(e);
	}
}