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.
4 replies on “Class 12 Comp Sci Stuff : Postfix Conversion”
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.
What the _____ !
why are you wasting your time in all this, at this time of the year you should be studying
@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…
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……