Oops! It appears that you have disabled your Javascript. In order for you to see this page as it is meant to appear, we ask that you please re-enable your Javascript!

Conversion from Prefix to Postfix

Conversion from Prefix to Postfix

October 2, 2012 Comments Off on Conversion from Prefix to Postfix By admin

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]=’�’;
}

Comments are closed
x Close

Like Us On Facebook

You cannot copy content of this page.