Infix To Postfix Conversion using C Programming

First, we will learn about Polish notation. Based on the relative position of the operator with respect to operands, the expression is known as either prefix or infix or postfix expression.

• prefix if the operator is placed before its two operands
• infix if the operator is placed at the middle of the two operands
• postfix if the operator is placed after the two operands

For example, the prefix: +AB , infix: A+B , postfix: AB+

Using infix notation, one can't tell the order in which operators should be applied by only looking at the expression. In this context, postfix notation is quite better because in postfix notation operands appear before the operator, there is no need to consider operator precedence.

So we will learn now how to perform infix to postfix conversion.

---

Algorithm for Infix to Postfix Conversion

---

1. Scan the characters of infix expression from left to right.
2. If the character is an operand, append it to postfix expression.
3. Else,
4.     If the precedence of the scanned operator is 
			greater than the precedence of the operator 
			in the stack(or the stack is empty), push it.
5.     Else, Pop the operator from the stack until the precedence 
			of the scanned operator is less-equal to the precedence 
			of the operator residing on the top of the stack. 
			Push the scanned operator to the stack.
6. If the scanned character is an '(', push it to the stack.
7. If the scanned character is an ')', pop and output from the stack until an '(' is encountered.
8. Read the next character and repeat from step 2.
9. Pop and output from the stack until it is not empty.

---

Example

---

Now, consider the infix example: A+(B*C-(D/E^F)) and follow the algorithm. The steps are shown below.

iteration	symbol	stack	postfix exp	comments
1	A		A	operand A in postfix exp
2	+	+	A	push + in stack
3	(	+(	A	push ( in stack
4	B	+(	AB	operand B in postfix exp
5	*	+(*	AB	push * in stack
6	C	+(*	ABC	operand C in postfix exp
7	-	+(-	ABC*	pop * because * has highest priority than -
8	(	+(-(	ABC*	push ( in stack
9	D	+(-(	ABC*D	operand D in postfix exp
10	/	+(-(/	ABC*D	push / in stack
11	E	+(-(/	ABC*DE	operand E in postfix exp
12	^	+(-(/^	ABC*DE	push ^ in stack because ^ has highest priority than /
13	F	+(-(/^	ABC*DEF	operand F in postfix exp
14	)	+(-	ABC*DEF^/	) is encountered pop the elements upto (
15	)	+	ABC*DEF^/-	) is encountered pop the elements upto (
16			ABC*DEF^/-+	input finished, remaining stack elements will be popped and placed in postfix exp.

Infix To Postfix Conversion Using C

#include <stdio.h> #include <stdlib.h> #include <string.h> #define SIZE 1024 int top=-1; void push(char *s,char elem) { s[++top]=elem; } char pop(char *s) { return(s[top--]); } int priority(char ch) { if(ch=='^') { return(5); } else if(ch=='*' || ch=='/') { return(4); } else if(ch=='+' || ch=='-') { return(3); } else { return(2); } } void infix_pofix(char *infix) { int length; char *s; static int index=0,pos=0; char symbol,temp; char *postfix; s=(char *)malloc(sizeof(char)*SIZE); postfix=(char *)malloc(sizeof(char)*100); length=strlen(infix); while(index<length) { symbol=infix[index]; switch(symbol) { case '(': push(s,symbol); break; case ')': temp=pop(s); while(temp!='(') { postfix[pos]=temp; pos++; temp=pop(s); } break; case '^': case '+': case '-': case '*': case '/':while(priority(s[top])>=priority(symbol)) { temp=pop(s); postfix[pos]=temp; pos++; } push(s,symbol); break; default:postfix[pos++]=symbol; break; } index++; } while(top>=0) { temp=pop(s); postfix[pos++]=temp; } postfix[pos++]='\0'; printf("\nequivalent postfix expression\n"); printf("%s",postfix); } int main() { char *infix; infix=(char *)malloc(sizeof(char)*SIZE); printf("\n enter the infix expression:"); scanf("%s",infix); infix_pofix(infix); return 0; }

Happy Exploring!