Made Easy2019

Question

The minimum size of stack required to evaluate given post fix expression is _____________

postfix :- 2 5 x 6 + 4 2 x -

 

MY ANSWER IS 8..

CAN ANYONE TELL ME WHERE I AM WRONG…??

Comments

operator and operand stack are different for evaluation?

Otherwise

16  4  2  *

this will be max size

It is size 3 or 4?

---

operator and operand stack are different for evaluation?

actually we didn't push the operators into the stack,

While reading the input ( postfix form ), when we encounter an operator, then we will perform pop operations ( number of pop's depend upon the operator ) on the operand stack.

Hence only one stack is used, that is used only for operands but not operators.

---

yes, we push only operands

and when get operator we just pop

thanks :)

Answer 1

Ans is 3.

3 is the minimum stack size required. This is how..

First you will push 2 ... Stack size becomes 1

Then you will push 5 ... Stack size becomes 2

On seeing x, you pop 2 numbers from stack and push back the result... Stack size becomes 1

Then push 6.. stack size becomes 2

Then on +, 2 pops and then 1 push.. stack size is 1 now

Then on on seeing 4,2 they are pushed onto stack.. stack size becomes 3

Then eventually as expression is further evaluated stack size dwindles down to 0.

So to evaluate expression, stack size should be atleast 3.

Comments

operator and operand stack different?

---

I am assuming that initially we are given an empty stack and a postfix expression already stored in some data structure, say array, over which we can iterate.