#include <iostream>
#include "conio.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
using namespace std;
struct TREE
{
char data;
struct TREE
*right,*left,*root;
};
typedef TREE tree;
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 preorder(tree *t) //Function to print tree in
preorder
{
if(t != NULL)
{
cout << t
-> data << ' ';
preorder(t ->
left);
preorder(t ->
right);
}
}
void inorder(tree *t) //Function to print tree in inorder
{
if(t != NULL)
{
inorder(t ->
left);
cout << t
-> data << ' ';
inorder(t ->
right);
}
}
/*************** Main Program Section *************/
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 postfix[60];
cout <<
"Enter a valid Postfix Expression\n";
cout <<
"(in a single line, without spaces)\n";
int i = 0;
while(postfix[i -
1] != '\n')
postfix[i++] =
getchar();
int len = i -
1,pass = true,valid = true;
node *stk,*nd;
//create a stack
initialize(stk);
tree *tr =
NULL,*value;
i = 0;
while(i < len)
//while there is data
{
if(!isOperator(postfix[i])) //if operand
{
create();
New -> data
= postfix[i];
push(stk,New);
//push address of tree node to stack
}
else //if
operator
{
insert(tr,postfix[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 ->
right = value; //assign to left child
nd =
pop(stk);
valid =
check(nd);
if(!valid)
break;
value = nd
-> data; //pop address
tr -> left
= 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 ->
right = value; //assign to left child
nd =
pop(stk);
valid =
check(nd);
if(!valid)
break;
value = nd
-> data; //pop stack
New ->
left = 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 Postfix 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\nPrefix : ";
preorder(tr);
//Postorder traversal gives Postfix of expression
float result =
evaluate(tr);
cout << endl
<< "\nSolution : " << result;
getch();
return 0;
}
