Calcutta Institute of Engineering and

Management
24/1A, Chandi Ghosh Road, Tollygunge, Kolkata-
700040

Stream: BCA Year: 2nd Semester:3rd

Paper Name: Data Structure & Algorithm Lab

Paper Code: BCAC393

Name GOURAV JAIN

University Roll 29901220025
Number
 Data Structure & Algorithm Lab (BCAC393)
2021
ROLL 29901220025
NAME GOURAV JAIN

Learning outcome: Students will be able to perform different operations on stack and
queue.

ASSIGNMENT: II

Sl. Program Listing

No
1 Write a menu driven program to perform various operations of Stack using array.
2 Write a program to convert an infix expression to its equivalent postfix expression.
3 Write a program to evaluate a postfix expression.

4 Write a menu driven program to perform various operations Linear Queue using
array.
5 Write a menu driven program to perform various operations Circular Queue using
array.
PROGRAM 1.
Write a menu driven program to perform various operations of Stack using array.

Code:-
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<conio.h>
int stack[10];
int n,x ,choice,top,i;

void push();
void pop();
void display();
int main()
{

top = -1;
printf("\n Enter the size of Stack :");
scanf("%d",&n);
printf("\nStack implement");
do
{
printf("\n1.PUSH\n2.POP\n3.DISPLAY\n4.EXIT\n");

printf("\nEnter the choice : ");

scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
 {
display();
break;
}
case 4:
{
break;
}
default:
{
printf("\nInvalid choice\n");
}
}
}
while(choice!=4);
return 0;
}
//add an element to the stack
void push()
{
if( top >= n-1)
{
printf("\nStack overflow");
}
else
{
printf("Enter a value to te pushed :");
scanf("%d",&x);
top++;
stack[top]=x;

}
}
//removes an element from the stack
void pop()
{
if(top <= -1)
{
printf("\nStack underflow\n");

}
else
 {
printf("\nThe popped element is %d",stack[top]);
top--;

}
}
//display the stack
void display()
{
if(top >= 0)
{
// Print the stack
printf("\nELEMENTS IN THE STACK\n\n");
for(i = top ; i >= 0 ; i--)
printf("%d\t",stack[i]);
}
else
{
printf("\nEMPTY STACK\n");
}
}

Output:-
PROGRAM :-2
Write a program to convert an infix expression to its equivalent
postfix expression.

Code:
#include<stdio.h>
#include<string.h>
char stack[50];
int top=-1;
void post(char infix[]);
void push(char);
char pop();

int main()
{
char infix[25];
printf("\nENTER THE INFIX EXPRESSION = ");
gets(infix);
post(infix);
// getch();
}
//adds an operator to stack
void push(char symb)
{
if(top>=49)
{
printf("\nSTACK OVERFLOW");
//getch();
return;
}
else
{
top=top+1;
stack[top]=symb;
}
}
//pops an operation from stack
char pop()
{
char item;
 if(top==-1)
{
printf("\nSTACK IS EMPTY");
//getch();
return(0);
}
else
{
item=stack[top];
top--;
}
return(item);
}
//converts the given expresion to postfix
int preced(char ch)
{
if(ch==47)
{
return(5);
}
else if(ch==42)
{
return(4);
}
else if(ch==43)
{
return(3);
}
else
return(2);
}
void post(char infix[])
{
int l;
int index=0,pos=0;
char symbol,temp;
char postfix[40];
l=strlen(infix);
push('#');
while(index<l)
{

symbol=infix[index];
switch(symbol)
 {
case '(': push(symbol);
break;
case ')': temp=pop();
while(temp!='(')
{
postfix[pos]=temp;
pos++;
temp=pop();
}
break;
case '+':
case '-':
case '*':
case '/':
case '^':
while(preced(stack[top])>=preced(symbol))
{
temp=pop();
postfix[pos]=temp;
pos++;
}
push(symbol);
break;
default: postfix[pos++]=symbol;
break;
}
index++;
}
while(top>0)
{
temp=pop();
postfix[pos++]=temp;
}
postfix[pos++]='\0';
puts(postfix);
return;
}

Output:-
PROGRAM :3
Write a program to evaluate a postfix expression.

Code:-
#include<stdio.h>
#include<conio.h>
#include<string.h>
#define MAX 50

int stack[MAX];
char post[MAX];
int top=-1;
void push(int tmp);
void evaluate(char c);
int main()
{
int i,l;
printf("\nEnter postfix expression to evaluate : ");
gets(post); //getting a postfix
l=strlen(post); //string length
for(i=0;i<l;i++)
{
if(post[i]>='0'&& post[i]<='9')
{
push(i); //element is a number push

}
//if element is an operator
if(post[i]=='+'|| post[i]=='-
'||post[i]=='*'||post[i]=='/'||post[i]=='^'||post[i]=='%')
{
evaluate(post[i]);

}
}
//print the result from top
printf("\n\nResult :: %d",stack[top]);
getch();
}
void push(int tmp)
{
//incrementing top
 top++;
//casting the string to its integer value
stack[top]=(int)(post[tmp]-48);

}
void evaluate(char c)
{
int a, b, ans;
a=stack[top];
stack[top]='\0';
top--;
b=stack[top];
stack[top]='\0';
top--;
//check operator been passed to evaluate
switch(c)
{
case'+':
ans=b+a;
break;
case'-':
ans=b-a;
break;
case'*':
ans=b*a;
break;
case'/':
ans=b/a;
break;
case'^':
ans=b^a;
break;
case'%':
ans=b%a;
break;

default:
ans=0;

}
top++;
//short the answer at top
stack[top]=ans;
}
Output:-
PROGRAM :-4
Write a menu driven program to perform various operations Linear
Queue using array.

Code:-
#include<stdio.h>
#include<stdlib.h>
#define MAX 10

int queue_arr[MAX];
int rear=-1;
int front=-1;

void insert(int item);

int del();
int peek();
void display();
int isFull();
int isEmpty();

int main()
{
int choice,item;
while(1)
{
printf("\n1.Insert\n");
printf("2.Delete\n");
printf("3.Display element at the front\n");
printf("4.Display all elements of the queue\n");
printf("5.Quit\n");
printf("\nEnter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1:
printf("\nInput the element for adding in queue : ");
scanf("%d",&item);
insert(item);
break;
case 2:
item=del();
printf("\nDeleted element is %d\n",item);
 break;
case 3:
printf("\nElement at the front is %d\n",peek());
break;
case 4:
display();
break;
case 5:
exit(1);
default:
printf("\nWrong choice\n");
}
}

return 0;

void insert(int item)

{
if( isFull() )
{
printf("\nQueue Overflow\n");
return;
}
if( front == -1 )
front=0;
rear=rear+1;
queue_arr[rear]=item ;
}
//remove an element from the queue
int del()
{
int item;
if( isEmpty() )
{
printf("\nQueue Underflow\n");
exit(1);
}
item=queue_arr[front];
front=front+1;
return item;
}
//aads an element to the queue
int peek()
{
if( isEmpty() )
{
printf("\nQueue Underflow\n");
exit(1);
}
return queue_arr[front];
}
//deallocates memory
int isEmpty()
{
if( front==-1 || front==rear+1 )
return 1;
else
return 0;
}

int isFull()
{
if( rear==MAX-1 )
return 1;
else
return 0;
}

void display()
{
int i;
if ( isEmpty() )
{
printf("\nQueue is empty\n");
return;
}
printf("\nQueue is :\n\n");
for(i=front;i<=rear;i++)
printf("%d ",queue_arr[i]);
printf("\n\n");
}

Output:-
PROGRAM:-5
Write a menu driven program to perform various operations Circular
Queue using array.

CODE:-
#include<conio.h>
# include<stdio.h>
# define MAX 5
int cqueue_arr[MAX];
int front = -1;
int rear = -1;
//aads an elements to the queue
void insert(int item)
{
if((front == 0 && rear == MAX-1) || (front == rear+1))
{
printf("Queue Overflow \n");
return;
}
if (front == -1)
{
front = 0;
rear = 0;
}
else
{

if(rear == MAX-1)
rear = 0;
else
rear = rear+1;
}
cqueue_arr[rear] = item ;
}
//remove an element from the queue
void del()
{
if (front == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",cqueue_arr[front]);
 if(front == rear)
{
front = -1;
rear=-1;
}
else
{
if(front == MAX-1)
front = 0;
else
front = front+1;
}
}
//display element in a queue
void display()
{
int front_pos = front,rear_pos = rear;
if(front == -1)
{
printf("Queue is empty\n");
return;
}
printf("Queue elements :\n");
if( front_pos <= rear_pos )
while(front_pos <= rear_pos)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
else
{
while(front_pos <= MAX-1)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
front_pos = 0;
while(front_pos <= rear_pos)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
}
printf("\n");
}
int main()
{
int choice,item;
do
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 :
printf("Input the element for insertion in queue : ");
scanf("%d", &item);
insert(item);
break;
case 2 :
del();
break;
case 3:
display();
break;
case 4:
break;
default:
printf("Wrong choice\n");
}
}
while(choice!=4);
return 0;
}

Output:-
------------------------------------x-------------------------------------