EX:NO:5 IMPLEMENTATION OF EVALUATING POSTFIX

EXPRESSION,INFIX TO POSTFIX CONVERSION

A) IMPLEMENTATION OF EVALUATING POSTFIX EXPRESSION

#include<stdio.h>
#include<conio.h>
#define size 100
int a[size];
int top=-1;
void push(int x)
{
if(top>=size-1)
printf("Stack Overflow\n");
top++;
a[top]=x;
}
int pop()
{
int x;
if(top<0)
{
printf("Stack Underflow\n");
return -1;
}
x=a[top];
top--;
return x;
}
int operator(char symbol)
{
if(symbol=='+'||symbol=='-'||symbol=='*'||symbol=='/')
return 1;
return 0;
}
int(evaluate(char* expression))
{
int i=0;
char symbol=expression[i];
int a,b,res;
while(symbol!='\0')
{
if(isdigit(symbol))
{
int num=symbol-'0';
push(num);
 }
else if(operator(symbol))
{
b=pop();
a=pop();
switch(symbol)
{
case '+':
res=a+b;
break;
case '-':
res=a-b;
break;
case '*':
res=a*b;
break;
case '/':
res=a/b;
break;
}
push(res);
}
i++;
symbol=expression[i];
}
res=pop();
return res;
}
int main()
{
char expression[10];
int res;
clrscr();
printf("Enter a expression:");
scanf("%s",expression);
res=evaluate(expression);
printf("Result=%d\n",res);
getch();
return 0;
}
OUTPUT:
Enter a expression:934*8+4/-
Result=4
 B) IMPLEMENTATION OF EVALUATING INFIX TO POSTFIX
CONVERSION
#include<stdio.h>
#define size 50
char s[size];
int top=-1;
void push(char elem)
{
s[++top]=elem;
}
char pop()
{
return(s[top--]);
}
int pr(char elem)
{
switch(elem)
{
case '#':
return 0;
case '(':
return 1;
case '+':
case '-':
return 2;
case '*':
case '/':
return 3;
}
return 0;
}
void convert(char* infix,char* postfix)
{
char ch,elem;
int i=0,k=0;
push('#');
while((ch=infix[i++])!='\n')
{
if(ch=='(')
push(ch);
else if(isalnum(ch))
postfix[k++]=ch;
else if(ch==')')
{
while(s[top]!='(')
 postfix[k++]=pop();
elem=pop();
}
else
{
while(pr(s[top])>=pr(ch))
postfix[k++]=pop();
push(ch);
}
}
while(s[top]!='#')
postfix[k++]=pop();
postfix[k]=0;
}
int evaluate(char* postfix)
{
char ch;
int i=0,a,b;
while((ch=postfix[i++])!=0)
{
if(isdigit(ch))
push(ch-'0');
else
{
b=pop();
a=pop();
switch(ch)
{
case '+':
push(a+b);
break;
case '-':
push(a-b);
break;
case '*':
push(a*b);
break;
case '/':
push(a/b);
break;
}
}
}
return s[top];
}
void main()
{
char infix[50],postfix[50];
clrscr();
printf("Enter the infix expression:");
fgets(infix,50,stdin);
convert(infix,postfix);
printf("Postfix expression:%s",postfix);
top=-1;
printf("\nResult of evaluation is=%d",evaluate(postfix));
getch();
}
OUTPUT:
Enter the infix expression:7+(3*4)
Postfix expression:734*+
Result of evaluation is=19
EX:NO:6 IMPLEMENTATION OF BINARY SEARCH TREE

#include<stdio.h>
int max=15;
char t[]={'\0','D','A','F','E','B','R','T','G','Q','\0','\0','V','\0','J','L'};
int rchild(int i)
{
if(t[i]!='\0'&&((2*i)+1)<=max)
return(2*i)+1;
return -1;
}
int lchild(int i)
{
if(t[i]!='\0'&&(2*i)<=max)
return(2*i);
return -1;
}
void preorder(int i)
{
if(i>0&&t[i]!='\0')
{
printf("%c ",t[i]);
preorder(lchild(i));
preorder(rchild(i));
}
}
void postorder(int i)
{
if(i>0&&t[i]!='\0')
{
postorder(lchild(i));
postorder(rchild(i));
printf("%c ",t[i]);
}
}
void inorder(int i)
{
if(i>0&&t[i]!='\0')
{
inorder(lchild(i));
printf("%c ",t[i]);
inorder(rchild(i));
}
}
int main()
{
clrscr();
printf("Preorder:\n");
preorder(1);
printf("\nPostorder:\n");
postorder(1);
printf("\nInorder:\n");
inorder(1);
getch();
return 0;
}

OUTPUT:

Preorder:
DAEGQBFRVTJL
Postorder:
GQEBAVRJLTFD
Inorder:
GEQABDVRFJTL
EX:NO:7 IMPLEMENTATION OF AVL TREE

#include<stdio.h>
typedef struct node
{
int data;
struct node* l,*r;
int ht;
}node;
node* insert(node*,int);
node* delete(node*,int);
void inorder(node*);
int height(node*);
node* rotateright(node*);
node* rotateleft(node*);
node* RR(node*);
node* LL(node*);
node* LR(node*);
node* RL(node*);
int BF(node*);
node* insert(node* T,int x)
{
if(T==NULL)
{
T=(node*)malloc(sizeof(node));
T->data=x;
T->l=NULL;
T->r=NULL;
}
else if(x>T->data)
{
T->r=insert(T->r,x);
if(BF(T)==-2)
if(x>T->r->data)
T=RR(T);
else
T=RL(T);
}
else if(x<T->data)
{
T->l=insert(T->l,x);
if(BF(T)==2)
if(x<T->l->data)
T=LL(T);
else
 T=LR(T);
}
T->ht=height(T);
return(T);
}
node* delete(node* T,int x)
{
node* p;
if(T==NULL)
return NULL;
else if(x>T->data)
{
T->r=delete(T->r,x);
if(BF(T)==2)
if(BF(T->l)>=0)
T=LL(T);
else
T=LR(T);
}
else if(x<T->data)
{
T->l=delete(T->l,x);
if(BF(T)==-2)
if(BF(T->r)<=0)
T=RR(T);
else
T=RL(T);
}
else
{
if(T->r!=NULL)
{
p=T->r;
while(p->l!=NULL)
p=p->l;
T->data=p->data;
T->r=delete(T->r,p->data);
if(BF(T)==2)
if(BF(T->l)>=0)
T=LL(T);
else
T=LR(T);
}
else
return(T->l);
}
 T->ht=height(T);
return(T);
}
int height(node* T)
{
int lh,rh;
if(T==NULL)
return 0;
if(T->l==NULL)
lh=0;
else
lh=1+T->l->ht;
if(T->r==NULL)
rh=0;
else
rh=1+T->r->ht;
if(lh>rh)
return(lh);
return(rh);
}
node* rotateright(node* x)
{
node* y;
y=x->l;
x->l=y->r;
y->r=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node* rotateleft(node* x)
{
node* y;
y=x->r;
x->r=y->l;
y->l=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node* RR(node* T)
{
T=rotateleft(T);
return(T);
}
node* LL(node* T)
{
T=rotateright(T);
return(T);
}
node* LR(node* T)
{
T->l=rotateleft(T->l);
T=rotateright(T);
return(T);
}
node* RL(node* T)
{
T->r=rotateright(T->r);
T=rotateleft(T);
return(T);
}
int BF(node* T)
{
int lh,rh;
if(T==NULL)
return 0;
if(T->l==NULL)
lh=0;
else
lh=1+T->l->ht;
if(T->r==NULL)
rh=0;
else
rh=1+T->r->ht;
return(lh-rh);
}
void inorder(node* T)
{
if(T!=NULL)
{
inorder(T->l);
printf("%d(BF=%d)",T->data,BF(T));
inorder(T->r);
}
}
void main()
{
node* root=NULL;
int x,n,i,op;
clrscr();
printf("1.Create\n2.Insert\n3.Delete\n4.Display\n5.Exit\n");
 while(1)
{
printf("Enter choice:");
scanf("%d",&op);
switch(op)
{
case 1:
printf("Enter the number of elements:");
scanf("%d",&n);
printf("Enter tree data:");
root=NULL;
for(i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
break;
case 2:
printf("Enter a data:");
scanf("%d",&x);
root=insert(root,x);
break;
case 3:
printf("Enter a data:");
scanf("%d",&x);
root=delete(root,x);
break;
case 4:
printf("The AVL tree is:\n");
inorder(root);
printf("\n");
break;
case 5:
exit(1);
}
}
getch();
}
OUTPUT:

1.Create
2.Insert
3.Delete
4.Display
5.Exit
Enter choice:1
Enter the number of elements:4
Enter tree data:50 10 20 15
Enter choice:4
The AVL tree is:
10(BF=-1)15(BF=0)20(BF=1)50(BF=0)
Enter choice:2
Enter a data:8
Enter choice:4
The AVL tree is:
8(BF=0)10(BF=0)15(BF=0)20(BF=1)50(BF=0)
Enter choice:3
Enter a data:8
Enter choice:4
The AVL tree is:
10(BF=-1)15(BF=0)20(BF=1)50(BF=0)
Enter choice:5
EX:NO:8 IMPLMENTATION OF EAPS USING PRIORITY QUEUES

#include<stdio.h>
#include<math.h>
#define MAX 100
void swap(int*,int*);
void display(int[],int);
void insert(int[],int,int,int);
int delete(int[],int,int);
void insert(int a[],int heapsize,int data,int lb)
{
int i,p;
int parent(int);
if(heapsize==MAX)
{
printf("Queue is FULL!\n");
return;
}
i=lb+heapsize;
a[i]=data;
while(i>lb&&a[p=parent(i)]<a[i])
{
swap(&a[p],&a[i]);
i=p;
}
}
int delete(int a[],int heapsize,int lb)
{
int data,i,l,r,max_child,t;
int left(int);
int right(int);
if(heapsize==1)
{
printf("Queue is pty!\n");
return 0;
}
t=a[lb];
swap(&a[lb],&a[heapsize-1]);
i=lb;
heapsize--;
while(1)
{
if((l=left(i))>=heapsize)
break;
 if((r=right(i))>=heapsize)
max_child=l;
else
max_child=(a[l]>a[r])?l:r;
if(a[i]>=a[max_child])
break;
swap(&a[i],&a[max_child]);
i=max_child;
}
return t;
}
int parent(int i)
{
float p;
p=((float)i/2.0)-1.0;
return ceil(p);
}
int left(int i)
{
return (2*i+1);
}
int right(int i)
{
return (2*i+2);
}
void display(int a[],int n)
{
int i;
if(n==0)
{
printf("Queue is Empty!\n");
return;
}
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
void swap(int* p,int* q)
{
int temp;
temp=*p;
*p=*q;
*q=temp;
}
void main()
{
 int lb,ch,num,n,a[MAX],data,s;
ch=n=lb=0;
clrscr();
printf("1.Insert\n2.Delete\n3.Display\n4.Exit\n");
while(1)
{
printf("Enter choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("Enter data to be inserted:");
scanf("%d",&data);
insert(a,n,data,lb);
n++;
break;
case 2:
s=delete(a,n+1,lb);
if(s!=0)
printf("The deleted value is:%d\n",s);
if(n>0)
n--;
break;
case 3:
display(a,n);
break;
case 4:
exit(1);
}
}
getch();
}
OUTPUT:

1.Insert
2.Delete
3.Display
4.Exit
Enter choice:1
Enter data to be inserted:3
Enter choice:1
Enter data to be inserted:6
Enter choice:1
Enter data to be inserted:8
Enter choice:3
836
Enter choice:2
The deleted value is:8
Enter choice:3
63
Enter choice:4
EX:NO:9 IMPLEMENTATION OF DIJKSTRAS ALGORITHM

#include<stdio.h>
#define INF 9999
#define MAX 10
void D(int G[MAX][MAX],int n,int start);
void D(int G[MAX][MAX],int n,int start)
{
int cost[MAX][MAX],distance[MAX],pred[MAX];
int visited[MAX],count,mindistance,nextnode,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INF;
else
cost[i][j]=G[i][j];
for(i=0;i<n;i++)
{
distance[i]=cost[start][i];
pred[i]=start;
visited[i]=0;
}
distance[start]=0;
visited[start]=1;
count=1;
while(count<n-1)
{
mindistance=INF;
for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i])
{
mindistance=distance[i];
nextnode=i;
}
visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i])
{
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}
for(i=0;i<n;i++)
 if(i!=start)
{
printf("\nDistance from source to %d:%d",i,distance[i]);
}
}
int main()
{
int G[MAX][MAX],i,j,n,u;
n=5;
clrscr();
G[0][0]=0;
G[0][1]=0;
G[0][2]=1;
G[0][3]=2;
G[0][4]=0;
G[1][0]=0;
G[1][1]=0;
G[1][2]=2;
G[1][3]=0;
G[1][4]=0;
G[2][0]=1;
G[2][1]=2;
G[2][2]=0;
G[2][3]=1;
G[2][4]=3;
G[3][0]=2;
G[3][1]=0;
G[3][2]=1;
G[3][3]=0;
G[3][4]=0;
G[4][0]=0;
G[4][1]=0;
G[4][2]=3;
G[4][3]=0;
G[4][4]=0;
u=0;
D(G,n,u);
getch();
return 0;
}
OUTPUT:
Distance from source to 1:3
Distance from source to 2:1
Distance from source to 3:2
Distance from source to 4:4
EX:NO:10 IMPLEMENTATION OF PRIMS ALGORITHM

typedef int bool;

#define false 0
#define true 1
#include<limits.h>
#include<stdio.h>
#include<conio.h>
#define V 5
int minkey(int key[],bool mstset[])
{
int v;
int min=INT_MAX,min_index;
for(v=0;v<V;v++)
if(mstset[v]==0&&key[v]<min)
min=key[v],min_index=v;
return min_index;
}
int printmst(int parent[],int graph[V][V])
{
int i;
printf("edge\tweight\n");
for(i=1;i<V;i++)
printf("%d-%d\t%d\n",parent[i],i,graph[i][parent[i]]);
}
void primmst(int graph[V][V])
{
int i;
int parent[V];
int key[V];
int count;
bool mstset[V];
for(i=0;i<V;i++)
key[i]=INT_MAX,mstset[i]=0;
key[0]=0;
parent[0]=-1;
for(count=0;count<V-1;count++)
{
int v;
int u=minkey(key,mstset);
mstset[u]=1;
 for(v=0;v<V;v++)
if(graph[u][v]&&mstset[v]==0&&graph[u][v]<key[v])
parent[v]=u,key[v]=graph[u][v];
}
printmst(parent,graph);
}
int main()
{
int graph[V][V]={{0,2,0,6,0},{2,0,3,8,5},{0,3,0,0,7},{6,8,0,0,9},{0,5,7,9,0}};
clrscr();
primmst(graph);
getch();
return 0;
}

OUTPUT:

edge weight
0-1 2
1-2 3
0-3 6
1-4 5
EX:NO:11 IMPLEMENTATION OF LINEAR SEARCH AND BINARY
SEARCH
A) LINEAR SEARCH
#include<stdio.h>
int search(int arr[],int n,int x)
{
int i;
for(i=0;i<n;i++)
{
if(arr[i]==x)
return i;
}
return -1;
}
void main()
{
int arr[]={2,4,6,8,10};
int x=8;
int n=sizeof(arr)/sizeof(arr[0]);
int result=search(arr,n,x);
clrscr();
if(result!=-1)
printf("Element is present at index %d",result);
else
printf("Element is not present in the array");
getch();
}

OUTPUT:

Element is present at index 3

 B) BINARY SEARCH

#include<stdio.h>
int binarysearch(int array[],int x,int low,int high)
{
while(low<=high)
{
int mid=low+(high-low)/2;
if(array[mid]==x)
return mid;
if(array[mid]<x)
low=mid+1;
else
low=mid-1;
}
return -1;
}
void main()
{
int array[]={1,3,5,7,9};
int n=sizeof(array)/sizeof(array[0]);
int x=9;
int result=binarysearch(array,x,0,n-1);
clrscr();
if(result==-1)
printf("Not found");
else
printf("Element is found at index %d",result);
getch();
}

OUTPUT:

Element is found at index 4

EXNO:12 IMPLEMENTATION OF INSERTION SORT AND
SELECTION SORT
A) INSERTION SORT
#include<stdio.h>
int main()
{
int a[100],n,i,j,temp;
clrscr();
printf("\nEnter the number of elements:");
scanf("%d",&n);
printf("Enter the array elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
for(j=i;j>0&&a[j-1]>a[j];j--)
{
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}
printf("Insertion sort result is:");
for(i=0;i<n;i++)
printf("%d ",a[i]);
getch();
return 0;
}

OUTPUT:

Enter the number of elements:5

Enter the array elements:9
2
8
7
6
Insertion sort result is:2 6 7 8 9
 B) SELECTION SORT
#include<stdio.h>
int main()
{
int a[100],n,i,j,temp;
clrscr();
printf("\nEnter the number of elements:");
scanf("%d",&n);
printf("Enter the arrray elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("Selection sort result is:");
for(i=0;i<n;i++)
printf("%d ",a[i]);
getch();
return 0;
}

OUTPUT:

Enter the number of elements:5

Enter the arrray elements:2
5
9
6
8
Selection sort result is:2 5 6 8 9
EX:NO:13 IMPLEMENTATION OF MERGE SORT

#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[50], R[50];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
 k++;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
clrscr();
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
getch();
return 0;
}
OUTPUT:
Given array is
12 11 13 5 6 7

Sorted array is
5 6 7 11 12 13

EX:NO:14 IMPLEMENTATION OF OPEN ADDRESSING

 (LINEAR PROBING AND QUADRATIC PROBING)
#include <stdio.h>
#include <conio.h>
int tsize;
int hasht(int key)
{
int i ;
i = key%tsize ;
return i;
}
int rehashl(int key)
{
int i ;
i = (key+1)%tsize ;
return i ;
}
int rehashq(int key, int j)
{
int i ;
i = (key+(j*j))%tsize ;
return i ;
}
void main()
{
int key,arr[20],hash[20],i,n,s,op,j,k ;
clrscr() ;
printf ("Enter the size of the hash table:");
scanf ("%d",&tsize);
printf ("Enter the number of elements:");
scanf ("%d",&n);
for (i=0;i<tsize;i++)
hash[i]=-1 ;
printf ("Enter Elements:");
for (i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("1.Linear Probing\n2.Quadratic Probing\n3.Exit\n");
while(1)
{
printf("Enter your option:");
scanf("%d",&op);
switch(op)
{
case 1:
for (i=0;i<tsize;i++)
 hash[i]=-1 ;
for(k=0;k<n;k++)
{
key=arr[k] ;
i = hasht(key);
while (hash[i]!=-1)
{
i = rehashl(i);
}
hash[i]=key ;
}
printf("The elements in the array are:\n");
for (i=0;i<tsize;i++)
{
printf("Element at position %d:%d\n",i,hash[i]);
}
break ;
case 2:
for (i=0;i<tsize;i++)
hash[i]=-1 ;
for(k=0;k<n;k++)
{
j=1;
key=arr[k] ;
i = hasht(key);
while (hash[i]!=-1)
{
i = rehashq(i,j);
j++ ;
}
hash[i]=key ;
}
printf("The elements in the array are:\n");
for (i=0;i<tsize;i++)
{
printf("Element at position %d:%d\n",i,hash[i]);
}
break ;
case 3:
exit(1);
}
}
getch() ;
}

OUTPUT:
Enter the size of the hash table:5
Enter the number of elements:4
Enter Elements:50
70
93
76
1.Linear Probing
2.Quadratic Probing
3.Exit
Enter your option:1
The elements in the array are:
Element at position 0:50
Element at position 1:70
Element at position 2:76
Element at position 3:93
Element at position 4:-1
Enter your option:2
The elements in the array are:
Element at position 0:50
Element at position 1:70
Element at position 2:76
Element at position 3:93
Element at position 4:-1
Enter your option:3