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

#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 isTopOpnd(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 = Opnd return true;
bool Stack::isTopOpnd(void)
{
	if (sp) 
	{
	switch(data[sp][0])
		{
		case '$':
		case '/':
		case '*':
		case '+':
		case '-': {return false;break;}
		default: {return true; break;}
		}
	}
	return false;
}


//MAIN PROGRAM LOOP STARTS HERE
main()
{

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

//Input prefix string
	cout << "Enter Prefix:" ;
	cin >> input;

//while the prefix string lasts	
	while(input[i])
	{
		symbol[0]=input[i];
		symbol[1]=NULL;
		switch(input[i])
		{
		case '*': 
		case '+': 
		case '-': 
		case '/': 
		case '$': {opStack.push(symbol);break;}
		default : 
			{
//Check if top of Stack already Operand 			
			twoOpnd=(opStack.isTopOpnd())? true : false;
//Another operand pushed in.
			opStack.push(symbol);

			while (twoOpnd) 
			{ 
				
				char op3[30]="",infix[30]="";
				
				infix[0]='(';
				strcpy(op3,opStack.pop());
				strcat(infix,opStack.pop());
				strcat(infix,opStack.pop());
				strcat(infix,op3);
				strcat(infix,")");

				twoOpnd=(opStack.isTopOpnd())? true : false;
				opStack.push(infix);
				strcpy(result,infix);
			}
			break;
			}//end default
			
		}//end switch 
		i++;
		
	}//end while(input)


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

	return 0;
}