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