Google PlusFacebookTwitter

Class 12 Comp Sci Stuff : Postfix Conversion

By on Jan 5, 2008 in On A Whim | 4 comments

Share On GoogleShare On FacebookShare On Twitter

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 Print X
2 + Push + X
3 Y Print + XY
4 * Push +* XY
5 Z Print +* XYZ
6 ^ Push +*^ XYZ
7 P Print +*^ XYZP
8 Pop
& Print

current stack

XYZP^*+
Push
9 ( Push -( XYZP^*+
10 X Print -( XYZP^*+X
11 / Push -(/ XYZP^*+X
12 Y Print -(/ XYZP^*+XY
13 + Pop
& Print /
-( XYZP^*+XY/
Push + -(+
14 Z Print -(+ 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 Print ( A
3 + Push (+ A
4 B Print (+ AB
5 ^ Push (+^ AB
6 D Print (+^ ABD
7 ) Pop
& Print current stack operands
( ABD^+
Pop ( ABD^+
8 / Push / ABD^+
9 ( Push /( ABD^+
10 E Print /( ABD^+E
11 Push /(- ABD^+E
12 F Print /(- ABD^+EF
13 ) Pop
& Print –
/( ABD^+EF-
Pop ( / ABD^+EF-
14 + Pop
& Print /
ABD^+EF-/
Push + + ABD^+EF-/
15 G Print + 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 Print NOT ( A
4 OR Push NOT ( OR A
5 B Print 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 Print 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 Print ( ! ( TRUE
5 && Push && TRUE
6 FALSE Print TRUE FALSE
7 ) Pop
& Print &&
( ! ( TRUE
FALSE &&
Pop ( ( ! TRUE
FALSE &&
8 || Pop
& Print !
( TRUE
FALSE && !
Push || ( || TRUE
FALSE && !
9 ( Push ( || ( TRUE
FALSE && !
10 TRUE Print ( || ( TRUE
FALSE && ! TRUE
11 || Push ( || ( || TRUE
FALSE && ! TRUE
12 FALSE Print ( || ( || 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 Print 20
2 8 Print 20 8
3 4 Print 20 8 4
4 / Pop 4 20 8
Pop 8 20
Push 8 / 4 20 2
5 2 Print 20 2 2
6 3 Print 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 Print FALSE
2 FALSE Print FALSE FALSE
3 TRUE Print FALSE FALSE
TRUE
4 TRUE Print 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 Print 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.



4 Comments

  1. rach

    January 6, 2008

    Post a Reply

    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.

  2. Tikna

    January 8, 2008

    Post a Reply

    What the _____ !

    why are you wasting your time in all this, at this time of the year you should be studying

  3. GQ

    January 10, 2008

    Post a Reply

    @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…

  4. Prakhar

    January 14, 2008

    Post a Reply

    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……

Leave a Reply to Tikna Cancel reply

Your email address will not be published. Required fields are marked *