//CIS:610-251 Data Structures and Algos
//Assignment # 2 Question # 9b
//Postfix to Prefix

#include<iostream.h>
#include<string.h>

class Stack
{
private:
	char  (*data)[30]; //data value in stack
	unsigned sp;      // Stack Pointer
	unsigned spMax;   //Max Stack Pointer Value;
public:
	Stack();
	void push(char*);
	char *pop();
	bool areTop2Opnd(void);
};


//Constructor
Stack::Stack()
{ 
	data=new char[30][30];	//init data as an array of 256 char
	sp=0;				//Stack initialized
	spMax=29;			
	data[0][0]=NULL;		
}



//Add an element to Stack and increment the SP.
void Stack::push(char * item)
{ 
	if (sp<spMax) strcpy(data[++sp],item); 
	else cout << " Overflow";
}



//Return the Top most element of stack and decrement the SP
char * Stack::pop()
{ 
	if (sp>0) return data[sp--]; 
	else return NULL;
}


//if Stack Top has 2 Opnd return true;
bool Stack::areTop2Opnd(void)
{
//Top two are not operands.	
	bool result=false;

	if (sp>1) 
	{
//Check is Top most is an operator
	switch(data[sp][0])
		{
		case '$':
		case '/':
		case '*':
		case '+':
		case '-': {result=(data[sp][1]==NULL)? false:true;break;}
		default : { result=true;break;}
		}
	if (result)
	{
		switch(data[sp-1][0])
		{
		case '$':
		case '/':
		case '*':
		case '+':
		case '-': {result=(data[sp-1][1]==NULL)? false:true;break;}
		default: {result=true;break;}
		}
	}
	}

return result;
}




//MAIN PROGRAM LOOP STARTS HERE
main()
{

	char input[40]="",symbol[3],result[30]="";
	Stack opStack;
	bool twoOpnd=true;
	int i=0,j=0;

//Input postfix string
	cout << "Enter Postfix:" ;
	cin >> input;


//Parse each character of postfix string
	while(input[i])
	{
		symbol[0]=input[i];
		symbol[1]=NULL;
		switch(input[i])
		{
		case '*': 
		case '+': 
		case '-': 
		case '/': 
		case '$': { 
			
			if (opStack.areTop2Opnd()) 
			{
			
			char prefix[30]="",temp[30]="";
				strcpy(temp,opStack.pop());
				strcpy(prefix,symbol);
				strcat(prefix,opStack.pop());
				strcat(prefix,temp);
				opStack.push(prefix);
				strcpy(result,prefix);
			}

				break;
				  
				  
		  }//end of above cases
		default : {opStack.push(symbol);break;}
			
					
		}//end switch 
		i++;
	}//end while(input)

cout << "\nPrefix = " <<  result << '\n';

	return 0;
}