Prefix to Infix conversion using Stack
Conversion of a Prefix Expression into an Infix Expression
We can use the following steps...
Step 1: Read the prefix expression from right to left .
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 between the operands
and push the resulted string back to stack.
Step 4: Repeat steps 2 and 3 till the end of the prefix expression.
Step 5: EXIT
Example
Consider the following Prefix Expression...
+ - A B * C D
The above prefix expression can be converted into infix expression using Stack data Structure as follows...
The equivalent infix Expression is as follows...
( ( A - B ) + ( C * D ) )
C program to convert prefix to infix expression
# include <stdio.h>
# include <conio.h>
# include <string.h>
# define MAX 100
void pop (char*);
void push(char*);
char stack[MAX] [MAX];
int top = -1;
int main()
{
char s[MAX], str1[MAX], str2[MAX], str[MAX];
char s1[2],temp[2];
int i=0;
printf("\Enter the prefix expression; ");
gets(s);
strrev(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] ='(';
temp[1] ='\0';
strcpy(str, temp);
strcat(str, str1);
temp[0] = s[i];
temp[1] = '\0';
strcat(str,temp);
strcat(str, str2);
temp[0] =')';
temp[1] ='\0';
strcat(str,temp);
push(str);
}
else
{
temp[0]=s[i];
temp[1]='\0';
strcpy(s1, temp);
push(s1);
}
i++;
}
printf("\nThe infix expression is: %s", stack[0]);
}
void pop(char *a1)
{
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 "Prefix Expression to an Infix Expression Converstion"
Post a Comment