Conversion from Postfix to Prefix

Application of Stacks

Conversion from Postfix to Prefix

The algorithm for converting a Postfix expression to Prefix notation is as follows:

•  Accept a postfix string from the user.
• Start scanning the string from left to right one character at a time.
• If it is an operand, push it in stack.
• If it is an operator, pop opnd2, opnd1 and concatenate them in the order (optr, opnd1, opnd2) as follows:

strcpy(arr,optr);
strcat(arr,opnd1);
stract(arr,opnd2);

Push the result in the stack.

• Repeat these steps until arr of input postfix string ends.
• Pop the remaining element of the stack, which is the required Prefix notation equivalent to a given Postfix notation.

Program to convert Postfix expression to Prefix:

#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 postfix_to_prefix(char instr[],char outstr[]);

void main()
{
char str[MAX],resstr[MAX];
clrscr();
printf(“\nEnter a postfix string?”);
gets(str);
printf(“\nPostfix string: %s”,str);
postfix_to_prefix(str,resstr);
printf(“\nPrefix 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 postfix_to_prefix(char instr[],char outstr[])
{
int i,j,ct=1,z=MAX-1;
char ch,opnd1,opnd2;
struct stack stk;
stk.top=-1;
for(i=0;instr[i]!=’\0′;i++)
{
ch=instr[i];
if(isdigit(ch))
{push(&stk,ch);
}
else
{
if(ct==1)
{opnd2=pop(&stk);
opnd1=pop(&stk);
outstr[z--]=’\0′;
outstr[z--]=opnd2;
outstr[z--]=opnd1;
outstr[z--]=ch;
ct++;
}
else
{
opnd2=pop(&stk);
outstr[z--]=opnd2;
outstr[z--]=ch;
}
}
}
for(i=0,z=z+1;outstr[z]!=’\0′;i++,z++)
{
outstr[i]=outstr[z];
outstr[z]=’ ‘;
}
outstr[i]=’\0′;
}