Data Structure and Algorithm

/***************************************************************************
 Prefix -> Infix
 The following algorithm works for the expressions whose infix form does
 not require parenthesis to override conventional precedence of operators.
 1) Create the Expression Tree from the prefix expression
 2) Run in-order traversal on the tree.

 Prefix -> Postfix
 1) Create the Expression Tree from the prefix expression
 2) Run post-order traversal on the tree.

 --------------------------------------------------------------------------------------------
 ALGORITHM FOR CREATING EXPRESSION TREE FROM PREFIX EXPRESSION
 --------------------------------------------------------------------------------------------
 1) Reverse the prefix expression
 2) Examine the next element in the input.
 3) If it is operand then
  i) create a leaf node i.e. node having no child
  ii) copy the operand in data part
  iii) PUSH node's address on stack
 4) If it is an operator, then
   i) create a node
  ii) copy the operator in data part
  iii) POP address of node from stack and assign it to node->left_child
   iv) POP address of node from stack and assign it to node->right_child
   v) PUSH node's address on stack
 5) If there is more input go to step 2
 6) If there is no more input, POP the address from stack,
    which is the address of the ROOT node of Expression Tree.
 --------------------------------------------------------------------------------------

 Evaluating an expression involves two phases:
 1) Create an expression tree for given expression
 2) Evaluate the tree recursively

 ---------------------------------------------------------------------------------------
 ALGORITHM TO EVALUATE THE EXPRESSION FROM EXPRESSION TREE
 ---------------------------------------------------------------------------------------
 1)if root != NULL
 2)if current node contains an operator
    a) x = Evaluate Tree(root -> left_child)
    b) y = Evaluate Tree(root -> right_child)
    c) perform operation on x and y, specified by the operator
       and store result in a variable
    d) Return variable
 3)else, Return root->data
 ---------------------------------------------------------------
  (Above Algorithms are from programmersheaven.com)
****************************************************************************/

/***************************************************************************
 APPLICATION : Conversion from Prefix to Infix and Postfix (using Expression Tree)
               and Evaluation of Expression Tree
 CODED BY    : Ankit Pokhrel
 COMPILED ON : Borland C++ Ver 5.02
 DATE     : 2010 - July - 30
***************************************************************************/

#include "iostream.h"
#include "conio.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"

struct TREE //Structure to represent a tree
{
 char data;
 struct TREE *right,*left,*root;
};

typedef TREE tree;

/********* Stack Using Linked List **********/

struct Stack //Structure to represent Stack
{
 struct TREE *data;
 struct Stack *next,*head,*top; //Pointers to next node,head and top
};

typedef struct Stack node;

node *Nw; //Global Variable to represent node

void initialize(node *&n)
{
 n = new node;
 n -> next = n -> head = n -> top = NULL;
}

void create(node *n)
{
 Nw = new node; //Create a new node
 Nw -> next = NULL; //Initialize next pointer field
 if(n -> head == NULL) //if first node
  {
  n -> head = Nw; //Initialize head
   n -> top = Nw; //Update top
  }
}

void push(node *n,tree *ITEM)
{
 node *temp = n -> head;
 if(n -> head == NULL) //if First Item is Pushed to Stack
  {
   create(n); //Create a Node
  n -> head -> data = ITEM; //Insert Item to head of List
   n -> head = Nw;
   return; //Exit from Function
  }

 create(n); //Create a new Node
 Nw -> data = ITEM; //Insert Item
 while(temp -> next != NULL)
    temp = temp -> next; //Go to Last Node

 temp -> next = Nw; //Point New node
 n -> top = Nw; //Update top
}

node* pop(node *n)
{
 node *temp = n -> head,*deleted;
 if(n -> top == NULL) //If the Stack is Empty
  {
    return NULL;
   }

 if(n -> top == n -> head) //If only one Item
  {
    deleted = n -> head;
    n -> head = n -> top = NULL; //Set head and top to Null
    return deleted; //Return deleted node
   }

 while(temp -> next != n -> top)
  temp = temp -> next; //move pointer temp to second last node

 temp -> next = NULL; //Second last node points to NULL
 deleted = n -> top; //Save topmost node
 n -> top = temp; //Update top
 return deleted; //Return deleted node
}

int Empty(node *nd) //function to check if the stack is empty or not
{
 if(nd -> top == NULL)
  return 1; //empty
 else
  return 0;
}

/*********** Tree Section ************/

tree *New;
void create() //Function to create a node of a tree
{
 New = new tree;
 New -> left = NULL;
 New -> right = NULL;
}

void insert(tree *&t,char Item,int pass) //Function to insert item on a tree
{
 if(t == NULL) //If tree doesn't exist
  {
   t = new tree; //make a node
   t -> data = Item; //insert item
   t -> left = NULL; //initialize left pointer
   t -> right = NULL; //initialize right pointer
   if(pass)
   t -> root = t; //initialize root
   return; //return from function
  }

 create();
 New -> data = Item;
}

void inorder(tree *t) //Function to print tree in inorder
{
 if(t != NULL)
  {
   inorder(t -> left);
   cout << t -> data << ' ';
   inorder(t -> right);
  }
}

void postorder(tree *t) //Function to print tree in postorder
{
 if(t != NULL)
  {
   postorder(t -> left);
   postorder(t -> right);
   cout << t -> data << ' ';
  }
}

/*************** Main Program Section *************/

void reverse(char ch[],int len)
{
 char temp[60];
 int j = 0;
 for(int i = len - 1;i >= 0;i--)
   temp[j++] = ch[i];

 for(int i = 0;i < len;i++)
  ch[i] = temp[i];
}

int isOperator(char ch)
{
 if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '$')
  return 1;
 else
  return 0;
}

bool check(node *nd)
{
 if(nd != NULL)
  return true;
 else
  return false;
}

float calculate(float opr1,float opr2,char oprator)
{
 float value;
 if(oprator == '+')
  value = opr1 + opr2;
 if(oprator == '-')
  value = opr1 - opr2;
 if(oprator == '*')
  value = opr1 * opr2;
 if(oprator == '/')
  if(opr2 != 0)
   value = opr1 / opr2;
 if(oprator == '$')
  value = pow(opr1,opr2);

 return value;
}

float evaluate(tree *t)
{
 float x,y,result;
 char ch[3];
 if(t != NULL)
 {
  if(isOperator(t -> data))
   {
    x = evaluate(t -> left); //go to left
    y = evaluate(t -> right); //go to right
    result = calculate(x,y,t -> data); //calculate
    return result;
   }

  else
   {
    ch[0] = t -> data;
    ch[1] = '\0';
    result = atof(ch); //convert to float
    return result;
   }
 }
}

int main()
{
 char prefix[60];
 cout << "Enter a valid Prefix Expression\n";
 cout << "(in a single line, without spaces)\n";
 int i = 0;
 while(prefix[i - 1] != '\n')
  prefix[i++] = getchar();
 int len = i - 1,pass = true,valid = true;
 reverse(prefix,len); //reverse the prefix expression

 node *stk,*nd; //create a stack
 initialize(stk);
 tree *tr = NULL,*value;

 i = 0;
 while(i < len) //while there is data
  {
   if(!isOperator(prefix[i])) //if operand
    {
     create();
     New -> data = prefix[i];
     push(stk,New); //push address of tree node to stack
    }

   else //if operator
    {
     insert(tr,prefix[i],pass); //create a node of tree and insert operator
     if(pass) //if first pass
     {
      nd = pop(stk);
      valid = check(nd);
      if(!valid)
       break;
      value = nd -> data; //pop address
      tr -> left = value; //assign to left child
      nd = pop(stk);
      valid = check(nd);
      if(!valid)
       break;
      value = nd -> data; //pop address
      tr -> right = value; //assign to right child
      pass = false; //reset pass
      push(stk,tr); //push address to stack
     }

     else
      {
       nd = pop(stk);
       valid = check(nd);
       if(!valid)
         break;
       value = nd -> data; //pop address
       New -> left = value; //assign to left child
       nd = pop(stk);
       valid = check(nd);
       if(!valid)
        break;
       value = nd -> data; //pop stack
       New -> right = value; //assign to right child
       push(stk,New); //push address to stack
      }
    }

   i++; //update i
  }

 if(!Empty(stk))
 {
  tr -> root = pop(stk) -> data; //Last data of stack is root of tree
  tr = tr -> root;
 }

 if(!Empty(stk)) //if stack is not empty
  valid = false;

 if(!valid)
  {
   cout << "\nThe Given Prefix Expression is not Valid";
   cout << "\nCheck above Expression and try again...";
   getch();
   return 0; //exit from program
  }

 cout << "\nInfix : ";
 inorder(tr); //Inorder traversal gives Infix of expression
 cout << "\n\nPostfix : ";
 postorder(tr); //Postorder traversal gives Postfix of expression

 float result = evaluate(tr);
 cout << endl << "\nSolution : " << result;
 getch();
 return 0;
}

/****************************************************************************
 ------------
 LIMITATIONS
 ------------
 1)Above Alogorithm Works only for the expressions whose infix form does
   not require parenthesis to override conventional precedence of operators.
 2)This Program doesn't work for Operand greater than 9.
 3)Above Algorithm Works only for Binary Operators.
 4)This Program Works only for operators +,-,*,/ and $(Power).
****************************************************************************/