//	Data structure project				//
//	infix to prefix conversion			//

#include <iostream>
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;
};

void convert(char* f)
{
	Stack<char> s1(64);
	Stack<char> s2(64);
	Stack<char> s3(64);
	int i=0;
	char e;

	while(f[i] != '\0')
	{
		if (f[i] == '(' || f[i] == '{' || f[i] == '[')
			s1.Push(f[i]);
		else if (f[i] == ')' || f[i] == '}' || f[i] == ']'){
			while(!s2.StackIsEmpty()){
				s2.Pop(e);
				s1.Push(e);
			}
			while(!s1.StackIsEmpty()){
				s1.Pop(e);
				if (e != '(' && e != '{' && e != '[')
					s2.Push(e);
				else
					break;
			}
		}
		else if (f[i] == '+' || f[i] == '-'){
			while(!s1.StackIsEmpty()){
				s1.Pop(e);
				if (e != '(' && e != '{' && e != '[')
					s3.Push(e);
				else{
					s1.Push(e);
					break;
				}
			}
			s1.Push(f[i]);
			while(!s3.StackIsEmpty()){
				s3.Pop(e);
				s1.Push(e);
			}
			while(!s2.StackIsEmpty()){
				s2.Pop(e);
				s1.Push(e);
			}
		}
		else if (f[i] == '*' || f[i] == '/'){
				s1.Push(f[i]);
				while(!s2.StackIsEmpty()){
					s2.Pop(e);
					s1.Push(e);
				}
		}
		else
			s2.Push(f[i]);

		i++;
	}

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

int main(){
	char f[64];
	char t;
	cout << "Data structure project\ninfix to prefix conversion\nseyed mohammad hoseini	871412306\n___________________________________\n\n";

	do{
		cout << "Enter a balanced infix expression :\n";
		cin.getline(f,64);
		cout << "\nprefix :\n";
		convert(f);
		cout << "\n\nTry again? (y/n) ";
		cin >> t;
		cin.ignore();
	}while(t == '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;
		Push(e);
	}
}