Prefix to Infix Conversion
Algorithm of Prefix to Infix
This algorithm is a non-tail recursive method. 1.The reversed input string is completely pushed into a stack. prefixToInfix(stack) 2.IF stack is not empty a. Temp -->pop the stack b. IF temp is a operator Write a opening parenthesis to output prefixToInfix(stack) Write temp to output prefixToInfix(stack) Write a closing parenthesis to output c. ELSE IF temp is a space -->prefixToInfix(stack) d. ELSE Write temp to output IF stack.top NOT EQUAL to space -->prefixToInfix(stack)
Prefix to Infix conversion
Example
*+a-bc/-de+-fgh
Expression | Stack | |||
---|---|---|---|---|
*+a-bc/-de+-fgh | NuLL | |||
*+a-bc/-de+-fg |
| |||
*+a-bc/-de+-f |
| |||
*+a-bc/-de+- |
| |||
*+a-bc/-de+ |
| |||
*+a-bc/-de |
| |||
*+a-bc/-d |
| |||
*+a-bc/- |
| |||
*+a-bc/ |
| |||
*+a-bc |
| |||
*+a-b |
| |||
*+a- |
| |||
*+a |
| |||
*+ |
| |||
* |
| |||
End |
|
Postfix to Infix implementation in c
#include <string.h> #include <ctype.h> #include <conio.h> char opnds[50][80],oprs[50]; int topr=-1,topd=-1; pushd(char *opnd) { strcpy(opnds[++topd],opnd); } char *popd() { return(opnds[topd--]); } pushr(char opr) { oprs[++topr]=opr; } char popr() { return(oprs[topr--]); } int empty(int t) { if( t == 0) return(1); return(0); } void main() { char prfx[50],ch,str[50],opnd1[50],opnd2[50],opr[2]; int i=0,k=0,opndcnt=0; clrscr(); printf("Give an Expression = "); gets(prfx); printf(" Given Prefix Expression : %s\n",prfx); while( (ch=prfx[i++]) != '\0') { if(isalnum(ch)) { str[0]=ch; str[1]='\0'; pushd(str); opndcnt++; if(opndcnt >= 2) { strcpy(opnd2,popd()); strcpy(opnd1,popd()); strcpy(str,"("); strcat(str,opnd1); ch=popr(); opr[0]=ch;opr[1]='\0'; strcat(str,opr); strcat(str,opnd2); strcat(str,")"); pushd(str); opndcnt-=1; } } else { pushr(ch); if(opndcnt==1)opndcnt=0; /* operator followed by single operand*/ } } if(!empty(topd)) { strcpy(opnd2,popd()); strcpy(opnd1,popd()); strcpy(str,"("); strcat(str,opnd1); ch=popr(); opr[0]=ch;opr[1]='\0'; strcat(str,opr); strcat(str,opnd2); strcat(str,")"); pushd(str); } printf(" Infix Expression: "); puts(opnds[topd]); getch(); }