Algorithm for infix to postfix expression conversion using stack with example.

Algorithm for infix to postfix expression conversion-

1. Push left parenthesis '(' into the stack and add right parenthesis ')' at the end of infix expression.

2. Scan expressions from left to right and repeat steps from (3) to (6) for each element of expression until the stack will be empty.

3. If a  operand occurred then add it to the post fix expression.

4. If left parenthesis '(' encountered then push it into the stack.

5. If an operator then performed following steps :-

(a) repeatedly pop each operator from stack which has higher or equal precedence then input operator.

(b) push result and then input operator into the stack.

6. If right parenthesis ')' occurred then perform following steps:-

a. Repeatedly pop each operator from stack until left parenthesis '('  will occurred.

b. Remove left parenthesis '(' from stack and do not add it into P.

7. Exit.

Change following infix expression into prefix and postfix expression.

1.) 5/2 + 4^2 * 3
Sol:- Given expression,
I = 5/2 + 4^2 * 3
Prefix :- oab
= 5/2 + 4^2 * 3
= 5/2 + ^42 * 3
= /52 + ^42 * 3
= /52 + *^423
= +/52*^423
Postfix :- abo
= 5/2 + 4^2 * 3
= 5/2 + 42^ * 3
= 52/ + 42^ * 3
= 52/ + 42^3*
= 52/42^3*+
Using Stack:-

Given expression I = 5/2 + 4^2 * 3)
Sr No	Scanned Symbol	Postfix Expression P	Stack
1	---	---	(
2	5	5	(
3	/	5	(/
4	2	5 2	(/
5	+	52/	(+
6	4	52/ 4	(+
7	^	52/ 4	(+^
8	2	52/ 4 2	(+^
9	*	52/ 42^	(+*
10	3	52/ 42^ 3	(+*
11	)	52/42^3*+	---

2.) ((a*b)/c) - d * e/f
Sol:- Given expression,
I = ((a*b)/c) - d * e/f
Prefix:-
((a*b)/c) - d * e/f
= (*ab /c) - d * e/f
= /*abc - d * e/f
= /*abc - *d e/f
= /*abc - /*def
= -/*abc/*def
Postfix :-
= ((a*b)/c)- d * e/f
= (ab* /c) - d * e/f
= ab*c/ - d * e/f
= ab*c/ - de* /f
= ab*c/ - de*f/
= ab*c/de*f/-

Using stack:-

Given expression I = ((a*b)/c)-d*e/f)
Sr No	Scanned Symbol	Postfix Expression P	Stack
1	---	---	(
2	(	---	((
3	(	---	(((
4	a	a	(((
5	*	a	(((*
6	b	a b	(((*
7	)	ab*	((
8	/	ab*	((/
9	c	ab* c	((/
10	)	ab*c/	(
11	-	ab*c/	(-
12	d	ab*c/ d	(-
13	*	ab*c/ d	(-*
14	e	ab*c/ d e	(-*
15	/	ab*c/ de*	(-/
16	f	ab*c/ de* f	(-/
17	)	ab*c/de*f/-	---

3.) ((a&&b) >c) !! ((d!!e) <f)
Sol:- Given expression,
I = ((a&&b) >c) !! ((d!!e) <f)
Prefix:-
= ((a&&b) >c) !! ((d!!e) <f)
= (&&ab >c) !! (!!de <f)
= >&&abc !! <!!def
= !!>&&abc<!!def
Postfix:-
((a&&b) >c) !! ((d!!e) <f)
= (ab&& >c) !! (de!! <f)
= ab&&c> !! de!!f<
= ab&&c>de!!f<!!

4.) (A+((B-C)*(D-E))+F+G) $ (H-J)
Sol:- Given expression,
I = (((A+((B-C)*(D-E))+F)+G) $ (H-J)
Prefix:-
I = (((A+ ((B-C) * (D-E))+F)+G) $ (H-J)
= (((A+(-BC * -DE))+F)+G) $ (H-J)
= (((A + *-BC-DE) +F)+G) $ (H-J)
= ((+A*-BC-DE +F)+G) $ (H-J)
= (++A*-BC-DEF +G) $ -HJ
= +++A*-BC-DEFG $ -HJ
= $+++A*-BC-DEFG-HJ
Postfix:-
= (((A+((B-C) * (D-E))+F)+G) $ (H-J)
= (((A+ (BC- * DE-)) +F)+G) $ (H-J)
= (((A+ BC-DE-*) +F)+G) $ HJ-
= ((ABC-DE-*+ +F)+G) $ HJ-
= (ABC-DE-*+F+ +G) $ HJ-
= ABC-DE-*+F+G+HJ-$