Minimum number of register

Question

Consider the evaluation of following expression tree on a machine in which memory can be accessed only through load and store instructions. The variable p, q, r, s, t and u are initially  stored in memory. The binary operators used in the tree can be evaluated by the machine only when all operands are in register. The instruction produce result only in a register.

What is the minimum number of registers needed to evaluate the expression if, no intermediate results can be stored in memory?

Comments

its 3

---

I think 4

how 3??

Answer 1

I think 3 registers required only

Comments

Can you tell me what is the Expression represented by tree ?

---

Which sort of tree it is ? I mean the indegree of t is 2 what does it means please explain it brother

---

I think expression will be -

{((P×q)+t)+(t-u)×(r×s)}

t is used times here.

---

yes it can be done with 3 registers!

---

can the problem be done using sethi ullman algorithm??

---

@Bikram 

@Prateek Raghuvanshi

I think evolution of expression tree is from left to right ,top to bottom but here you have changed the order order of evolution and this is only possible in case of parallel processing of all the node .

 

so what i want to ask is that  evolution of expression tree is from left to right ,top to bottom ,is this assumption right ??

if order of evolution is fixed then ans is 4 otherwise answer is 3