Dark Mode

4 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 : 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**

1