CBSE’s class XII computer science syllabus also happens to have infix to postfix conversions (and vice versa) as an application of a stack…without actually coding. Weird, or shall I say, good – because THAT sort of coding will knock the socks of most people. Anyway, I’ve given solutions to the conversion exercises given by our school. I hope they’re correct, and in case they aren’t, please do leave a comment to correct me.
Postfix, also known as the Reverse Polish Notation, is something some friends of mine have a called a pain in the butt. Indeed, if you try to follow the algorithm given in the notes given in our school, you’ll find the procedure is not *that* clear. Although it’s based on Djikistra’s ‘shunting yard’ algorithm, you’ll find that this explanation is WAY better the one given in our notes. The Sumita Arora book’s description is OK too, so you may go in for that if you’re physically incapable of making a small mouse click (and perfectly capable of lifting a heavy book).
Infix to Postfix
1. X + Y * Z ^ P – (X / Y + Z)
S. No.  Input  Action  Stack Status  Postfix Expression 
1  X  X  
2  +  Push  +  X 
3  Y  +  XY  
4  *  Push  +*  XY 
5  Z  +*  XYZ  
6  ^  Push  +*^  XYZ 
7  P  +*^  XYZP  
8  –  Pop current stack 
XYZP^*+  
Push  –  
9  (  Push  (  XYZP^*+ 
10  X  (  XYZP^*+X  
11  /  Push  (/  XYZP^*+X 
12  Y  (/  XYZP^*+XY  
13  +  Pop & Print / 
(  XYZP^*+XY/ 
Push +  (+  
14  Z  (+  XYZP^*+XY/  
15  )  Pop & Print + 
(  XYZP^*+XY/+ 
Pop (  –  XYZP^*+XY/+  
16  End  Pop –  XYZP^*+XY/+ 
2. (A + B ^ D) / (E – F) + G
S. No.  Input  Action  Stack Status  Postfix Expression 
1  (  Push  (  
2  A  (  A  
3  +  Push  (+  A 
4  B  (+  AB  
5  ^  Push  (+^  AB 
6  D  (+^  ABD  
7  )  Pop & Print current stack operands 
(  ABD^+ 
Pop (  ABD^+  
8  /  Push  /  ABD^+ 
9  (  Push  /(  ABD^+ 
10  E  /(  ABD^+E  
11  –  Push  /(  ABD^+E 
12  F  /(  ABD^+EF  
13  )  Pop & Print – 
/(  ABD^+EF 
Pop (  /  ABD^+EF  
14  +  Pop & Print / 
ABD^+EF/  
Push +  +  ABD^+EF/  
15  G  +  ABD^+EF/G  
16  End  Pop +  ABD^+EF/G+ 
3. NOT (A OR B) AND C
S. No.  Input  Action  Stack Status  Postfix Expression 
1  NOT  Push  NOT  
2  (  Push  NOT (  
3  A  NOT (  A  
4  OR  Push  NOT ( OR  A 
5  B  NOT ( OR  AB  
6  )  Pop & Print OR 
NOT (  AB OR 
Pop (  NOT  AB OR  
7  AND  Pop NOT  AB OR NOT  
Push AND  AND  AB OR NOT  
8  C  AND  AB OR NOT  
9  End  Pop & Print AND 
AB OR NOT AND 
4. ( !(TRUE && FALSE)  (TRUE  FALSE) )
S. No.  Input  Action  Stack Status  Postfix Expression 
1  (  Push  (  
2  !  Push  ( !  
3  (  Push  ( ! (  
4  TRUE  ( ! (  TRUE  
5  &&  Push  &&  TRUE 
6  FALSE  TRUE FALSE  
7  )  Pop & Print && 
( ! (  TRUE FALSE && 
Pop (  ( !  TRUE FALSE && 

8    Pop & Print ! 
(  TRUE FALSE && ! 
Push   (   TRUE FALSE && ! 

9  (  Push  (  (  TRUE FALSE && ! 
10  TRUE  (  (  TRUE FALSE && ! TRUE 

11    Push  (  (   TRUE FALSE && ! TRUE 
12  FALSE  (  (   TRUE FALSE && ! TRUE FALSE 

13  )  Pop & Print  
(  (  TRUE FALSE && ! TRUE FALSE  
Pop (  (   TRUE FALSE && ! TRUE FALSE  

14  )  Pop & Print  
(  TRUE FALSE && ! TRUE FALSE   
Pop (  TRUE FALSE && ! TRUE FALSE   
Postfix to Infix
1. 20 8 4 / 2 3 + * –
S. No.  Input  Action  Stack Status 
1  20  20  
2  8  20 8  
3  4  20 8 4  
4  /  Pop 4  20 8 
Pop 8  20  
Push 8 / 4  20 2  
5  2  20 2 2  
6  3  20 2 2 3  
7  +  Pop 3  20 2 2 
Pop 2  20 2  
Push 2 + 3  20 2 5  
8  *  Pop 5  20 2 
Pop 2  20  
Push 2 * 5  20 10  
9  –  Pop 10  20 
Pop 20  
Push 20 – 10  10 
2.* FALSE FALSE TRUE TRUE NOT AND TRUE AND OR AND
S. No.  Input  Action  Stack Status 
1  FALSE  FALSE  
2  FALSE  FALSE FALSE  
3  TRUE  FALSE FALSE TRUE 

4  TRUE  FALSE FALSE TRUE TRUE 

5  NOT  Pop TRUE  FALSE FALSE TRUE 
Push NOT TRUE  FALSE FALSE TRUE FALSE 

6  AND  Pop FALSE  FALSE FALSE TRUE 
Pop TRUE  FALSE FALSE  
Push TRUE AND FALSE 
FALSE FALSE FALSE 

7  TRUE  FALSE FALSE FALSE TRUE 

8  AND  Pop TRUE  FALSE FALSE FALSE 
Pop FALSE  FALSE FALSE  
Push FALSE AND TRUE 
FALSE FALSE FALSE 

9  AND  Pop FALSE  FALSE FALSE 
Pop FALSE  FALSE  
Push FALSE AND FALSE 
FALSE FALSE  
10  OR  Pop FALSE  FALSE 
Pop FALSE  
Push FALSE OR FALSE 
FALSE  
11  AND  Input Error!  FALSE 
* Here, the given question is wrong because enough operands have not
been given for successful completion of algorithm. However, I decided
to put it up anyway so that the method could be demonstrated. Note that
if the last AND is removed, then the question becomes perfectly valid.
January 6, 2008
uhm…u’ve made the error in the last question. u’ve repeated an AND. step 9 should have been an OR, not an AND.
Check the question, u’ll see.
January 8, 2008
What the _____ !
why are you wasting your time in all this, at this time of the year you should be studying
January 10, 2008
@Rach: Righto. Sorry for that. Too lazy to edit it now though.
@Tikna: Erm, yeah. Well, I’ve been doing a bit, but I must admit, I’m pretty distracted…
January 14, 2008
hey why are people talking about studying (at this point of time or at any point of time)???? its the time to CHILL before your parents get to know your pre board results.party on guys……