NCERT Solutions for Class 12 Computer Science (C++) – Stack

NCERT Solutions for Class 12 Computer Science (C++) – Stack

Short Answer Type Questions-I[2 marks each]

Question 1.
Evaluate the following postfix expression. Show the status of stack after execution of each operation separately:
2,13, + , 5, -,6,3,/,5,*,<
Answer:

ITEM SCANNED	OPERATION	STACK
2	PUSH 2	2
13	PUSH 13	2,13
+	POP 13 and 2 Evaluate 2 + 13 = 15 PUSH 15	15
5	PUSH 5	15,5
–	POP 5 & 15 EVALUATE 15-5 = 10 PUSH 10	10
6	PUSH 6	10, 6
3	PUSH 3	10, 6, 3
/	POP 3 & 6 EVALUATE 6/3= 2 PUSH 2	10,2
5	PUSH 5	10, 2, 5
*	POP 5 & 2 EVALUATE 2*5 = 10 PUSH 10	10, 10
<	POP 10 & 10 EVALUATE 10<10 = FALSE PUSH FALSE	FALSE

RESULT = FALSE

Question 2.
Evaluate the following postfix expression : (show status of Stack after each operation)
100,40,8,/,20,10,-,+,*
Answer:

ITEM SCANNED	OPERATION	STACK
100	PUSH 100	100
40	PUSH 40	100,40
8	PUSH 8	100,40,8
/	POP 8 POP 40 EVALUATE 40/8 =5 PUSH 5	100,5
20	PUSH 20	100,5,20
10	PUSH 10	100, 5, 20, 10
	POP 10 POP 20 EVALUATE 20-10 =10 PUSH 10	100,5,10
+	POP 10 POP 5 EVALUATE 10 + 5= 15 PUSH 15	100,15
*	POP 15 POP 100 EVALUATE 100 * 15 = 1500 PUSH 1500	1500

Question 3.
Evaluate the following postfix expression. Show the status of stack after execution of each operation separately:
T, F, NOT, AND, T, OR, F, AND
Answer:

S.No.	Scanned Element	Operation	Stack
1	True	PUSH True	True
2	False	PUSH False	False
3	NOT Calculate NOT False	POP False PUSH True	True True, True
4	And calculate: True AND True	POP True POP True PUSH True	True True
5	True	PUSH True	True, True
6	OR Calculate: True OR True	POP True PUSH True	True True
7	False	PUSH False	True, False
8	AND Calculate: True AND False	POP False POP True PUSH False	True False

Thus the stack will have False Value

Question 4.
Evaluate the following postfix expression. Show the status of stack after execution of each operation separately:
F, T, NOT, AND, F, OR, T, AND
Answer:

S.No.	Scanned Element	Operation	Stack
1	F	PUSH F	F
2	T	PUSH T	F,T
3	NOT Calculate NOT T	POP T PUSH F	F F,F
4	AND Calculate NOT	POP F POP F PUSH F	F F
5	F	PUSH F	F,F
6	OR	POP F POP F
7	T	PUSH T	F,T
8	AND	POP T POP F PUSH F	F F

Thus the stack will have False Value

Question 5.
Evaluate the following postfix expression using a stack and show the contents of stack after execution of each operation:
5,3,2, *, 4,2, /, -,*
Answer:

SYMBOL	STACK	OUTPUT
5		5
3		5,3
2		5,3,2
*	PUSH 3,2 Perform 3*2=6 POP 6	5 5 5,6
4		5,6,4
2		5,6,4,2
/	PUSH 4,2 Perform 4/2=2 POP2	5,6 5,6 5,6,2
–	PUSH 6,2 Perform 6-2=4 POP 4	5 5 5,4
*	PUSH 5,4 perform 5*4=20. POP 20	20

Result=20

Question 6.
Evaluate the following POSTFIX notation. Show status of Stack after every step of evaluation (i.e. after each operation)
False NOT, True, AND, True, False, OR, AND
Answer:

Element Scanned	Stack Status
False	False
NOT	True
True	True, True
AND	True
True	True, True
False	True, True, False
OR	True, True
AND	True

Final Answer: True

Question 7.
Top is a pointer variable pointing to the top element of a stack, with each node having the following structure declaration:
struct Stack {int Data, Stack * Next};
Considering the above explanation, what will the following code do ?
int count = 0, Sum = 0;

Stack * Temp = Top;
 while (Temp - > Next! = NULL)
 { count + +;
 Sum + = Temp - > Data;
 Temp Temp - > Next;
 }
 count < < Sum / count;

Answer:
It will calculate the average of stack values.

Question 8.
Convert the expression ((x * 3 + y * 3 + z * 3) / (x + y + z)) into postfix expression. Show the content of the stack during the conversion.
Answer:
Given expression : ((x * 3 + y * 3 + z * 3) / (x + y + z))
((x * 3 + y * 3 + z * 3) / (x + y + z))

Symbol Scanned	Stack	Expression
( ( X *	( (( (( ((*	— — X X
3 + y X- 3 + z X- 3 ) / ( X + y + Z ) )	((* ((* + ((* + ((* + * ((* + * ((* + * + ((* + * + ((* + * + * ((* + * + * ( (/ (/( (/( (/(+ (/(+ </(+ + (/(+ + (/	x3 x3 x3y x3y x3y3 x3y3 x3y3z x3y3z x3y3z3 x3y3z3 * + * + * x3y3z3 * + * + * x3y3z3* + * + * x3y3z3 * + * + * x x3y3z3 * + * + * x       • x3y3z3 * + * + * x y x3y3z3 * + * + * x y x3y3z3 * + * + * xyz x3y3z3 * + * + * xyz + + x3y3z3 * + * + * xyz + +/

\Postfix expression is: x3y3z3 * + * + * xyz + +/

Question 9.
Evaluate the following POSTFIX expression, show the status of Stack after execution of each operation separaterly:
45,45,+,32,20,10,/,-,*
Answer:

Element Scanned	Stack Status
45	45
45	45,45
+	90
32	90,32
20	90,32,20
10	90,32,20,10
/	90,32,2
–	90,30
*	2700

Hence the final result is 2700

Question 10.
Convert the following Infix expression to its equivalent Postfix expression, showing the stack contents for each step of conversion.
P/Q+(R-T)*U
Answer:
P/Q+(R-T)*U = (P/Q+(R-T)*U)

Element	Stack of Operator	Postfix Expression
(	(
P	(	P
/	(/	P
Q	</	PQ
+	(/+	PQ
(	(/+(	PQ
R	(/+(	PQR
–	(/+(-	PQR
T	(/+c-	PQRT
)	(/+	PQRT-
*	(*	PQRT-+/
U	)*	PQRT-+/U
)		PQRT-+/U*

 

Short Answer Type Questions-II[3 marks each]

 

Question 1.
Write the definition of a member function Pop ()
in C++, to delete a book from a dynamic stack of TEXTBOOKS considering the following code is already included in the program.

Struct TEXTBOOKS
 {
 Char ISBN [20]; Char TITLE [80]; TEXTBOOKS *Link;
 };
 class STACK
 {
 TEXTBOOKS *Top; 

public :
 STACK () {Top = NULL;} 

void Push ();
 . void pop );
 -STACK ();
 };

Answer:

void STACK : : POP ()
 {
 if (Top ! = NULL)
{
 TEXTBOOKS *Temp;
 Temp=Top;
cout<< TOP- >ISBN<<Top-
 TITLE<<"delected"<<endl;
 Top=Top-Link;
 delete Temp;
 }
 else
 cout<<"Stack Empty"<<endl;
 }

OR
Any other correct equivalent function definition

Question 2.
Write the defintion of a member function PUSH () in C+ +, to add a new book in a dynamic stack of BOOKS considering the following code is already included in the program :

struct BOOKS
 {
 Char ISBN [20]; TITLE[80];
 BOOKS *Link;
 };
 class STACK
 {
 BOOKS *Top;
 public :
 STACK () {Top = NULL;}
 void PUSH ();
 Void POP ();
 -STACK ();
 };

Answer:

void STACK :: PUSH ()
 {
 BOOKS *Temp;
 Temp=New BOOKS;
 gets (Temp->ISBN);
 gets (Temp->TITLE);
 Temp->Link =Top;
 Top=Temp;
 }

OR
Any other correct equivalent function definition

Question 3.
Convert the expression (A-5)*6+(10/B)/2 to corresponding postfix expression. Also show the status of operator stack after each step.
Answer:
((A-5)*6+(10/B)/2)

Scanned Elements	Stack Status	Output
( ( A – 5 ) * 6 + ( 10 / B ) / 2 )	( (( (( ((- ((- ( (* (* (+ (+( (+( (+(/ (+(/ (+ (+/ (+/	A A A, 5 A, 5,- A, 5,- A, 5, -, 6 A, 5, -, 6* A, 5,-, 6,* A, 5,     6, *, 10 A, 5, -, 6, *, 10 A, 5,     6, *, 10, B A, 5,-, 6,10, B/ A, 5,    6,10, B J A, 5,-, 6, *, 10, B/,2 A,5,-,6,M0,By,2y,+

The correspondence postfix expression is A, 5, 6, 10, B, /,2, /,+

Long Answer Type Questions[4 marks each]

Question 1.
Convert the following Infix expression to its equivalent Postfix expression, showing the stack contents for each step of conversion.
A/(B+C)*D-E
Answer:
A/ (B + C) *D-E

Element	Stack	Expression
A / ( B + C ) ★ D – E	( (/ (/C (/c (/c+ (/c+ (* (* (- (-	A A A AB AB ABC ABC+ ABC+/ ABC+/D ABC+/D* ABC+/D*E-

Question 2.
Write definition for a function DISPMID (int A[][5], int R, int C) in C+ + to display the elements of middle row
and middle column from a two dimensional array A having R number of rows and C number of columns.
For example, if the content of array is as follows:

215	912	516	401	515
103	901	921	802	601
285	209	609	360	172

The function should display the following as output:
103 901 921 802
601 516 921 609
Answer:

void DISPMID (int A[] [5] , int R, int C)
 {
 int mid = (R+C)/2;
 for (int i=0; i<c; i++)
 {
 Cout << A[mid] [i]<<"";
 } cout<<endl;
 for (int i=0; i<R; i++)
 cout << A[i][mid]<<"";
 }

Question 3.
Convert the following Infix expression to its equivalent Postfix expression, showing the stack contents for each step of conversion.
P/(Q-R)*S+T
Answer:
P/(Q-R)*S+T
BODMAS : PQR-/S*T+
PQR-/S*T+

Element	Stack	Expression
P / ( Q – R ) * S + T )	( (/ (/c (/c (/c- (/c- (/ (* (* (+ (+	P P P PQ PQ PQR PQR- PQR-/ PQR-/S PQR-/S* PQR-/S*T PQR-/S*T+

Question 4.
Convert the following infix expression to its equivalent postfix expression, showing the stack contents for each step of conversion:
X/Y+U*(V-W)
Answer:
X / Y + U* (V – W) = ((X / Y) + (U * (V – W)))

Element	Stack	Postfix
(
(
X		X
/	/	X
Y	/	XY
)		XY/
+	+	XY/
(	+	XY/
U	+	XY/U
*	+ *	XY/U
(	+ *	XY/U
V	+ *	XY/UV
–	+ *-	XY/UV
W	+ *-	XY/UVW
)	+ *	XY/UVW-
)	+	XY/UVW-*
)	it	XY/UVW-* +

OR

Element	Stack	Postfix
X		X
/	/	X
Y	/	XY
+	+	XY/
U	+	XY/U
*	+ *	XY/U
(	+ *(	XY/U
V	+ *(	XY/UV
–	+ *(-	XY/UV
w	+ ‘(-	XY/UVW
)	+ *	XY/UVW-
		XY/UW-*
		XY/UVW-* +

OR

Any other method or converting the given Infix expression to its equivalent Postfix expression showing stack contents

Question 5.
Evaluate the following postfix expression using stack and show the contents after excecution of each.
Answer:
Operations : 470,5,4,∧,25,/,6,*

S. No.	Symbol	Operation	Stack	Result
1	470	push(470)	470
2	5	push(5)	470,5
3	4	push(4)	470,5,4
4	/N	P°P(4)	470,5
0		pop(5)	470
		perform(5∧4)
		push(625)	470,625
5	25	push(25)	470,625,25
6	/	pop(25)	470,625
		pop(625)	470
		perform(625/25)	470
		push(25)	470,25
7	6	push(6)	470,25,6
8	*	pop(6)	470,25
		pop(25)	470
		perform(25*6)	470

Question 6.
Write member functions to perform POP and PUSH operations in a dynamically allocated stack containing the objects of the following structure:

struct Game
 { char Gamename[30];
 int numofplayer;
 Game *next; } ;

Answer:

struct Game
 {
 char Gamename[3 0] ;
 int numofplayer;
 Game *next;
 };
 class Stack { Game *Top;
 public :
 Stack ()
 {
 Top = NULL;
 }
 void Push();
 void Pop();
 void display();
 -Stack();
 } ;
 void Stack::Push()
 {
 Game *temp = new Game;
 cout<<"Enter Data : "; gets(temp->Gamename);
 cin>>temp->numofplayer;
 temp->next =Top;
 Top = temp;
 }
 void Stack:: Pop()
 {
 if ( Top != NULL)
 {
 Game *temp = Top;
 cout<Gamename<<" Deleted"; Top = Top->next;
 delete temp;
 }
 else
 cout<<"Stack is empty....";
 }

Question 7.
Write a function PUSHBOOK() in C++ to perform insert operation on Dynamic Stack, which contains Book_no and Book_Title. Consider the following definition of NODE, while writing your C+ + code,

struct NODE
{
int Book_No ;
char Book_Title [20];
NODE * Next;
};

Answer:

Void PUSHBOOK (NODE *TOP> int Book_No, char B Title [20])
 {
 NODE*temp;
 temp=new NODE;
 temp —> Book_No=Book_No;
 Strcpy (temp —> Book_Title, B Title) ;
 temp --> Next=NULL ;
 if (Top==NULL)
 Top=temp;
 else
 {
 temp —> Next=top;
 Top==temp;
 }
 }

Question 8.
Write a function POPBOOK( ) in C++ to perform delete operation from a Dynamic Stack, which contains Bno and Title. Consider the following definition of NODE, while writing your C++code.

struct NODE
{
int Bno;
char Title[20] ;
NODE * Link;
} ;

Answer:

node*PopBOOK(node*TOP int Bno, char B Title [20])
{
node*temp;
temp=new node;
temp —>Bno=Bno;
strcpy (temp —>Title, B Title);
temp ->link=NULL:
if (TOP==NULL)
Top=Temp;
else
{
temp —>link=Top;
TOP==temp;
}
}

Question 9.
Write the definition of a member function push() for a class Library in C++ to insert a book information in a dynamically allocated strack of books considering the following code is already written as a part of the program

struct book
{
int bookid;
char bookname[20];
book*next;
} ;
class Library
{
book*top;
public
Library()
{
top=NULL;
}
void push();
void pop();
void disp() ;
-Library();
};

Answer:

void Library: :push()
{
book*nptr;
nptr=new book;
cout<<"Enter values for bookid and bookname"; cin> >nptr->bookid;
gets(nptr->bookname);
nptr->next =NULL;
if (top==NULL)
top=nptr;
else
{
nptr->next=top,
top=nptr;
}
}

Question 10.
Convert the following Infix expression to its equivalent Postfix expression, showing the stack contents for each step of conversion:
U * V + R / (S-T)
Answer:
U*V + R/(S-T)

Element	Stack	Postfix
(
(
U		U
*	*
V		UV
)		UV*
+	+
(
R		UV*R
/	+/
(
S		UV*RS
–	+/-
T		UV*RST
)		UV*RST-
)		UV*RST-/
)		UV*RST-/+

OR

U		U
*	*	U
V	*	UV
+	+	UV*
R	+	UV*R
/	+/	UV*R
(	+/(	UV*R
S	+/(	UV*RS
–	+/(-	UV*RS
T	+/(-	UV*RST
)	+/	UV’RST-
	+	UV’RST-/
		UV*RST-/+

OR

Any other method for converting the given Infix expression to its equivalent Postfix expression showing stack contents.

NCERT SolutionsComputer scienceEnglishHindiHumanitiesCommerceScience