Application of Stacks
Conversion from Prefix to Postfix
The algorithm for converting a Prefix expression to a Postfix notation is as follows:
- Accept a prefix string from the user.
- Start scanning the string from right one character at a time.
- If it is an operand, push it in stack.
- If it is an operator, pop opnd1, opnd2 and concatenate them in the order (opnd1, opnd2, optr) as follows:
strcpy(arr,opnd1);
strcat(arr,opnd2);
stracat(arr,optr);
Push the result in the stack.
- Repeat these steps until arr of input prefix string ends.
- Pop the remaining element of the stack, which is the required Postfix notation equivalent to a given Prefix notation.
Program to convert Prefix expression to Postfix:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 20
struct stack
{
int top;
char arr[MAX];
};
void push(struct stack *,char);
char pop(struct stack *);
int isdigit(char);
void prefix_to_postfix(char instr[],char outstr[]);
void main()
{
char str[MAX],resstr[MAX],temp[MAX];
int i,z;
clrscr();
printf(“nEnter a prefix string?”);
gets(str);
for(i=0;str[i]!=’�’;i++);
for(i=i-1,z=0;i>=0;z++,i–)
temp[z]=str[i];
temp[z]=’�’;
printf(“nPrefix string: %s”,str);
prefix_to_postfix(temp,resstr);
printf(“nPostfix string: %s”,resstr);
getch();
}
void push(struct stack *s,char ch)
{
if(s->top==MAX-1)
{printf(“Stack Overflow!”);
exit(1);
}
s->arr[++(s->top)]=ch;
}
char pop(struct stack *s)
{
if(s->top==-1)
{printf(“Stack Underflow!”);
exit(1);
}
return(s->arr[(s->top)–]);
}
int isdigit(char ch)
{return(ch>=’0′ && ch<=’9′);
}
void prefix_to_postfix(char instr[],char outstr[])
{
int i,j,ct=1,z=0;
char ch,opnd1,opnd2;
struct stack stk;
stk.top=-1;
for(i=0;instr[i]!=’�’;i++)
{
ch=instr[i];
if(isdigit(ch))
{push(&stk,ch);
}
else
{
if(ct==1)
{opnd1=pop(&stk);
opnd2=pop(&stk);
outstr[z++]=opnd1;
outstr[z++]=opnd2;
outstr[z++]=ch;
ct++;
}
else
{
opnd2=pop(&stk);
outstr[z++]=opnd2;
outstr[z++]=ch;
}
}
}
outstr[z]=’�’;
}