231 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
edited | 231 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

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

but note that all operators are binary operators in the question

0

Very elaborate answer. Thank you @MiNiPanda.