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


NCERT Solutions for Class 12 Computer Science (C++) Chapter 9 – Stack – Free PDF download

NCERT Solutions for Class 12 Computer Science

Chapter NameStack
ChapterChapter 9
ClassClass 12
SubjectComputer Science (C++) NCERT Solutions
BoardCBSE
CategoriesCBSE NCERT Solutions


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
OPERATIONSTACK
2PUSH 22
13PUSH 132,13
+POP 13 and 2
Evaluate 2 + 13 = 15
PUSH 15
15
5PUSH 515,5
POP 5 & 15
EVALUATE 15-5 = 10
PUSH 10
10
6PUSH 610, 6
3PUSH 310, 6, 3
/POP 3 & 6
EVALUATE 6/3= 2
PUSH 2
10,2
5PUSH 510, 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

OPERATIONSTACK
100PUSH 100100
40PUSH 40100,40
8PUSH 8100,40,8
/POP 8
POP 40
EVALUATE 40/8 =5
PUSH 5
100,5
20PUSH 20100,5,20
10PUSH 10100, 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 ElementOperationStack
1TruePUSH TrueTrue
2FalsePUSH FalseFalse
3NOTCalculate NOT FalsePOP FalsePUSH TrueTrueTrue, True
4Andcalculate: 

True AND True

POP True POP TruePUSH TrueTrueTrue
5TruePUSH TrueTrue, True
6ORCalculate: True OR TruePOP TruePUSH TrueTrueTrue
7FalsePUSH FalseTrue, False
8ANDCalculate: True AND FalsePOP FalsePOP True PUSH FalseTrueFalse

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 ElementOperationStack
1FPUSH FF
2TPUSH TF,T
3NOTCalculate NOT TPOP TPUSH FFF,F
4ANDCalculate NOTPOP FPOP F 

PUSH F

FF
5FPUSH FF,F
6ORPOP FPOP F 

 

7TPUSH TF,T
8ANDPOP TPOP F 

PUSH F

FF

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:

SYMBOLSTACKOUTPUT
55
35,3
25,3,2
*PUSH 3,2Perform 3*2=6 

POP 6

55 

5,6

45,6,4
25,6,4,2
/PUSH 4,2Perform 4/2=2 

POP2

5,65,6 

5,6,2

PUSH 6,2Perform 6-2=4 

POP 4

55 

5,4

*PUSH 5,4perform 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 ScannedStack Status
FalseFalse
NOTTrue
TrueTrue, True
ANDTrue
TrueTrue, True
FalseTrue, True, False
ORTrue, True
ANDTrue

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

StackExpression
(( 

X

*

((( 

((

((*

—— 

X

X

3+ 

y

X-

3

+

z

X-

3

)

/

(

X

+

y

+

Z

)

)

((*((* + 

((* +

((* + *

((* + *

((* + * +

((* + * +

((* + * + *

((* + * + *

(

(/

(/(

(/(

(/(+

(/(+

</(+ +

(/(+ +

(/

x3x3 

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 ScannedStack Status
4545
 45 45,45
+ 90
 3290,32
2090,32,20
 1090,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)

ElementStack of OperatorPostfix 

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 StatusOutput
(( 

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

ElementStackExpression
A/ 

(

B

+

C

)

D

E

((/ 

(/C

(/c

(/c+

(/c+

(*

(*

(-

(-

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:

215912516401515
103901921802601
285209609360172

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+

ElementStackExpression

/

(

Q

R

)

*

S

+

T

)

((/ 

(/c

(/c

(/c-

(/c-

(/

(*

(*

(+

(+

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

ElementStackPostfix
(
(
XX
//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-*
)itXY/UVW-* +

OR

ElementStackPostfix
XX
//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.SymbolOperationStackResult
1470push(470)470
25push(5)470,5
34push(4)470,5,4
4/NP°P(4)470,5
0pop(5)470
perform(5∧4)
push(625)470,625
525push(25)470,625,25
6/pop(25)470,625
pop(625)470
perform(625/25)470
push(25)470,25
76push(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 StackPostfix
(
(
UU
**
VUV
)UV*
++
(
RUV*R
/+/
(
SUV*RS
+/-
TUV*RST
)UV*RST-
)UV*RST-/
)UV*RST-/+

OR

UU
 **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.