The Gateway to Computer Science Excellence
0 votes
234 views
A postfix expression P is given with n binary operators. To evaluate the operator using stack, how many PUSH and POP operations are needed?

   A) PUSH:n, POP:n                                                               B)PUSH:2n, POP:2n+1

      
   C)PUSH:2n+1, POP:2n                                                      D)PUSH:n, POP:2n
in DS by Active (1.8k points)
edited by | 234 views
0
Is it C?
0
yes the ans is c can you please explain it.
0
take a example you can realize it.... then you think in general case why this relation holds good

1 Answer

+3 votes
Best answer

For convenience I am assuming the postfix expression like : ABCD... op1 op2 op3 ...

i.e. all the operators come after all the operands..

[For eg if the infix exp is 2^6^5= (2^(6^5)) [as ^ is right associative] then the postfix is: 2^(65^) -> 265^^ ]

If there are n binary operators then they has to be exactly n+1 operands.

__+__-__%__^__*__  this is just for showing that for 5 operators we should have 6 operands.

 

Now the postfix expression is : a1a2a3......an+1 op1op2op3....opn

Where a denotes operands and op denotes operators.

Step 1:

Push all the (n+1) operands... --> (n+1) pushes

Stack configuration[bottom to top] : a1a2a3......an+1

Input symbols left   : op1op2op3....opn

Step 2:  For op1 ,

pop an+1 and an --> 2 pops

push (an op1 an+1)  --> 1 push

I will denote the top of stack as T.

Now stack has (n+1) - 2 + 1 = n elements [ (n+1) elements - 2 pops + 1push ]

Stack configuration : a1a2a3......an-2T

Input symbols left : op2op3....opn

Step 3: For op2,

pop T and an-2 --> 2 pops

push (an-2 op2 T)  --> 1 push

Now stack has (n) - 2 + 1 = n-1 elements [ (n) elements - 2 pops + 1push ]

Stack configuration : a1a2a3......an-3T

Input symbols left : op3....opn

 

Now observe that for each operator, we are performing 2 pops and 1 push.

Suppose we are done with (n-1) operators then how many

pushes are done in total till now : n+1+ (n-1)*1 = 2n [inital n+1 pushes for n+1 operands]

pops : (n-1)*2 = 2n-2

Stack configuration : a1T

Input symbols left :   opn

For opn,

pop a1 and T --> 2 pops

push a1 opn T --> 1 push

Stack configuration : T (the final result)

Input symbol: $

Total pushes : 2n+1

Total pops: 2n-2+2 = 2n

 

by Boss (23.5k points)
selected by
+1
This was a generalization..for exams we shouldn't waste time doing this..Like Shaik said take an example and solve..
+1
thanx @MiNiPanda sir
+1

@Shubham Aggarwal

but note that all operators are binary operators in the question

0

Very elaborate answer. Thank you @MiNiPanda.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,388 answers
198,575 comments
105,411 users