edited by
1,833 views
1 votes
1 votes
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
edited by

1 Answer

Best answer
4 votes
4 votes

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

 

selected by

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
2 answers
2
Shahid Rabbani asked Jan 11, 2015
1,277 views
For every push pop>3 units time required. Do continuously 4 push afterward 4 pop. Then what is the average life time of stack.
1 votes
1 votes
1 answer
4