Conversion of a Postfix Expression into an Prefix Expression
We can use the following steps...
Step 1: Read the postfix expression from left to right .
Step 2: If the symbol is an operand, then push it onto the stack.
Step 3: If the symbol is an operator,
pop two symbols from the stack
and create it as a string by placing the operator in front of the operands
and push the resulted string back to stack.
Step 4: Repeat steps 2 and 3 till the end of the postfix expression.
Step 5: EXIT
Example
Consider the following Postfix Expression...
A B - C D * +
The above postfix expression can be converted into prefix expression using Stack data Structure as follows...
The equivalent prefix Expression is as follows...
+ - A B * C D
C program to convert postfix to prefix expression
# include <stdio.h>
# include <conio.h>
# include <string.h>
#define MAX 100
void pop (char *a1);
void push(char *str);
char stack[MAX][MAX];
int top =-1;
main()
{
char s[MAX], str1[MAX], str2[MAX], str[MAX];
char s1[2], temp[2];
int i = 0;
printf("Enter the postfix expression; ");
gets (s);
while(s[i]!='\0')
{
/*skip whitespace, if any */
if (s[i] == ' ')
i++;
if(s[i] == '^' || s[i] == '*' || s[i] == '-' || s[i]== '+' || s[i] == '/')
{
pop (str1);
pop (str2);
temp[0] = s[i];
temp[1] = '\0';
strcpy (str, temp);
strcat(str, str2);
strcat(str, str1);
push(str);
}
else
{
temp[0] = s[i];
temp[1] = '\0';
strcpy (s1, temp);
push (s1);
}
i++;
}
printf("\n The prefix expression is: %s", stack[0]);
}
void pop(char*a1)
{
if(top == -1)
{
printf("\nStack is empty");
return ;
}
else
{
strcpy (a1, stack[top]);
top--;
}
}
void push (char *str)
{
if(top == MAX - 1)
printf("\nstack is full");
else
{
top++;
strcpy(stack[top], str);
}
}
0 Comment to "Postfix to Prefix Expression"
Post a Comment