Department of Computer Science

Data Structures Lab Ilahia College of Engineering and Technology

Experiment No: 6

STACK

PROBLEM DEFINITION:

Write a program to implement Stack.

ALGORITHM:

Step 1: Start
Step 2: Set top to -1
Step 3: Print size of stack
Step 4: If (push)
Step 4.1: If (top=size-1)
Step 4.1.1: Print overflow
Step 4.1.2: Endif
Step 4.1.3: Else
Step 4.1.3.1: Decrement top
Step 4.1.3.2: Read one element
Step 4.1.3.3: Set stack[top] to element
Step 4.1.4: Else end
Step 5: If (pop)
Step 5.1: If (top=-1)
Step 5.1.1: Print overflow
Step 5.1.2: Endif
Step 5.1.3: Else
Step 5.1.3.1: Set item to stack[top]
Step 5.1.3.2: Set top to top-1
Step 5.1.3.3: Else end
Step 6: If (display)
Step 6.1: Set i as top
Step 6.2: Loop (i<top)
Step 6.2.1: Print stack
Step 6.2.2: Increment i
Step 6.3: Loop ends
Step 7: Stop

PROGRAM DEVELOPMENT:

#include<stdio.h>

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

#include<conio.h>
void main()
{
int st[50],top=-1,k,n,i,si;
char ch;
clrscr();
printf("\n\tProgram to push ,pop or display an element from a stack");
printf("\n\t \n\n");
printf("\n\tEnter the size of the stack:") ;
scanf("%d",&si);
do
{
printf("\n\t\tMENU");
printf("\n\t\t \n");
printf("\n\n\t1.Push\n\n\t2.Pop\n\n\t3.Display\n\n\t4.Exit");
printf("\n\n\tEnter your choice:");
scanf("%d",&n);
if(n==1)
{
if(top==si-1)
{
printf("\n\tStack is overflow");
else
{
printf("\n\tEnter the element to be inserted:");
scanf("%d",&k);
top++;
st[top]=k;
printf("\n\tThe entered element is %d",st[top]);
}
}
else if(n==2)
{
if(top==-1)
{
printf("\n\tStack is underflow");
}
else
{
printf("\n\tThe deleted element is %d",st[top]);
top--;
}
}

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

else if(n==3)
{
if(top==-1)
{
printf("\n\tStack underflow");
}
else
{
printf("\n\tThe stack is:");
for(i=top;i>=0;i--)
{
printf("\t\t%d",st[i]);
}
}
}
else
{
break;
}
printf("\n\n\tDo you want to continue (Y/N) ?");
scanf(" %c",&ch);
}
while((ch=='Y')||(ch=='y'));
getch();
}

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Experiment No: 7

QUEUE

PROBLEM DEFINITION:

Write a program to implement Queue.

ALGORITHM:

Step 1: Start
Step 2: Set front and rear to -1
Step 3: Read size of queue
Step 4: If (insertion)
Step 4.1: If (rear=size-1)
Step 4.1.1: Print overflow
Step 4.2: End if
Step 4.3: Else
Step 4.3.1: Print enter the element
Step 4.3.2: Read the element
Step 4.3.3: If (front=-1& rear=-1)
Step 4.3.3.1: Set front=0
Step 4.3.3.2: Increment rear
Step 4.3.3.3: Read element to queue [rear]
Step 4.3.3.4: Endif
Step 4.3.4: End
else Step 5: If (deletion)
Step 5.1: If (front=-1)
Step 5.1.1: Print underflow
Step 5.2: End if
Step 5.3: Else
Step 5.3.1: Print deleted element is queue [front]
Step 5.3.2: If (front=rear)
Step 5.3.2.1: Set front and rear as -1
Step 5.3.2.2: Endif
Step 5.3.2.3: Else
Step 5.3.2.3.1: Increment front
Step 5.3.2.3.2: End Else
Step 5.4: Endif
Step 6: If (display)
Step 6.1: If (front & rear are -1)
Step 6.1.1: Print underflow
Step 6.1.2: End if
22

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Step 6.1.3: Else

Step 6.1.3.1: Set i as zero
Step 6.1.3.2: Loop (i<rear)
Step 6.1.3.2.1: Print queue[i]
Step 6.1.3.2.2: Loop ends
Step 6.1.4: End else
Step 7: End
if Step 8:
Stop

PROGRAM DEVELOPMENT:

#include<stdio.h>
#include<conio.h>
void main()
{
int no,i,front=-1,rear=-1,k,queue[50],element,n;
char c;
clrscr();
printf("\n\n\n\tPROGRAM TO INSERT, DELETE AND DISPLAY ELEMENTS TO
QUEUE");
printf("\n\t.......................................................\n\n\n");
printf("\n\n\tEnter the size of the queue: ");
scanf("%d",&n);
do
{
printf("\n\n\n\t\t\t\tMENU\n\n"); printf("\t\t1.INSERT\n\n\t\t2.DELETE\n\n\t\t3.DISPLAY\n\n\
t\t4.EXIT\n\n\t\tEnter your choice: ");
scanf("%d",&no);
if(no==1)
{
if(rear==(n-1)) printf("\n\
t\tOverflow"); else
{
printf("\n\n\t\tEnter the element: ");
scanf("%d",&element);
if(front==-1&&rear==-1)
front=0;
rear++;
queue[rear]=element;
}
}

23

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

if(no==2)
{
if(front==-1) printf("\n\t\
tUnderflow\n"); else
{
k=queue[front];
printf("\n\t\tDeleted element is %d ",k);
}
if(front==rear)
front=rear=-1;
else
front++;
}
if(no==3)
{
if(front==-1&&rear==-1)
printf("\n\t\tUnderflow\n");
else
{
printf("\n\t\tQueue elements are\n ");
for(i=front;i<=rear;i++)
{
printf("\n\n\t\t%d",queue[i]);
}
}
}
if(no==4)
break;
printf("\n\n\t\tDo you want to continue(y/n) ");
scanf(" %c",&c);
}
while(c=='y'||c=='Y');
getch();
}

24

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Experiment No: 10

STACK USING LINKED LIST

PROBLEM DEFINITION:

Write a program to implement Stack using Linked List.

ALGORITHM:

Step 1: Start
Step 2: Read the operation
Step 3: If (insertion)
Step 3.1: New = Getnode (Node)
Step 3.1.1: If (new=null) then
Step 3.1.1.1: Print insufficient memory”
Step 3.1.1.2: Exit
Step 4: Else
Step 4.1: Ptr=header
Step 4.2: While (ptr->link#Null) do
Step 4.2.1: Ptr=ptr->link
Step 4.2.2: End while
Step 4.2.3: Ptr->link=new
Step 4.2.4: New->data=x
Step 4.2.5: Endif
Step 4.2.6: Endif
Step 5: If (Deletion)
Step 5.1: Ptr=header
Step 5.2: If (ptr->link==Null) then
Step 5.2.1: Printf”empty list”
Step 5.2.2.: Exit
Step 5.3: Else
Step 5.3.1: While (ptr->link#null)do
Step 5.3.2:Ptr1=ptr
Step 5.3.3: Ptr=ptr->link
Step 5.3.4: Endwhile
Step 5.3.5:Ptr1->link=null
Step 5.3.6: Return node (ptr)
Step 5.3.7: Endif
Step 6: Endif
Step 7: If (display)
Step 7.1: Ptr=header->link
Step 7.2: While (ptr#Null)do
37

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Step 7.3: Display (ptr->data)

Step 7.4: Ptr=ptr->link
Step 7.5: Endwhile
Step 8: Endif
Step 9: Stop

PROGRAM DEVELOPMENT:

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
typedef struct node
{
int data;
struct node *link;
}NODE;
NODE *start=NULL,*top=NULL,*s,*ptr,*disply;
void main()
{
int no,item;
char c;
clrscr();
printf("\n\tPROGRAM TO INSERT, DELETE AND DISPLAY ELEMENTS TO STACK
USING LINKED LIST");
printf("\n\t.......................................................\n");
do
{
printf("\t\t\t\tMENU\n"); printf("\t\t1.INSERT\n\t\t2.DELETE\n\t\t3.DISPLAY\n\t\t4.EXIT\n\t\
tEnter your choice: "); scanf("%d",&no);
if(no==1)
{
ptr=(NODE*)malloc(sizeof(NODE));
printf("\n\t\tEnter the element: ");
scanf("%d",&item);

ptr->data=item;
ptr->link=NULL;
if(start==NULL)
{
start=ptr;
top=ptr;
}

38

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

else
{
ptr->link=top;
top=ptr;
}
}
if(no==2)
{
if(top==NULL) printf("\n\t\
tStack is empty"); else
{
s=top;
printf("\n\t\tDeleted Element is %d",top->data);
top=top->link;
free(s);
if(top==NULL)
start=NULL;
}
}
if(no==3)
{
if(top==NULL) printf("\n\t\
tStack is empty"); else
{
printf("\n\t\tStack elements are:");
disply=top;
while(disply!=NULL)
{
item=disply->data;
printf("\t %d\n",item);
disply=disply->link;
}
}
}
if(no==4)
break;
printf("\n\t\tDo you want to continue(y/n) ");
scanf(" %c",&c);
}
while(c=='y'||c=='Y');
getch();
}

39

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Experiment No: 11

QUEUE USING LINKED LIST

PROBLEM DEFINITION:

Write a program to implement Queue using Linked List.

ALGORITHM:

Step 1: Start
Step 2: Read the option
Step 3: If (insertion)
Step 3.1: New = getnode (node)
Step 3.2: Ptr=header
Step 3.3: While (ptr->link#Null) do
Step 3.3.1: Ptr=ptr->link
Step 3.4: End while
Step 3.5: Ptr-
>link=new
Step 3.6: New->data=x
Step 4: End if
Step 5: If (deletion)
Step 5.1: Ptr=header->link
Step 5.2: If (ptr=null)
Step 5.2.1: Print Empty list
Step 5.2.2: Exit
Step 5.3: Else
Step 5.3.1:Ptr1=ptr->link
Step 5.3.2: Header->link=ptr1
Step 5.3.3: Return node (ptr)
Step 5.3.4: Endif
Step 5.3.5: Endif
Step 6: If (display)
Step 6.1: Ptr=header->link
Step 6.2: While (ptr#null) do
Step 6.2.1: Display ptr->data
Step 6.2.2: Ptr=ptr->link
Step 6.2.3: Endwhile
Step 7: End if
Step 8: Stop

41

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

PROGRAM DEVELOPMENT:

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
typedef struct node
{
int data;
struct node *link;
}NODE;
NODE *front=NULL,*rear=NULL,*s,*ptr,*disply;
void main()
{
int no,item;
char c;
clrscr();
printf("\n\tPROGRAM TO INSERT,DELETE AND DISPLAY ELEMENTS TO QUEUE
USING LINKEDLIST");
printf("\t\t..............................................................\n\n");
do
{
printf("\t\t\t\tMENU"); printf("\n\t\t1.INSERT\n\t\t2.DELETE\n\t\t3.DISPLAY\n\t\t4.EXIT\n\t\
tEnter your choice: "); scanf("%d",&no);
if(no==1)
{
ptr=(NODE*)malloc(sizeof(NODE));
printf("\t\tEnter the element: ");
scanf("%d",&ptr->data);
ptr->link=NULL;
if(rear==NULL)
{
front=ptr;
rear=ptr;
}
else
{
rear->link=ptr;
rear=ptr;
}
}
if(no==2)
{

42

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

if(front==NULL) printf("\t\
tStack is empty\n"); else
{
s=front;
printf("\t\tDeleted Element is %d\n",front->data);
front=front->link;
free(s);
if(front==NULL)
rear=NULL;
}
}
if(no==3)
{
if(front==NULL) printf("\t\
tQueue is empty\n"); else
{
printf("\t\tQueue elements are");
disply=front; while(disply!
=NULL)
{
printf(" %d",disply->data);
disply=disply->link;
}
printf("\n");
}
}
if(no==4)
break;
printf("\t\tDo you want to continue(y/n) ");
scanf(" %c",&c);
}
while(c=='y'||c=='Y');
getch();
}

43

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Experiment No: 12

SINGLY LINKED LIST

PROBLEM DEFINITION:

Write a program to implement Singly Linked List.

ALGORITHM:

Step 1: Start
Step 2: Read the option
Step 3: If (traverse)
Step 3.1: Ptr=header->link
Step 3.2: While (ptr!=Null)do
Step 3.2.1: Print ptr->data
Step 3.2.2: Ptr=ptr->link
Step 3.3: End while
Step 3.4: Stop
Step 4: Elseif (insertion at front)
Step 4.1: New = getnode (Node)
Step 4.2: If (new=null)
Step 4.2.1: Insertion not possible
Step 4.2.2: Exit
Step 4.3: Else
Step 4.3.1: New->link=header->link
Step 4.3.2: Header->link=new
Step 4.4: Endif
Step 4.5: Stop
Step 5: Elseif (insertion at end)
Step 5.1: New = getnode (node)
Step 5.2: If (new=null) then
Step 5.2.1: Print insufficient memory
Step 5.2.2: Exit
Step 5.3: Else
Step 5.3.1: Ptr=header
Step 5.3.2: While (ptr->link#null)
Step 5.3.2.1: Ptr=ptr->link
Step 5.3.3: End while
Step 5.3.4: Ptr-
>link=new
Step 5.3.5: New->data=x
Step 5.3.6: New->link=null
45

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Step 5.4: Endif

46

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Step 5.5: Stop

Step 6: Else if (inset at any position)
Step 6.1: New = getnode (node)
Step 6.2: If (new==null)
Step 6.2.1: Printf insufficient memory
Step 6.2.2: Exit
Step 6.3: Else
Step 6.3.1: Ptr=header
Step 6.3.2: While (ptr->data#key) and (ptr->link#null)
Step 6.3.2.1: Ptr=ptr->link
Step 6.3.3: End while
Step 6.3.4: If (ptr->link=null)
Step 6.3.4.1: Print key not available
Step 6.3.4.2: Exit
Step 6.3.5: Else
Step 6.3.5.1: New->link=ptr->link
Step 6.3.5.2: New->data=v
Step 6.3.5.3: Ptr->link =new
Step 6.3.6: Endif
Step 6.4: Endif
Step 6.5: Stop
Step 7: Elseif (deletefront)
Step 7.1: Ptr=header->link
Step 7.2: If (ptr=null) then
Step 7.2.1: Print Empty list
Step 7.2.2: Exit
Step 7.3: Else
Step 7.3.1: Ptr1=ptr->link
Step 7.3.2: Header->link=ptr1
Step 7.3.3: Return node (ptr)
Step 7.4: Endif
Step 7.5: Stop
Step 8: Else if (delete
end)
Step 8.1: Ptr=header->link
Step 8.2: If (ptr=null) then
Step 8.2.1: Print empty list
Step 8.2.2: Exit
Step 8.3: Else
Step 8.3.1: While (ptr->link#Null)
Step 8.3.1.1: Ptr1=ptr
Step 8.3.1.2: Ptr=ptr->link
Step 8.3.2: End while
Step 8.3.3: Ptr->link=null
47

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Step 8.3.4: Return node(ptr)

48

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Step 8.3.5: Endif

Step 8.3.6: Stop
Step 9: Elseif (delete any)
Step 9.1: Ptr1=header
Step 9.2: Ptr=ptr1->link
Step 9.3: If (ptr==null) then
Step 9.3.1: Print Empty list
Step 9.3.2: Exit
Step 9.4: Else
Step 9.4.1: While (ptr#null) and (ptr->data#key) do
Step 9.4.1.1: Ptr1=ptr
Step 9.4.1.2: Ptr=ptr->link
Step 9.4.2: End while
Step 9.4.3: If (ptr==null) then
Step 9.4.3.1: Print Key not present
Step 9.4.3.2: Exit
Step 9.4.4: Else
Step 9.4.4.1: Ptr1->link=ptr->link
Step 9.4.4.2: Return node (ptr)
Step 9.4.5: End if
Step 9.4.6: Stop
Step 9: Endif
Step 10: Stop

PROGRAM DEVELOPMENT:

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
void traverse();
void insertfront();
void insertend();
void insertany();
void deletefront();
void deleteend();
void deleteany();
typedef struct node
{
int data;
struct node *link;
}NODE;
NODE *header=NULL,*newptr=NULL,*ptr,*ptr1;
void main()
49

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

{
int no,item;
char c;
clrscr();
printf("\n\tPROGRAM TO PERFORM OPERATIONS ON SINGLE LINKED
LIST"); printf("\n\t..........................................");
do
{
printf("\n\t\t\t\tMENU\n\n");
printf("\t\t1.TRAVERSE\n\t\t2.INSERT AT FRONT\n\t\t3.INSERT AT END\n\t\t4.INSERT AT
ANY POSITION\n\t\t5.DELETE FROM FRONT\n\t\t6.DELETE FROM END\n\t\t7.DELETE
FROM ANY POSITION\n\t\t8.EXIT\n\t\tEnter your choice: ");
scanf("%d",&no);
if(no==8)
break;
switch(no)
{
case 1:
traverse();
break;
case 2:
insertfront();
break;
case 3:
insertend();
break;
case 4:
insertany();
break;
case 5:
deletefront();
break;
case 6:
deleteend();
break;
case 7:
deleteany();
break;
default :
printf("\t\tINVALID ENTRY");
break;
}
printf("\t\tDo you want to continue(y/n) ");
scanf(" %c",&c);
50

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

}
while(c=='y'||c=='Y');
getch();
}
void insertfront()
{
newptr=(NODE*)malloc(sizeof(NODE));
printf("\t\tEnter the element: ");
scanf("%d",&newptr->data);
newptr->link=NULL;
if(newptr==NULL) printf("\t\
tInsufficient memmory"); else
{
newptr->link=header->link;
header->link=newptr;
}
}
void insertend()
{
newptr=(NODE*)malloc(sizeof(NODE));
if(newptr==NULL)
printf("\t\tInsufficient memmory");
else
{
printf("\t\tEnter the element: ");
scanf("%d",&newptr->data);
newptr->link=NULL;
ptr=header;
while(ptr->link!=NULL)
ptr=ptr->link;
newptr->link=ptr->link;
ptr->link=newptr;
}
}
void insertany()
{
int key;
newptr=(NODE*)malloc(sizeof(NODE));
if(newptr==NULL)
printf("\t\tInsufficient memmory");
else
{
printf("\t\tenter the key");

51

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

scanf("%d",&key); printf("\t\
tenter the element");
scanf("%d",&newptr->data);
ptr=header->link;
while(ptr->data!=key&&ptr!=NULL)
ptr=ptr->link;
if(ptr==NULL) printf("\t\
tkey is not found"); else
{
newptr->link=ptr->link;
ptr->link=newptr;
}
}
}
void deletefront()
{
ptr=header->link;
ptr1=ptr->link;
if(ptr==NULL)
printf("\t\tEmpty list");
else
{
header->link=ptr1;
printf("\t\tdeleted element is %d",ptr->data);
free(ptr);
}
printf("\n");
}
void deleteend()
{
ptr=header;
ptr1=ptr->link;
if(ptr1==NULL)
printf("\t\tEmpty list");
else
{
while(ptr1->link!=NULL)
{
ptr=ptr->link;
ptr1=ptr1->link;
}
ptr->link=NULL;
printf("\t\tDeleted element is %d",ptr1->data);

52

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

free(ptr1);
}
printf("\n");
}
void deleteany()
{
int key;
ptr=header;
ptr1=ptr->link;
if(ptr1==NULL)
printf("\t\tEmpty list");
else
{
printf("\t\tenter the key");
scanf("%d",&key);
while(ptr1->data!=key&&ptr1!=NULL)
{
ptr=ptr1;
ptr1=ptr1->link;
}
if(ptr1==NULL) printf("\t\
tKey not found"); else
if(ptr1->data==key)
{
ptr->link=ptr1->link;
printf("\t\tDeleted element is %d",ptr1->data);
free(ptr1);}
printf("\n");
}}
void traverse()
{
if(header->link==NULL)
printf("\t\tlist is empty\n");
else
{
printf("\t\tElements are\n");
ptr=header->link; printf("\
t\t"); while(ptr!=NULL)
{
printf(" %d",ptr->data);
ptr=ptr->link;
}
printf("\n");}}

53

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Experiment No: 14

INFIX TO POSTFIX EVALUATION

PROBLEM DEFINITION:

Write a program to implement Infix to Postfix Evaluation.

ALGORITHM:

Step 1: Start
Step 2: Read the expression
Step 3: For I from 0 to length
Step 3.1: Set ch as a[i]
Step 3.2: If (ch=’c’)
Step 3.2.1: Push (ch)
Step 3.3: If (ch=’)’)
Step 3.3.1: While (stk [top]!=’(’)
Step 3.3.1.1: Read stk [top]=post[j++]
Step 3.3.1.2: Decrement top
Step 3.3.2: End loop
Step 3.3.3: Decrement top
Step 3.4: If (ch=’+’ or ch=’-’ or ch=’*’ orch=’/’)
Step 3.4.1: If (top=-1 or stk[top]=’(’)
Step 3.4.1.1: Push (ch)
Step 3.4.2: Else
Step 3.4.2.1: x=priority (ch)
Step 3.4.2.2: y=priority (stk [top])
Step 3.4.2.3: If(y>=x)
Step 3.4.2.3.1: Read stk [top] to post [j++]
Step 3.4.2.3.2: Decrement top
Step 3.4.2.3.3: Push (ch)
Step 3.4.2.4: Else
Step 3.4.2.4.1: Push (ch)
Step 3.4.2.5: End if
Step 3.4.3: End if
Step 3.5: If (ch is an
alphabet)
Step 3.5.1: Read ch to post [j++]
Step 3.6: End if
Step 4: End loop
Step 5: While (stk [top] !=’\0’)
Step 5.1: Read stk [top] to post [j++]
59

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Step 5.2: Decrement top

60

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Step 6: End loop

Step7: Assign post[i] as ‘\0’
Step 8: Print “Post fix expression as post”
Step9: Stop

Eval-Postfix ()

Step 1: Start
Step 2: Find postfix expression for given expression
Step 3: For I from 0 to length of post
Step 3.1: Set ch as post[i]
Step 3.2: If ch is an alphabet
Step 3.2.1: Print “Enter the value for ch”
Step 3.2.2: Read the value to c.
Step 3.3.3: Push C to another stk.
Step 3.3: Else
Step 3.3.1: Set o1 as stk [top]
Step 3.3.2: Decrement top
Step 3.3.3: Set o2 as stk [top]
Step 3.3.4: Decrement top
Step 3.3.5: If(ch== +)
Step 3.3.5.1: x=o1+o2
Step 3.3.6: If(ch= -)
Step 3.3.6.1: x=o1-o2
Step 3.3.7: If (ch=*)
Step 3.3.7.1: x=o1*o2
Step 3.3.8: If (ch=/)
Step 3.3.8.1: x=o1/o2
Step 3.3.9: End if
Step 3.3.10: Push (x)
Step 3.4: End if
Step 4: End for
Step 5: Print value as stk [top]
Step 6: Stop

PROGRAM DEVELOPMENT:

#include <stdio.h>
#include<conio.h>
#include<string.h>
void push(char);
void push1(int);
int priority(char);
void read();

61

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

int top=-1,top1=-1,j=0,i,x,y;
char stk[50],stk1[50],a[50],ch,post[50];
void main()
{
clrscr();
printf("\n\n\tProgram for Infix to Postfix
Evaluation"); printf("\n\t \n");
printf("\n\tEnter the expression: ");
gets(a);
for(i=0;a[i]!='\0';i++)
{
ch=a[i];
switch(ch)
{
case '(':push(ch);
break;
case')':while (stk[top]!='(')
{
post[j++]=stk[top];
top--;
}
top--;
break;
case '+':
case '-':
case '^':
case '/':
case '*': if (top== -1||stk[top]=='(')
push(ch);
else
{x=priority(ch);
y=priority(stk[top]);
if(y>=x)
{
post[j++]=stk[top];
top--;
push(ch);}
else
push(ch);
}
break;
default:
if(isalpha(ch))
post[j++]=ch;
break;
}
}
while(stk[top]!='\0')
{
post[j++]=stk[top];
62

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

top--;
}
post[j]='\0';

printf("\n\tPostfix expression: ");

puts(post);
read();
getch();
}
void push(char ch)
{
top++;
stk[top]=ch;
}
void push1(int ch)
{top1++;
stk1[top1]=ch;
}
int priority(char c)
{
if (c=='t'||c=='-')
return 1;
else if(c=='*'||c=='/')
return 2;
else if(c=='^')
return 3;
else
return 0;
}
void read()
{
int c,o1,o2; for(i=0;post[i]!
='\0';i++)
{ch=post[i];
if(isalpha(ch))
{printf("\n\tEnter the value for %c: ",ch);
scanf("%d", &c);
push1(c);
}
else {
o1=stk1[top1];
top1--;
o2=stk1[top1];
top1--;
switch(ch)
{
case '+':x=o1+o2;
break;
case'-':x=o1-o2;
break;
63

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

case'*':x=o1*o2;
break;
case'/':x=o1/o2;
break;
case'^':x=o1^o2;
break;
default:
break;
}
push1(x);
}
}
printf("\n\tValue of the expression is %d",stk1[top1]);
}

OUTPUT:

CONCLUSION:

The algorithm was developed and the program was coded. The program was tested
successfully.

64

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Experiment No: 15

IMPLEMENTATION OF TREE

PROBLEM DEFINITION:

Write a program to implement Tree.

ALGORITHM:

Step 1: Start
Step 2: Ptr=new node ()
Step 3: Repeat the following steps until info!=0
Step 4: Enter the ptr->data
Step 5: Ptr->left=NULL and ptr->right=NULL
Step 6: If (root=NULL)
Step 6.1: Root =ptr
Step 6.2: Start=root
Step 7: Else
Step 7.1: Root=start
Step 7.2: While (root!=NULL)
Step 7.2.1: If (ptr->data<root->data)
Step 7.2.1.1: If (root->left=NULL)
Step 7.2.1.1.1: Root->left=ptr
Step 7.2.1.1.2: Exit while loop
Step 7.2.2: Root=root->left
Step 7.2.3: Else
Step 7.2.3.1: If (root->right==NULL)
Step 7.2.3.2: Root->right=ptr
Step 7.2.3.3: Exit while loop
Step 7.2.3.4: Root=root->right
Step 7.2.4: End if
Step 7.3: End While
Step 8: End if
Step 9: Stop

Preorder ()

Step 1: Start
Step 2: If (p=NULL) ie start= NULL
Step 2.1: Tree traversal not possible
Step 3: Else
Step 3.1: Print p->data
65

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

Step 3.2: Preorder (p->left)

Step 3.3: Preorder (p->right)
Step 4: End if
Step 5: Stop

Inorder ()

Step 1: Start
Step 2: If (p=NULL)
Step 2.1: Tree traversal not possible
Step 3: Else
Step 3.1: Inorder (p->left)
Step 3.2: Print p->data
Step 3.3: Inorder (p-
>right)
Step 4: End if
Step 5: Stop

Postorder ()

Step 1: Start
Step 2: If (p==NULL)
Step 2.1: Tree traversal not possible
Step 3: Else
Step 3.1: Postorder (p->left)
Step 3.2: Postorder (p->right)
Step 3.3: Print p->data
Step 4: End if
Step 5: Stop

PROGRAM DEVELOPMENT:

# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
typedef struct BST
{ int data;
struct BST *lchild, *rchild;
} node;
void insert(node *, node *);
void inorder(node *);
void preorder(node *);
void postorder(node *);
66

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

node *search(node *, int, node **);

67

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

int f=0;
void main()
{ int choice;
char ans = 'N';
int key;
node *new_node, *root, *tmp, *parent;
node *get_node();
root = NULL;
clrscr();
printf("\n\n\tProgram For Binary Search
Tree"); printf("\n\n\t ");
do { printf("\
n");
printf("\n\tMenu");
printf("\n\t----");
printf("\n\t1.Create"); printf("\n\
t2.Search"); printf("\n\
t3.Traversals"); printf("\n\
t4.Exit"); printf("\n\tEnter your
choice: "); scanf("%d", &choice);
switch (choice)
{ case 1:
do {
new_node = get_node(); printf("\
tEnter The Element: ");
scanf("%d", &new_node->data);
if (root == NULL) /* Tree is not Created */
root = new_node;
else
insert(root, new_node);
printf("\tWant To enter More Elements?(y/n): ");
scanf(" %c",ans);
ans = getch();
} while (ans == 'y');
break;
case 2:
printf("\tEnter Element to be searched: ");
scanf("%d", &key);
tmp = search(root, key, &parent);
if(tmp!=NULL)
{
printf("\n\tParent of node %d is %d\n", tmp->data, parent->data);
}

68

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

break;
case 3:
if (root == NULL)
printf("Tree Is Not Created");
else {
printf("\n\tThe Inorder display : ");
inorder(root);
printf("\n\tThe Preorder display : ");
preorder(root);
printf("\n\tThe Postorder display : ");
postorder(root);
}
printf("\n");
break;
}
} while (choice != 4);
/*
Get new Node
*/
node *get_node()
{ node *temp;
temp = (node *)
malloc(sizeof(node)); temp->lchild =
NULL;
temp->rchild = NULL;
return temp;
/*
This function is for creating a binary search tree
*/
void insert(node *root, node *new_node) {
if (new_node->data < root->data) {
if (root->lchild == NULL)
root->lchild = new_node;
else
insert(root->lchild, new_node);
}
if (new_node->data > root->data)
{ if (root->rchild == NULL)
root->rchild = new_node;
else
insert(root->rchild, new_node);
}
}
/*
69

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

This function is for searching the node from

70

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

binary Search Tree

*/
node *search(node *root, int key, node **parent)
{ node *temp;
temp = root;
while (temp != NULL)
{ if (temp->data == key)
{ f=1;
printf("\tElement %d is Present", temp->data);
return temp;
}
*parent = temp;
if (temp->data > key)
temp = temp->lchild;
else
temp = temp->rchild;
}
if(f==0)
{
printf("\nElement not [present");
return NULL;
}
}
/*
This function displays the tree in inorder fashion
*/
void inorder(node *temp)
{ if (temp != NULL) {
inorder(temp->lchild);
printf("%d", temp->data);
inorder(temp->rchild);
}
}
/*
This function displays the tree in preorder fashion
*/
void preorder(node *temp)
{ if (temp != NULL)
{ printf("%d", temp->data);
preorder(temp->lchild);
preorder(temp->rchild);
}
}
/*
71

For More Visit : KtuQbank.com | Fair Use Policy

Department of Computer Science
Data Structures Lab Ilahia College of Engineering and Technology

This function displays the tree in postorder fashion

*/
void postorder(node *temp) {
if (temp != NULL) {
postorder(temp->lchild);
postorder(temp->rchild);
printf("%d", temp->data);
}
}

72

For More Visit : KtuQbank.com | Fair Use Policy