Code – Page 3

Class 12 Comp Sci Stuff : Postfix Conversion

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.

(Circular) Queues : Implementation Using Array

/* Copyright (C) 2007 Ankur Banerjee. This program is free software: you can redistribute it and / or modify it under the terms of the GNU General Public License as published by the Free Software Foundation version 3 of the License. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. For a copy of the GNU General Public License see http://www.gnu.org/licenses/gpl.html /

/ Array implementation of a Circular Queue /

#include <iostream.h>
#include <conio.h>
#include <process.h>

void main()
{
clrscr();
const int max = 5;
int ch, n, front = -1, rear = -1, q[max], i;
char choice;
do
{
clrscr();
cout<<endl<<“Program Menu”
<<endl<<“1. Insert new element”
<<endl<<“2. Delete an element”
<<endl<<“3. Show list”
<<endl<<“4. Exit”
<<endl<<“Enter your choice: “;
cin>>ch;
switch(ch)
{
case 1 : clrscr();
if (front == (rear + 1) % max)
cout<<endl<<“Queue overflow! Insertion not possible!”;
else if (front == -1 && rear == -1)
{
front = 0;
rear = 0;
cout<<endl<<“Enter number to be inserted: “;
cin>>n;
q[front] = n;
}
else
{
rear = (rear + 1) % max;
cout<<endl<<“Enter number to be inserted: “;
cin>>n;
q[rear] = n;
}
break;
case 2 : clrscr();
if (front == -1 && rear == -1)
cout<<endl<<“Queue does not exist!”;
else if (rear == 0 && front == 0)
{
n = q[front];
rear = -1;
front = -1;
cout<<endl<<“Deleted data item: “
<<n<<endl;
}
else
{
n = q[front];
front = (front + 1) % max;
cout<<endl<<“Deleted data item: “
<<n<<endl;
}
break;
case 3 : clrscr();
if (front == -1 && rear == -1)
cout<<endl<<“Queue does not exist!”;
else if(front == 0 && rear == max – 1)
{
cout<<“\nDisplaying items:\n”;
for (i = front; i <= rear; i++)
cout<<q[i]<<” “;
cout<<endl;
}
else
{
cout<<“\nDisplaying items:\n”;
for(i=front; i!=rear; i=(i+1)%max)
cout<<q[i]<<” “;
cout<<q[rear]<<endl;
}
break;
case 4 : cout<<endl<<“Exiting program”<<endl;
exit(0);
default : cout<<endl<<“You entered an invalid choice!”;
}
cout<<endl<<“Do you wish to continue? (y/n): “;
cin>>choice;
} while (choice == ‘Y’ || choice == ‘y’);
}

/ Output */

Program Menu
1. Insert new element
2. Delete an element
3. Show list
4. Exit
Enter your choice: 1

Enter number to be inserted: 41