DATA STRUCTURE & ALGORITHM PCC-CS 391

54

20. /* program for conversion of:

1. infix into its postfix form
2. infix into its prefix form
3. Evaluation of postfix expression
4. Evaluation of prefix expression
operators supported '+,-,*,/,%,^,(,)
operands supported -- all single character operands
*/
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#define MAX 50
typedef struct stack
{
int data[MAX];
int top;
}stack;

int precedence(char);
void init(stack *);
int empty(stack *);
int full(stack *);
int pop(stack *);
void push(stack *,int );
int top(stack *); //value of the top element
void infix_to_prefix(char infix[],char prefix[]);
void infix_to_postfix(char infix[],char postfix[]);
void eval_prefix(char prefix[]);
void eval_postfix(char postfix[]);
int evaluate(char x,int op1,int op2);

void main()
{ char infix[30],postfix[30],prefix[30];

BISWAJIT_MANDI 11000223012 B.TECH_IT_3RD SEM

DATA STRUCTURE & ALGORITHM PCC-CS 391

55

printf("\nEnter an infix expression : ");

gets(infix);
infix_to_postfix(infix,postfix);
infix_to_prefix(infix,prefix);
printf("\nPostfix : %s\n prefix: %s ",postfix,prefix);
printf("\nPrefix Evaluation : ");
eval_prefix(prefix);
printf("\nPostfix evaluation : ");
eval_postfix(postfix);
getch();
}
void infix_to_prefix(char infix[],char prefix[])
{ int i,j;
char temp,in1[30];
// reverse the infix expression and store it in in1[]
for(i=strlen(infix)-1,j=0;i>=0;i--,j++)
in1[j]=infix[i];
in1[j]='\0';
// reverse the direction of brackets
for(i=0;in1[i]!='\0';i++){
if(in1[i]=='(')
in1[i]=')';
else
if(in1[i]==')')
in1[i]='(';
}
// convert from infix to postfix
infix_to_postfix(in1,prefix);
//reverse the final expression
for(i=0,j=strlen(prefix)-1;i<j;i++,j--)
{
temp=prefix[i];

BISWAJIT_MANDI 11000223012 B.TECH_IT_3RD SEM

DATA STRUCTURE & ALGORITHM PCC-CS 391

56

prefix[i]=prefix[j];
prefix[j]=temp;
}
}
void infix_to_postfix(char infix[],char postfix[])
{ stack s;
char x;
int i,j;//i-index for infix[],j-index for postfix
char token;
init(&s);
j=0;
for(i=0;infix[i]!='\0';i++)
{ token=infix[i];
if(isalnum(token))
postfix[j++]=token;
else
if(token == '(')
push(&s,'(');
else
if(token == ')')
while((x=pop(&s))!='(')
postfix[j++]=x;
else
{
while(precedence(token)<=precedence(top(&s)) &&
!empty(&s))
{
x=pop(&s);
postfix[j++]=x;
}
push(&s,token);
}

BISWAJIT_MANDI 11000223012 B.TECH_IT_3RD SEM

DATA STRUCTURE & ALGORITHM PCC-CS 391

57

}
while(!empty(&s))
{
x=pop(&s);
postfix[j++]=x;
}
postfix[j]='\0';
}

void eval_postfix(char postfix[])

{ stack s;
char x;
int op1,op2,val,i;
init(&s);
for(i=0;postfix[i]!='\0';i++){
x=postfix[i];
if(isalpha(x))
{ printf("\nEnter the value of %c : ",x);
scanf("%d",&val);
push(&s,val);
}
else
{ //pop two operands and evaluate
op2=pop(&s);
op1=pop(&s);
val=evaluate(x,op1,op2);
push(&s,val);
}
}
val=pop(&s);
printf("\nvalue of expression = %d",val);
}
void eval_prefix(char prefix[]){

BISWAJIT_MANDI 11000223012 B.TECH_IT_3RD SEM

DATA STRUCTURE & ALGORITHM PCC-CS 391

58

stack s;
char x;
int op1,op2,val,i;
init(&s);
for(i=strlen(prefix)-1;i>=0;i--){
x=prefix[i];
if(isalpha(x))
{ printf("\nEnter the value of %c : ",x);
scanf("%d",&val);
push(&s,val);
}
else{
//pop two operands and evaluate
op1=pop(&s);
op2=pop(&s);
val=evaluate(x,op1,op2);
push(&s,val);
} }
val=pop(&s);
printf("\nvalue of expression = %d",val);
}
int evaluate(char x,int op1,int op2){
if(x=='+') return(op1+op2);
if(x=='-') return(op1-op2);
if(x=='*') return(op1*op2);
if(x=='/') return(op1/op2);
if(x=='%') return(op1%op2);

}
int precedence(char x)
{ if(x == '(') return(0);
if(x == '+' || x == '-') return(1);

BISWAJIT_MANDI 11000223012 B.TECH_IT_3RD SEM

DATA STRUCTURE & ALGORITHM PCC-CS 391

59

if(x == '*' || x == '/' || x == '%') return(2);

return(3);
}
void init(stack *s)
{
s->top=-1;
}
int empty(stack *s)
{
if(s->top==-1) return(1);
return(0);
}
int full(stack *s)
{
if(s->top==MAX-1) return(1);
return(0);
}
void push(stack *s,int x){
s->top=s->top+1;
s->data[s->top]=x;
}
int pop(stack *s)
{ int x;
x=s->data[s->top];
s->top=s->top-1;
return(x);
}
int top(stack * p){
return(p->data[p->top]);
}

BISWAJIT_MANDI 11000223012 B.TECH_IT_3RD SEM

 60

Output:

Sabuj manna 11000223030

 61

21. Write a C program to create a stack and do push and pop operations.
#include<stdio.h>
#include<stdlib.h>
structstack{
int size;
int top;
int *arr;
};
//Creating stackdatatype
int check_full(struct stack*ptr){
if(ptr->top==ptr->size-1){
return 1;
}
else{
return 0;
}
}
voidpush(struct stack*ptr, intvar){
if (check_full(ptr) == 1){
//Stack is already full so it will result in stack overflow
printf("StackOverflow, couldnot push%d elementintostack\n"
,var);
}
else{
//Iterating top and inserting the element
ptr->top++;
ptr->arr[ptr->top]=var;

Sabuj manna 11000223030

 62

printf("%dhasbeensuccessfullypushed intothe stack\n"

,var);
}
}
int check_empty(structstack*ptr){
if(ptr->top==-1){
return 1;
}
else{
return0;148
}
}
int pop(structstack*ptr){
int var;
if(check_empty(ptr)==1){
// stack is empty so there is nothing to pop
printf("Stackunderflow,Can'tpop.\n");
return 0;
}
else{
// storing the popped value in a variable and decrementing top by 1
var=ptr->arr[ptr->top];
ptr->top--;
printf("%dhasbeenpoppedfromthestack\n"
,var);
return var;
}

Sabuj manna 11000223030

 63

}
int main(){
int n,i,var;
struct stack *s;
s=(structstack*)malloc(sizeof(structstack));
s->size = 10;
s->top = -1;
s->arr=(int*)malloc(s->size*(sizeof(int)));
printf("The stack has been successfully created.\n");
printf("Enter how many elements you want to push:");
scanf("%d"
,&n);
for(i=0; i<n;i++){
printf("Enterthevalueyouwanttopush:");
scanf("%d"
,&var);
push(s,var);
}
printf("\n\n");
printf("Enter how many elements you want to pop:");
scanf("%d",&n);
for(i=0; i<n;i++){
pop(s);
}
return 0;
}

Sabuj manna 11000223030

 64

Output:

Sabuj manna 11000223030

 65

22. Write a C program to create a stack and do push and pop operations
and
peek the stack.
#include<stdio.h>
#include<stdlib.h>
structstack{
int size;
int top;
int *arr;
};
int check_empty(structstack*s){
if(s->top==-1){
return 1;
}
else{
return 0;
}
}
int check_full(struct stack*s){
if(s->top==s->size -1){
return 1;
}
else
{
return 0;
}
}
voidpush(struct stack*s,intval)

Sabuj manna 11000223030

 66

{
if (check_full(s) == 1)
{
printf("StackOverflow, cannotpush%delementinto thestack\n"
,val);
}
else
{
s->top++;
s->arr[s->top]=val;
printf("%dhasbeensuccessfullypushed intothe stack\n"
,val);
}152
}
int pop(structstack*s)
{
if (check_empty(s) == 1)
{
printf("StackUnderflow, cannotpop\n");
return 0;
}
else
{
int val =s->arr[s->top];
s->top--;
printf("%dhasbeensuccessfullypopped fromthestack\n"
,val);

Sabuj manna 11000223030

 67

return val;
}
}
int peek(structstack*s,intval)
{
if(s->top-val+ 1<0)
{
printf("Positionnot valid\n");
return -1;
}
else
{
printf("Element%d=%d\n"
, val, s->arr[s->top-val+ 1]);
}
}
int main()
{
int n, v, value;
struct stack *s;
s=(structstack*)malloc(sizeof(structstack));
s->size = 10;
s->top = -1;
s->arr=(int*)malloc(s->size*sizeof(int));
printf("Enter how many elements you want to push:");
scanf("%d"
,&n);

Sabuj manna 11000223030

 68

for(inti=0; i<n;i++)
{
printf("Enterthevalueyouwanttopush:");
scanf("%d"
,&v);
push(s, v);
}
printf("\n"); 153
printf("Enter how many elements you want to pop:");
scanf("%d"
,&value);
for(intj=0;j <value; j++)
{
pop(s);
}
for(inti=1; i<=s->top+1; i++)
{
peek(s, i);
}
return 0;
}

Sabuj manna 11000223030

 69

Output:

Sabuj manna 11000223030

 70

23. Write a C program to create a stack and find stack top and stack
bottom.
#include<stdio.h>
#include<stdlib.h>
Struct stack
{
int size;
int top;
int *arr;
};
int check_empty(structstack*s)
{
if(s->top==-1)
{
return 1;
}
else
{
return 0;
}
}
int check_full(struct stack*s)
{
if(s->top==s->size -1)
{
return 1;
}
else

Sabuj manna 11000223030

 71

{
return 0;
}
}
Void push(struct stack*s,intval)
{
if (check_full(s) == 1)
{
printf("StackOverflow, cannotpush%delementinto thestack\n"
,val);
}
else
{
s->top++;
s->arr[s->top]=val;
printf("%d has been successfully pushed into the stack\n"
,val);
}
}
int pop(struct stack*s)
{
if (check_empty(s) == 1)
{
printf("StackUnderflow, cannotpop\n");
return 0;
}
else

Sabuj manna 11000223030

 72

{
int val =s->arr[s->top];
s->top--;
printf("%d has been successfully popped from the stack\n"
,val);
return val;
}
}
int peek(struct stack*s,intval)
{
if(s->top-val+ 1<0)
{
printf("Position not valid\n");
return -1;
}
else
{
printf("Element %d=%d\n"
, val, s->arr[s->top-val+ 1]);
}
}
int stack_top(struct stack* s)
{
return(s->arr[s->top]);
}
int stack_bottom(struct stack*s)
{

Sabuj manna 11000223030

 73

return(s->arr[0]);
}
int main()
{
int n, v, value;
struct stack *s;
s=(struct stack*)malloc(sizeof(struct stack));
s->size = 10;
s->top = -1;
s->arr=(int*)malloc(s->size*sizeof(int));
printf("Enter how many elements you want to push:");
scanf("%d"
,&n);
for(inti=0; i<n;i++)
{
printf("Enterthevalueyouwanttopush:");
scanf("%d"
,&v);
push(s, v);
}
printf("\n");
for(inti=1; i<=s->top+1; i++)
{
peek(s, i);
}
printf("StackTop=%d\n"
,stack_top(s));

Sabuj manna 11000223030

 74

printf("StackBottom=%d"
,stack_bottom(s));
return 0;
}

Output:

Sabuj manna 11000223030

 75

4.Write a C program to create a stack and do all the operations using

linkedlists.
#include<stdio.h>
#include<stdlib.h>
Struct node
{
int data;
struct node *next;
};
intis_full(struct node *ptr)
{
struct node *s;
s=(struct node *)malloc(sizeof(struct node));
//Evenafterallocating memorydynamically,ifitisNULLitmeansmemory
//hasbeenexhausted
if (s == NULL)
{
return 1;
}
else
{
return 0;
}
}
intis_empty(structnode*ptr)
{
if (ptr==NULL)
{

Sabuj manna 11000223030

 76

return 1;
}
else
{
return 0;
}
}
structnode *push( struct node*ptr,int var)
{
if (is_full(ptr)==1)
{
printf("Stack Overflow\n");
}
else
{
//Creating a node and linking it with the previous top node
structnode *temp;
temp=(structnode *)malloc(sizeof(structnode));
temp->data=var;158
temp->next=ptr;
ptr=temp;
return temp;
}
}
voidstack_traversal(structnode *ptr)
{
printf("\n Stack->\n");

Sabuj manna 11000223030

 77

while ( ptr!=NULL)
{
printf("Element:%d\n"
,ptr->data);
ptr=ptr->next;
}
}
//Topisapointer
//variablesowhateverchangeshappenstotopwillnotreflectinmainfunctionunless
//and untill address of top is passed into the function
int pop(structnode**ptr)//Doubledereferencingdoneoneforpointerandsecond
//fordereferencing addressoftop
{//Anotheroptionisusingtopasaglobalvariable
if (is_empty(*ptr)==1)
{
printf("Stack underflow");
}
else
{
structnode *temp=*ptr;
//Assigningapointerto thenodetobedeletedandupdatedtopnodetototop->next
int data=(*ptr)->data;
*ptr=(*ptr)->next;
free(temp);
return data;
}
}
int main()

Sabuj manna 11000223030

 78

{
struct node *top;
top =NULL;
int n,val;
printf("Enter the number of stacks:");
scanf("%d",&n);
for(int i=0; i<n;i++)
{
printf("Enter the value you want to insert:");
scanf("%d"
,&val);
top=push(top,val);
}
stack_traversal(top);
printf("Enter the number of stacks you want to pop:");
scanf("%d"
,&n);
for(inti=0; i<n;i++)
{
printf("%d element has bee n popped\n"
,pop(&top));
}
stack_traversal(top);
return 0;
}
Output:

Sabuj manna 11000223030

 79

Sabuj manna 11000223030