/*	File:	PostfixToInfix.cpp

			Christer Karlsson


This code implements a function that changes
a post-fix expression to an in-fix expression.

Allowed inputs are:

Operators: +,-,*,/,%
Operands : Chars								*/

#include <iostream>
#include <cstdlib>
#include <queue>

using namespace std;

// Tree structure
struct node
{
	char data;
	node *left;
	node *right;
};

// Global varaibles
const int SIZE = 80;        // Max size of the buffer = 80
char postfix[SIZE];
int top=-1;
node *exptree[SIZE];
queue<char> answer;

// Check symbol for operand or operator
int  whattype(char inputchar)
{
     if(inputchar=='+' || inputchar=='-' || inputchar=='*' || inputchar=='/' || inputchar=='%')
	  return(-1);
     else if(isdigit(inputchar) || isalpha(inputchar))
	  return(1);
     else
	  return(-99);  // For error, shouldn't be any
}
// Insert a single element in a tree
void push(node *tree)
{
	top++;
	exptree[top]=tree;
}
// pop of the top element
node *pop()
{
	top--;
	return(exptree[top+1]);
}
// Create the expression tree
void create_expr_tree(char *suffix)
{
	char symbol;
	node *newl, *ptr;
	int flag;
    int length;

    // Get the length of the Postfix expression subtract one due to endl-character
    length = cin.gcount()-1;
	// Loop through the Postfix expression
	for(int i=0; i<length; i++)
    {
        // Read a symbol from the postfix expression    
        symbol=suffix[i];    
		// An operand or operator?
		flag=whattype(symbol);	// flag=-1 when operator and flag=1 when operand

		// Is the symbol is an operand?
		if(flag == 1)
		{
			// Create a new node
			newl = new node;
			// Store the operand in the data-part
			newl->data = symbol;
			// No leaves
			newl->left = NULL;
			newl->right = NULL;
			// Push node's address on the stack
			push(newl);
		}
		// Symbol must be an operator
		else{ 
			// Create a new node
			newl = new node;
			// Store the data in the node
			newl->data = symbol;
			// Pop top address from stack and assign to right child
			ptr = pop();
			newl->right = ptr;
			// Pop top address from stack and assign to left child
			ptr = pop();
			newl->left = ptr;
			// Push the new node's address on the stack
			push(newl);
		}
	}
}
// PreOrder traversal of the tree
void preOrder(node *tree)
{
	if( tree!=NULL)
    {
		// Push the root on the queue
		answer.push(tree->data);
		// Traverse the left subtre
		preOrder(tree->left);
		// Traverse the right subtree
		preOrder(tree->right);
	}
}
// InOrder traversal of the tree
void inOrder(node *tree)
{
    bool test;
	if( tree!=NULL)
    {
		// Test to see if leaf-node or not
		test = ( tree->left !=NULL);
		// Push a left parenthesis on the queue if not leaf-node 
        if(test)
            answer.push('(');
		// Traverse the left subtree
		inOrder(tree->left);
		// Push the root on the queue
		answer.push(tree->data);
		// Traverse the right subtree
		inOrder(tree->right);
		// Push a right parenthesis on the queue if not leaf-node
		if(test)
            answer.push(')');
	}
}
// PostOrder traversal of the tree
void postOrder(node *tree)
{
	if( tree!=NULL)
    {
		// Traverse the left subtree
		postOrder( tree->left);
		// Traverse the right subtree
		postOrder( tree->right);
		// Push the root on the queue
		answer.push(tree->data);
	}
}

// The main program
int main(int argc, char *argv[])
{
    char symbol;
	cout << "Enter Postfix Expression : ";
	cin.getline( postfix, SIZE);

	//Creation of Expression Tree
	create_expr_tree(postfix);

	//Traversal Operation on the expression tree
	cout << "\nPre-Order Traversal  : ";
	preOrder(exptree[0]);
	// Display the Pre-Order expression
    while( !answer.empty() )
    {
       cout << answer.front();
       answer.pop();         
    }    	

	cout << "\nIn-Order Traversal   : ";
	inOrder(exptree[0]);
    // Pop-off the leading (
    answer.pop();
    // Display the In-Order expression    
    while( !answer.empty() )
    {
       symbol = answer.front();
       answer.pop();
       // Check to see if the symbol is the tailing )
       if( !answer.empty() )
            cout << symbol;          
    }
                 
	cout << "\nPost-Order Traversal : ";
	postOrder(exptree[0]);	
	// Display the Post-Order expression
    while( !answer.empty() )
    {
       cout << answer.front();
       answer.pop();         
    }
     
	// End of program
	cout << endl;
    system("PAUSE");	
    return(0);
}