PRAMOD KUMAR SAHU -Academy of Technocrats -Data Structure : Stack / Queue
/*Conversion of Infix to Postfix*/
#include<stdio.h>
#include<conio.h>
char infix[30],postfix[30];
char stk[30];
int top=-1;
void push(char ch)
{
stk[++top]=ch;
}
char pop()
{
return (stk[top--]);
}
int type_of_char(char ch)
{
switch(ch)
{
case '(':
return 1;
case ')':
return 2;
case '+':
case '-':
case '*':
case'/':
case '^':
return 3;
default :
return 0;
}
}
int precedence(char ch)
{
switch(ch)
{
case '^':
return 3;
case '*':
case '/':
return 2;
case '+':
case '-':
return 1;
}
15
PRAMOD KUMAR SAHU -Academy of Technocrats -Data Structure : Stack / Queue
}
void main()
{
int i,p=0,ch,prec;
char c;
clrscr();
printf("enter an infix expression");
gets(infix);
for(i=0;infix[i]!=0;i++)
{
ch=type_of_char(infix[i]);
switch(ch)
{
case 0:
postfix[p++]=infix[i];
break;
case 1:
push(infix[i]);
break;
case 2:
c=pop();
while(c!='(')
{
postfix[p++]=c;
c=pop();
}
break;
case 3:
prec=precedence(infix[i]);
while(top!=-1 && prec<=precedence(stk[top]))
{
postfix[p++]=pop();
}
push(infix[i]);
break;
}
}
while(top!=-1)
{
postfix[p++]=pop();
}
postfix[p]='\0';
puts(postfix);
}
16
PRAMOD KUMAR SAHU -Academy of Technocrats -Data Structure : Stack / Queue
/*Program for checking of Palindrome using stack and queue
operations*/
#include<stdio.h>
#include<conio.h>
int top=-1,front=-1,rear=-1;
char stk[10];
char que[10];
void main()
{
void push(char);
void insert(char);
char delete();
char pop();
int i;
char str[30],ch;
clrscr();
printf("enter a string");
gets(str);
for(i=0;str[i]!='\0';i++)
{
push(str[i]);
insert(str[i]);
}
while(top!=-1)
{
if(pop()!=delete())
break;
}
if(top==-1)
printf("not pallindrom");
else
printf("pallindrom");
}
void push(char ch)
{
top=top+1;
stk[top]=ch;
}
void insert(char ch)
{
rear=rear+1;
que[rear]=ch;
}
17
PRAMOD KUMAR SAHU -Academy of Technocrats -Data Structure : Stack / Queue
char pop()
{
return stk[top--];
}
char delete()
{
return que[front++];
}
/*Check string is palindrom or not using stack*/
#include<stdio.h>
#include<conio.h>
int top=-1;
char stk[10];
void main()
{
void push(char);
char pop();
int i;
char str[30],ch;
clrscr();
printf("enter a string");
gets(str);
for(i=0;str[i]!='\0';i++)
{
push(str[i]);
}
for(i=0;i<strlen(str);i++)
{
if((ch=pop())!=str[i])
break;
}
if(i<strlen(str))
printf("not pallindrom");
else
printf("pallindrom");
}
void push(char ch)
{
top=top+1;
stk[top]=ch;
}
char pop()
18
PRAMOD KUMAR SAHU -Academy of Technocrats -Data Structure : Stack / Queue
{
return stk[top--];
}
/*program of evaluation of postfix expression*/
#include<stdio.h>
#include<conio.h>
int stack[20],top=-1;
void push(int);
void evaluate(char ,int ,int);
void main()
{
char postfix[30];
int i,num1,num2,tp;
printf("enter the postfix expression:");
scanf("%s",postfix);
for(i=0;postfix[i]!='\0';i++)
{
tp=gettype(postfix[i]);
switch(tp)
{
case 1:
push(postfix[i]-48);
break;
case 0:
num1=pop();
num2=pop();
evaluate(postfix[i],num1,num2);
break;
}
}
printf("%d",stack[0]);
}
void push(int item)
{
top=top+1;
stack[top]=item;
}
int pop()
{
return (stack[top--]);
}
int gettype(char ch)
{
switch (ch)
19
PRAMOD KUMAR SAHU -Academy of Technocrats -Data Structure : Stack / Queue
{
case '+':
case '-':
case '*':
case '/':
return 0;
default :
return 1;
}
}
void evaluate(char ch,int op1,int op2)
{
int result;
switch(ch)
{
case '+':
result=op1+op2;
break;
case '-':
result=op1-op2;
break;
case '*':
result=op1*op2;
break;
case '/':
result=op1/op2;
break;
}
push(result);
}
20
PRAMOD KUMAR SAHU -Academy of Technocrats -Data Structure : Stack / Queue
Postfix Example
Example 1 : Give postfix form for A = B / C – D.
Solution: A + (B/C) - D
A + (BC/) - D
A+T-D
(A + T) - D
(AT+) – D
S–D Where S = (AT +)
SD –
AT + D –
ABC/+D-. Postfix Expression.
------------------------------------------------------------------------------------------------
Example 2: Convert the expression (A + B ) /( C –D ) to prefix form.
Solution: In this expression the brackets are already specified. Therefore
the conversion looks like:
(AB+) / (CD –)
T/S Where T = (AB +) and S = (CD -)
TS/
AB+CD - /. Postfix Expression
------------------------------------------------------------------------------------------------
Example 3: Give postfix form for (A + B) * C / D.
Solution: (AB+) C / D
T*C/D where T = (AB +)
(T * C) / D
(TC*) / D
S/D
SD /
TC * D /
AB + C * D /-. Postfix Expression.
------------------------------------------------------------------------------------------------
Prefix Example :
Example 4: Give prefix form for A * B + C
Solution: (A*B)+C
21
PRAMOD KUMAR SAHU -Academy of Technocrats -Data Structure : Stack / Queue
(8 AB) + C where T = (AB +)
T+C where T=(* AB)
+ TC
Expanding the expression + TC
+ * ABC Prefix Expression.
------------------------------------------------------------------------------------------------
Example 4: Give prefix form for A/B ^ C + D.
Solution: A / (B ^ C) + D (^ has highest priority)
A / (^ BC) + D
A /T +D
(A /T) + D
(/ AT) + D
S+D where S = (/ AT)
+ SD
Expanding the expression + SD
+ / ATD
+ / A ^ BCD Prefix Expression.
------------------------------------------------------------------------------------------------
Example 4: Give prefix form for (A – B / C) * (D * E - F)
Solution: (A - (B / C)) * ((D * E) – F)
(A - (/ BC)) * ((* DE) – F)
A /T +D
(A - T) * (S – F) where (T = /BC) and S = (* DE)
(- AT) * (- SF)
Q+P where Q = (- AT)
* QP
Expanding the expression *QP
* AT – SF
* - A / BC – SF
* - A / BC - * DEF. Prefix Expression
------------------------------------------------------------------------------------------------
22
