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 Postfix to Prefix

Conversion from Postfix to Prefix

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

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]!=’�’;i++)
{
ch=instr[i];
if(isdigit(ch))
{push(&stk,ch);
}
else
{
if(ct==1)
{opnd2=pop(&stk);
opnd1=pop(&stk);
outstr[z–]=’�’;
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]!=’�’;i++,z++)
{
outstr[i]=outstr[z];
outstr[z]=’ ‘;
}
outstr[i]=’�’;
}

Comments are closed
x Close

Like Us On Facebook

You cannot copy content of this page.