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 : a_{1}a_{2}a_{3......}a_{n+1 }op_{1}op_{2}op_{3}....op_{n}
Where a denotes operands and op denotes operators.
Step 1:
Push all the (n+1) operands... --> (n+1) pushes
Stack configuration[bottom to top] : a_{1}a_{2}a_{3......}a_{n+1}
Input symbols left : op_{1}op_{2}op_{3}....op_{n}
Step 2: For op_{1} ,
pop a_{n+1} and a_{n }--> 2 pops
push (a_{n} op1 a_{n+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 : a_{1}a_{2}a_{3......}a_{n-2}T
Input symbols left : op_{2}op_{3}....op_{n}
Step 3: For op_{2},
pop T and a_{n-2 }--> 2 pops
push (a_{n-2} op_{2} T) --> 1 push
Now stack has (n) - 2 + 1 = n-1 elements [ (n) elements - 2 pops + 1push ]
Stack configuration : a_{1}a_{2}a_{3......}a_{n-3}T
Input symbols left : op_{3}....op_{n}
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 : a_{1}T
Input symbols left : op_{n}
For op_{n},
pop a_{1} and T --> 2 pops
push a_{1} op_{n} T --> 1 push
Stack configuration : T (the final result)
Input symbol: $
Total pushes : 2n+1
Total pops: 2n-2+2 = 2n