Infix notation : Infix notation is the common arithmetic and logical notation, in which operator is written between operand.
e.g.
1+2
1+2*3
Postfix notation: Operators are written after their operands.
e.g.
1 2 3 + * 4 /
Some Examples of conversion of infix to postfix expression
| Infix | Postfix |
|---|---|
| A * B + C / D
A * (B + C) / D |
A B * C D / +
A B C + * D / |
Infix to postfix conversion of expression code in C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
/* infix to postfix expression conversion code by Codingstreet.com */ #include<stdio.h> #include<string.h> int push(char *stack,char val,int *top,int *size); int pop(char *stack,int *top); int isstack_empty(int *top); int isstack_full(int *top,int *size); int isstack_empty(int *top){ if((*top)==0) return 1; return 0; } int isstack_full(int *top,int *size){ if((*top)==(*size)-1) return 1; return 0; } int push(char *stack,char val,int *top,int *size){ if(isstack_full(top,size)){ return 0; } stack[(*top)++]=val; return 1; } int pop(char *stack,int *top){ if(isstack_empty(top)){ return -1; } else return stack[--(*top)]; } int get_precedence(char c){ switch(c){ case '+': case '-': return 1; case '*': case '/': case '%': return 2; case '^': return 0; case '(': return -1; default : return -2; } } void infix_to_postfix(char *instring){ int i=0,top,size,pred1,pred2; char c,c2; int len=strlen(instring); if(instring==NULL) return; char stack[len-1]; top=0;size=len-1; while(instring[i]!='\0'){ c=instring[i]; if(c==' ') {i++;continue; } else if(c=='('){ push(stack,c,&top,&size); } else if(c=='+' || c=='-' || c=='*' || c=='/' || c=='%'||c=='^'){ if(isstack_empty(&top)) { push(stack,c,&top,&size); } else { pred1=get_precedence(stack[top-1]); pred2=get_precedence(c); while(pred2<=pred1 && !isstack_empty(&top)){ c2=pop(stack,&top); printf("%c",c2); pred2=get_precedence(stack[top-1]); pred1=get_precedence(c); } push(stack,c,&top,&size); } } else if(c==')'){ while(stack[top-1]!='('){ c2=pop(stack,&top); printf("%c",c2); } pop(stack,&top); } else { printf("%c",c); } i++; } while(!isstack_empty(&top)){ c=pop(stack,&top); printf("%c",c); } printf("\n"); } int main(){ char str[]="((a+t)*((b+(a+c))^(c+d)))"; printf("\nInput string :%s \nOutput: ",str); infix_to_postfix(str); return 0; } |