**Introduction:**In the last post I have explained about the infix,prefix,postfix expression. In this post we are going to know about the conversion of infix to postfix expression.

**Infix to Postfix Conversion:**- Consider an infix string x+y*c.Each character of the string is called tokens.
- The algorithm for converting an infix expression to postfix expression is given below.
- We need a stack to solve this problem

**Algorithm for converting infix expression to postfix expression:**- Initialize an empty stack and a Postfix String S.
- Read the tokens from the infix string one at a time from left to right
- If the token is an
**operand**, add it to the Postfix string S. - If the token is a
**left parentheses**, Push it on to the stack - If the token is a
**right parentheses**- Repeatedly Pop the stack and add the poped out element in to the string S until a left parenthesis is encountered;
- Remove the left parenthesis from the stack and ignore it

- If the token is an
**operator**- If the stack is empty push the operator in to the stack
- If the stack is not empty compare the precedence of the operator with the element on top of the stack
- If the operator in the stack has higher precedence than the token Pop the stack and add the poped out element in to the string S. else Push the operator in to the stack
- Repeat this step until the stack is not empty or the operator in the stack has higher precedence than the token

- Repeat this step till all the characters are read.
- After all the characters are read and the stack is not empty then Pop the stack and add the tokens to the string S
- Return the Postfix string S

**Example fo**

**r Converting infix to Postfix Expression:**

Example 1:

Infix String----->A*B+C/D

Solution:

- Initially the stack is empty and the Postfix String S has no characters
- Read the token A.A is a operand so it is added to the string S.now Stack->empty and S->A
- Read the token *.* is an operator.stack is empty so push * in to the stack. now Stack->* and S->A
- Read the token B.B is an operand so it is added to the string S. now Stack->* and S->AB
- Read the token +.+is an operator.compare +and *.* has higher precedence than +. so pop * from the stack and add it to the string S. now Stack->empty and S->AB*.now the stack is empty so push the + in to the stack.now Stack->+ and S->AB*
- Read the token C.C is a operand so it is added to the string S.now Stack->+ and S->AB*C
- Read the token /./ is an operator.compare /and +./ has higher precedence than +. so push / in to the stack . now Stack->+/ and S->AB*C
- Read the token D.D is a operand so it is added to the string S.now Stack->+/ and S->AB*CD
- All the characters are read but the stack is not empty so pop the stack and add the characters to the String. now S->AB*CD/+

Example 2:

Infix String----->A*(B+C)/D

Solution:

- Initially the stack is empty and the Postfix String S has no character.
- Read the token A.A is a operand so it is added to the string S.now Stack->empty and S->A
- Read the token *.* is an operator.stack is empty so push * in to the stack. now Stack->* and S->A
- Read the token (.push the left parentheses in to the stack.
- Read the token B.B is an operand so it is added to the string S. now Stack->* and S->AB
- Read the token +.+is an operator.compare +and *.+ has lower precedence than *.So push + in to the stack. now Stack->*+ and S->AB
- Read the token C.C is an operand so it is added to the string S.now Stack->*+ and S->ABC
- Read the token ). ) is a right parentheses ,Pop the stack and add the + in to the string S. now Stack->* and S->ABC+
- Read the token /./ is an operator.compare /and *./ and * have equal precedence but * comes before /so pop the stack and add * in to the string S.now stack is empty so push / in to the stack . now Stack->/ and S->ABC+*
- Read the token D.D is an operand so it is added to the string S.now Stack->/ and S->ABC+*D
- Now the input string is empty but the stack is not empty so pop the stack and add the characters to the String.now Stack->Empty and S->ABC+*D/

**Exercise fo**

**r Converting infix to Postfix Expression:**

- A+B-C
- A+B*C
- (A+B)*C
- (A+B)*(C-D)
- ((A+B)*C-(D-E))%(F+G)
- A*(B+C/D)
- ((A*B)+(C/D))
- ((A*(B+C))/D)
- (A*(B+(C/D)))
- (2+((3+4)*(5*6)))

hey thnx,now i can convert infix to postfix,thnx for ur help.

ReplyDeletevery helpful...... thanks

ReplyDeleteextremely helfpful

ReplyDeleteno use

Deleteno use

Deletevery helpful

ReplyDeletevery understandable.....thanx....

ReplyDeletethanx for such a easy type code

ReplyDeleteno use......

ReplyDeleteok fine

ReplyDeleteThis is BULLSHIT! I NEED A PROGRAM! WATDAFUCK!

ReplyDeleteThis comment has been removed by the author.

Deletehhhh

DeleteYou have explained it so beautifully.

ReplyDeleteThank yo so much :)

excelent tutorial .. i am bookmarking it :)

ReplyDeletevery gud

ReplyDeleteThis is fine... What to do in the case of unary operators....

ReplyDeletefor example, infix statement: -a+b

what is its postfix statement?????

Thanks

ReplyDeletewhat if the given output should be in step by step solution??? can you help me guyz?

ReplyDeleteC code of infix to postfix http://thecprojectt.blogspot.in/2013/03/c-program-15_27.html

ReplyDeletethanks.... it is easy and understandable

ReplyDeletethanks.. it helps..

ReplyDelete