Expression of Tree Traversal

Expression of Tree Traversal

Defination of expresssion tree:-

Algebraic expressions such as a/b + (c-d) e

The terminal nodes (leaves) of an expression tree are the variables or constants in the expression (a, b, c, d, and e). The non-terminal nodes of an expression tree are the
operators (+, -, , and ). Notice that the parentheses which appear in Equation do not appear in the tree. Nevertheless, the tree representation has captured the intent of the
parentheses since the subtraction is lower in the tree than the multiplication.

                                                                              fig 1.1
                                       
Above tree is Expression of a/b+(c-d)e
In tree there are Three Types of Traversal

1 .Preorder Traversal(Prefix) :  To Traverse non Empty tree in Preoder.
a.Visit a root(Display the root).
b.Traverse left Subtree.
c.Traverse right subtree.
*Remember-DLR(D-DATA,L-LEFT,R-RIGHT)
  Example-
In  fig 1.1  preorder traversal is :-      + /  a  b *  - c d e

2.Inorder Traversal(Infix):
a. Traverse the left subtree.
b. Visit the root(Display the root).
c. Traverse the right subtree.
*Remember-LDR(D-DATA,L-LEFT,R-RIGHT)
Example-
In  fig 1.1  Inorder traversal is :-      a / b + c - d * e

3.Postorder Travrsal(Postfix):
a. Traverse the left subtree.
b. Traverse the right subtree.s
c. Visit the root(Display the root).
*Remember-LRD(D-DATA,L-LEFT,R-RIGHT)
Example-
In  fig 1.1  postorder traversal is :-       a b / c d - e * +


ALGORITHM:
          Define structure for Binary Tree (Information, Left Pointer & Right Pointer).

 Create Expression Tree:
          CreateTree() Root& Node pointer variable of type structure. Stack is an pointer array of type structure. String is character array which contains postfix expression. Top & I are variables of type integer.
Step 1: Top = -1 , I = 0;
 Step 2: Do Steps 3,4,5,6 While String[I] != NULL
Step 3: Create Node of type of structure
Step 4: Node->Data=String[I];
Step 5: If isalnum(String[I]) Then Stack[Top++] = Node; Else Node->Right = Stack [--Top ]; Node->Left = Stack[ --Top ]; Stack[ Top++ ] = Node;
Step 6: Increment I;
Step 7: Root = Stack[0];
Step 8: Return Root

Inorder Traversal Recursive : Tree is pointer of type structure. InorderR(Tree)
Step 1: If Tree != NULL 25
Step 2: InorderR( Tree->Left )
Step 3: Print Tree->Data
Step 4: InorderR( Tree->Right )

Postorder Traversal Recursive: Tree is pointer of type structure. PostorderR(Tree)
Step 1: If Tree != NULL
Step 2: PostorderR( Tree->Left )
Step 3: PostorderR( Tree->Right )
Step 4: Print Tree->Data

Preorder Traversal Recursive: Tree is pointer of type structure. PreorderR(Tree)
Step 1: If Tree != NULL
Step 2: Print Tree->Data
Step 3: PreorderR( Tree->Left )
Step 4: PreorderR( Tree->Right )

Program:-

#include<iostream>
#include<stdlib.h>
using namespace std;
#define MAX 15
int IsOperand(char ch)
{
if(ch>='A' && ch<='Z'||ch>='a' && ch<='z')
return 1;
else
return 0;
}
int IsOperator(char ch)
{
if(ch=='*' || ch=='/' || ch=='+' || ch=='-' || ch=='%'|| ch=='^'|| ch=='$')
return 1;
else
return 0;
}
class Expresiontree
{

struct exp
{
char data;
struct exp *lchild;
struct exp *rchild;
};
struct exp *root;
public:
Expresiontree();
void create(char *);

void inorder_r();
void inorder_r(exp*);

void inorder_nr();
void inorder_nr(exp *);

void preorder_r();
void preorder_r(exp *);

void preorder_nr();
void preorder_nr(exp *);

void postorder_r();
void postorder_r(exp *);

void postorder_nr();
void postorder_nr(exp *);

};
Expresiontree::Expresiontree()
{
root=NULL;
}
void Expresiontree::create(char *postfix)
{
exp *temp;
exp *stack[MAX];
char ch;
int top=-1;
int l;
for(l=0;postfix[l]!='\0';l++)
{
ch=postfix[l];
temp=new exp;
temp->data=ch;
temp->rchild=NULL;
temp->lchild=NULL;
if (IsOperand(ch))
stack[++top] = temp;
else

{
temp->rchild = stack [top-- ];
temp->lchild = stack[ top-- ];
stack[ ++top ] = temp;
}

}
root=stack[top--];

}


void Expresiontree::inorder_r()
{
inorder_r(root);
}
void Expresiontree::inorder_r(exp *r)
{
if(r)
{
inorder_r(r->lchild);
cout<<r->data<<"  ";
inorder_r(r->rchild);
}
}

void Expresiontree::inorder_nr()
{
inorder_nr(root);
}
void Expresiontree::inorder_nr(exp *root)
{
exp *curr=root;
exp *stack[MAX];
int top=-1;
while(1)
{
if(curr)
{
stack[++top]=curr;
curr=curr->lchild;
}
else
{
if(top!=-1)
{
curr=stack[top--];
cout<<curr->data;
curr=curr->rchild;
}
else
{
break;
}
}
}
}

void Expresiontree::preorder_r()
{
preorder_r(root);
}
void Expresiontree::preorder_r(exp *root)
{
if(root)
{
cout<<root->data;
preorder_r(root->lchild);
preorder_r(root->rchild);
}
}

void Expresiontree::preorder_nr()
{
preorder_nr(root);
}
void Expresiontree::preorder_nr(exp *root)
{
exp *stack[MAX],*curr=root;
int top=-1;
while(1)
{
if(curr)
{
cout<<curr->data;
stack[++top]=curr;
curr=curr->lchild;
}
else
{
if(top!=-1)
{
curr=stack[top--];
curr=curr->rchild;
}
else
{
break;
}
}
}
}

void Expresiontree::postorder_r()
{
postorder_r(root);
}
void Expresiontree::postorder_r(exp *root)
{
if(root)
{
postorder_r(root->lchild);
postorder_r(root->rchild);
cout<<root->data;
}
}

void Expresiontree::postorder_nr()
{
postorder_nr(root);
}
void Expresiontree::postorder_nr(exp *root)
{
exp *curr=root;
exp *stack[MAX];
int top=-1;
char flag[MAX],f;
while(1)
{
if(curr)
{
stack[++top]=curr;
flag[top]='L';
curr=curr->lchild;
}
else
{
if(top!=-1)
{
curr=stack[top];
f=flag[top];
top--;
if(f=='L')
{
stack[++top]=curr;
flag[top]='R';
curr=curr->rchild;
}
else
{
cout<<curr->data;
curr=NULL;
}
}
else
{
break;
}
}
}
}

int main()
{
char postfix[MAX];
int choice;
Expresiontree obj;
while(choice!=8)
{
cout<<"\nMENU\n";
cout<<"1.Create\n2.Inorder Recursive Traversal\n3.Inorder Non Recursive Traversal\n4.Preorder Recursive Traversal\n5.Preorder Non Recursive Traversal\n6.Postorder Recursive Traversal\n7.Postorder Non Recursive Traversal\n8.Exit";
cout<<"\nEnter choice:-\t";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the postfix expression:-";
cin>>postfix;
obj.create(postfix);
break;
case 2:
cout<<"\nInorder Recursive Traversal\n";
obj.inorder_r();
break;
case 3:
cout<<"\nInorder Non Recursive Traversal\n";
obj.inorder_nr();
break;
case 4:
cout<<"\nPreorder Recursive Traversal\n";
obj.preorder_r();
break;
case 5:
cout<<"\nPreorder Non Recursive Traversal\n";
obj.preorder_nr();
break;
case 6:
cout<<"\nPostorder Recursive Traversal\n";
obj.postorder_r();
break;
case 7:
cout<<"\nPostorder Non Recursive Traversal\n";
obj.postorder_nr();
break;
case 8: exit (0);
}
}

}

Implement Priority Queue As ADT Using Single Linked List for Patients in Hospital

Implement priority queue as ADT using single linked list for servicing patients in an hospital with priorities as i) Serious (top priority) ii) medium illness (medium priority) iii) General (Least priority).

#include<iostream>
#include<stdlib.h>

using namespace std;

class Queue
{
public:

struct node
          {
       int data;
       char name[10];
       struct node* next;
   };

struct node *head;

Queue()
       {

head=NULL;
}//Constructor

~Queue();
void Enqueue();
void Deque();
int Qempty();
void PrintTop();
void PrintLast();
};

void Queue::Enqueue()
{

struct node *p,*q;
p=new node;
cout<<"ENTER PATIENT NAME\t";
cin>>p->name;
cout<<"\nENTER PRIRITOY\t";
cin>>p->data;

p->next=NULL;
if(head==NULL)
       {
head=p;
}

else
        {
if(p->data>head->data)
               {
p->next=head;
head=p;
}

else
                {

q=head;
while(q->next!=NULL && (p->data <= (q->next->data)))
q=q->next;

p->next=q->next;
q->next=p;
}
}
}

void Queue::Deque()
{

struct node *p;
p=head;

head=p->next;
cout<<"\nDequed element id\t"<<p->data;
cout<<"\nDequed element name\t"<<p->name;
delete p;
}

int Queue::Qempty()
{

if(head==NULL)
       {
return (1);
}

else
return (0);
}

void Queue::PrintTop()
{

cout<<head->name<<"\t"<<head->data;
}

void Queue::PrintLast()
{

struct node *q;
int x;
q=head;
while(q->next!=NULL)
       {

q=q->next;
}

cout<<q->name<<"\t"<<q->data;
}

Queue::~Queue()
{

struct node *p;
p=head;
while(head!=NULL)
      {

p=head;
head=head->next;
delete p;
}
}

int main()
{
Queue s;
int x,n,ch,i;
struct node *head;
char pname[10];
do
{
cout<<"\n\tMENU\n1.CREATE\n2.INSERT\n3.DELETE\n4.PRINTT0P\n5.PRINTLAT\n6.EXIT";
cout<<"\nENTER YOUR CHOICE\t";
cin>>ch;
switch(ch)
{
case 1: cout<<"\nENTER NO. OF ENTRIES\t";
cin>>n;
for(i=0;i<n;i++)
{
s.Enqueue();
}
break;
case 2:
s.Enqueue();
break;
case 3:if(s.Qempty())
{
cout<<"\nQUEUE IS EMPTY\nELEMENTS CAN NOT BE DELETED";
}
s.Deque();

      break;
case 4:cout<<"ELEMENT AT THE FRONT OF QUEUE IS";
s.PrintTop();
//cout<<"\t"<<x;
break;
case 5:cout<<"ELEMENT AT THE REAR OF QUEUE IS";
s.PrintLast();
break;
case 6:cout<<"PROGRAM ENDING\n";
exit(0);
}
}while(ch<7);
}

Conversion of Expression and Evaluation

//Implementation of Stack

#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

class stack
{
struct node
{
int data;
node *next;
};//struct
node *top;

public:
stack()
{
top=NULL;
}
void push(char);
char pop();
int empty();
void display();
int Top()
{
return top->data;
}
};//class

int stack::empty()
{
if(top==NULL)
return 1;
else
return 0;
}//check empty condition

void stack::push(char val)
{
node *temp;
node *newnode=new node;
newnode->next=NULL;
newnode->data=val;

if(top==NULL)
top=newnode;
else
{
newnode->next=top;
top=newnode;
}
}//push opration

char stack::pop()
{
node *temp;
if(empty())
cout<<"\nstack is empty ";
else
{
temp=top;
top=top->next;
return temp->data;
}
}//pop opration

void stack::display()
{
node *temp=top;

while(temp!=NULL)
{
cout<<"\t"<<temp->data;
temp=temp->next;
}
}//display
int priority(char op)
{
static int flag=3;
if(op=='(')
return 0;
else if(op=='+' || op=='-')
return 1;
else if(op=='*' || op=='/')
return 2;
else if(op=='^')
return flag++;
else return -1;

}//priority

void infixtopostfix(char infix[20])
{
char token,post[20],x;
int j=0;
stack s2;

for(int i=0;infix[i]!='\0';i++)
{
token=infix[i];
if(isalnum(token))
post[j++]=token;
else
if(token=='(')
s2.push(token);
else if(token==')')
while((x=s2.pop())!='(')
post[j++]=x;
else
{
while(!s2.empty() && priority(s2.Top())>=priority(token))
{
post[j++]=s2.pop();
}//while
s2.push(token);
}//else
}//for

while(!s2.empty())
post[j++]=s2.pop();

post[j]='\0';
cout<<post;
}//function of Infix To Postfix


void infixtoprefix(char infix[20])
{
char token,pre[20],x;
int j=0;
stack s2;

for(int i=(strlen(infix)-1);i>=0;i--)
{
token=infix[i];
if(isalnum(token))
pre[j++]=token;
else
if(token==')')
s2.push(token);
else if(token=='(')
while((x=s2.pop())!=')')
pre[j++]=x;
else
{
while(!s2.empty() && priority(s2.Top())>priority(token))
{
pre[j++]=s2.pop();
}//while
s2.push(token);
}//else
}//for

while(!s2.empty())
pre[j++]=s2.pop();

pre[j]='\0';
for(int i=strlen(pre)-1;i>=0;i--)
cout<<pre[i];
}//function of Infix To Prefix

float operation(char token,float op1,float op2)
{
float p;
if(token=='*')
p=op1*op2;
else if(token=='/')
p=op1/op2;
else if(token=='+')
p=op1+op2;
else if(token=='-')
p=op1-op2;
else if(token=='^')
p=pow(op1,op2);

return p;
}//operation

void evapost(char post[20])
{
stack s3;
int val;
float result,op2,op1;
char token;
for(int i=0;post[i]!='\0';i++)
{
token=post[i];
if(isalpha(token))
{
cout<<"\nEnter value of variable "<<token<<" : ";
cin>>val;
s3.push(val);
}//if
else
if(isdigit(token))
s3.push(token-48);

else
{
op2=s3.pop();
op1=s3.pop();
result=operation(token,op1,op2);
s3.push(result);
}//else
}//for
result=s3.pop();
cout<<"\nResult= "<<result;
}//evapostfix expression

void evapre(char pre[20])
{
stack s3;
int val;
float result,op2,op1;
char token;
for(int i=strlen(pre)-1;i>=0;i--)
{
token=pre[i];
if(isalpha(token))
{
cout<<"\nEnter value of variable "<<token<<" : ";
cin>>val;
s3.push(val);
}//if
else
if(isdigit(token))
s3.push(token-48);

else
{
op1=s3.pop();
op2=s3.pop();
result=operation(token,op1,op2);
s3.push(result);
}//else
}//for
result=s3.pop();
cout<<"\nResult= "<<result;
}//evaprefix expression

int main()
{
char str1[20],str2[20],str3[20],str4[20];
int choice;
char ans='y';
do
{
cout<<"\n1.infix to postfix\n2.infix to prefix\n3.postfix evaluation\n4.prefix evaluation.";
cout<<"\nEnter your choice : ";
cin>>choice;
switch(choice)
{
case 1: cout<<"Enter infix expression  ";
 cin>>str1;
 infixtopostfix(str1);
 break;

case 2: cout<<"Enter infix expression  ";
 cin>>str2;
 infixtoprefix(str2);
 break;
case 3: cout<<"Enter postfix expression  ";
 cin>>str3;
 evapost(str3);
 break;
case 4: cout<<"Enter prefix expression  ";
 cin>>str4;
 evapre(str4);
 break;
}//switch
cout<<"\nDo you want to continue (y/n): ";
cin>>ans;

}while(ans=='y' || ans=='Y');

return 0;
}//main

/////////////////OUTPUT///////////////////
/*
1.infix to postfix
2.infix to prefix
3.postfix evaluation
4.prefix evaluation.
Enter your choice : 1
Enter infix expression  (((a+b)*(c-e))/(f+g))
ab+ce-*fg+/
Do you want to continue (y/n): y

1.infix to postfix
2.infix to prefix
3.postfix evaluation
4.prefix evaluation.
Enter your choice : 2
Enter infix expression  a+b/c*d-(e+f+(g-h)^i)/j+k
+-+a*//*bcd/++ef^-ghijk
Do you want to continue (y/n): y

1.infix to postfix
2.infix to prefix
3.postfix evaluation
4.prefix evaluation.
Enter your choice : 3
Enter postfix expression  623+-382/+*2^3+

Result= 52
Do you want to continue (y/n): y

1.infix to postfix
2.infix to prefix
3.postfix evaluation
4.prefix evaluation.
Enter your choice : 4
Enter prefix expression  ^*+232-64

Result= 100
Do you want to continue (y/n): n
*/

Refrence :-

1. http://www.thecrazyprogrammer.com/2014/02/c-program-and-algorithm-for-conversion-of-an-expression-from-infix-to-postfix.html

2. http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html

In this program their are Various type of opration.we can perform :

1.Infix to Postfix Opration

2.Infix to Prefix
3.Postfix Evaluation
4.Prefix Evaluation.

Implementation of Sequential File in C++

//Program of sequential file

#include<iostream>
#include<fstream>
using namespace std;
class Myfile
{
    struct student
    {
        int rollno;
        char name[20];
    };
    struct student s;

    public:
    void create(char);
    void display(char);
    void del(char);
    void insert(char);
    void modify(char,int);
};
 void Myfile::create(char fname[20]) //user defined function to create a file and input records in it
{
struct student s;
int i,n;
FILE fp;
fp.fopen(fname,"a+");
cout>>"\nEnter how many no of records you want to input?";
cin>>n;
for(i=0;i<n;i++)
{
cout<<"\nEnter roll no:";
cin>>rollno;
cout<<"Enter Student Name:"
cin>>s.name;
fwrite(&s,sizeof(s),1,fp);
}
fclose(fp);
}

 void Myfile::display(char fname[20]) //user defined function to display records
{
struct student s;
FILE fp;
fp=fopen(fname,"r");
if(fp==NULL)
{
cout<<"Error";
}
else
{
while(fread(&s,sizeof(s),1,fp)!=0)
{
cout<<s.rollno;
cout<<s.name<<"\n";
}
}
fclose(fp);
}
void Myfile::create(char fname[20], struct student s) //function to insert a record at end of file
{
ifstream fp;
fp=fopen(fname,"r+");
if(fp==NULL)
{
fp=fopen(fname,"w");
}
else
{
//fseek(fp,0,2);
fwrite(&s,sizeof(s),1,fp);
fclose(fp);
}
}

int Myfile::search(char fname[20],struct student s,int rollno) //function to search a record
{
ifstream *fp;
int count=0;
fp=fopen(fname,"r") ;
while(fread(&s,sizeof(s),1,fp)!=0)
{
if(rollno==s.rollno)
{
return count;
}
else
{
count++;
}
}
return(-1);
fclose(fp);
}

void Myfile::modify(char fname[20],struct student s,int rollno)  //function to modify a particular record
{
int k;
ifstream fp;
fp=fopen(fname,"r+");
while(fread(&s,sizeof(s),1,fp)!=0)
{
if(s.rollno==rollno)
{
fseek(fp,-sizeof(s),1);
cout<<"Enter modified data:\n";
cout<<"Enter roll no:";
cin>>s.rollno;
cout<<"Enter Name:";
cin>>s.name;

fwrite(&s,sizeof(s),1,fp);
}
}
fclose(fp);
}

void Myfile::del(char fname[20],struct student s,int rollno) //function to delete a record
{
int k;
ifstream fp;
ifstream fp1;
fp=fopen(fname,"r");
fp1=fopen("temp","w");
while(fread(&s,sizeof(s),1,fp)!=0)
{
if(rollno!=s.rollno)
{
fwrite(&s,sizeof(s),1,fp1);
}
}
fclose(fp);
fclose(fp1);
remove(fname);
rename("temp",fname);
}



int main()  // call to main function
{
int i,j,k,l; // variable declaration
ifstream fp;
Myfile mf; //declaring a file pointer
int choice;
int rollno;
char fname[20];
struct student s;
cout<<"\nEnter name of file:";

cin>>"%s",fname;
create(fname);

do //use of do while loop to repeat menu
{
cout<<"\n";
cout<<"\n..................MENU.................";
cout<<"\n1.Display\n2.Insert\n3.Search\n4.Modify\n5.Delete\n6.Exit";
cout<<"\n";
cout<<"\nEnter your choice:";
cin>>choice;

switch(choice) //switch case to display menu
{
case 1:
                        cout<<"\nRollno\tName"; //to display record
mf.display(fname);
break;
case 2:
                        cout<<"\nEnter Roll No:"; // to insert a record
cin.rollno;
k=mf.search(fname,s,rollno);
if(k!=-1)    // to avoid duplication
{
cout<<"\nSorry roll no already exist.";
}
else
{
cout<<"\nEnter Name:";
cin>>s.name;
s.rollno=rollno;
mf.inserts()insert(fname,s);
cout<<"Record inserted successfully.";
}
break;
case 3:
                        cout<<"\nEnter the roll no to be searched:"; // to search a record
cin>>rollno;
j=mf.search(fname,s,rollno);
if(j!=-1)
{
cout<<"Record found at position "<<j;
}
else
{
cout<<"Sorry!!!No  such record found.";
}
break;
case 4:
                        cout<<"\nEnter the roll no to be modified:";  //to modify a record
cin>>rollno;
k=mf.search(fname,s,rollno);
if (k!=-1)
{
mf.modify(fname,s,rollno);
}
else
{
cin>>"\nSorry!!!No  such record  found.";
}
break;
case 5:
                        cout<<"\nEnter the roll no to be deleted:"; //to delete a record
cin>>rollno;
l=mf.search(fname,s,rollno);
if (l!=-1)
{
mf.del(fname,s,rollno);
cout<<"Record deleted successfully.";
}
else
{
cout<<"Sorry!!!No  such record found.";
}
break;
case 6:
                        break;
default:
                        cout<<"\nWrong choice.";
break;
} //end of switch case
}while(choice<6); //end of do while loop
cout<<"\n";
    return(0);
} //end of main function