GATE CSE 1997 | Question: 4.9

Question

The expression $( a * b) * c \; op \dots$

where ‘op’ is one of ‘$+$’, ‘$*$’ and ‘$\uparrow$’ (exponentiation) can be evaluated on a CPU with single register without  storing the value of ($a * b$) if

• A. $\text{‘op’}$ is ‘$+$’ or ‘$*$’

• B. $\text{‘op’}$ is ‘$\uparrow$’ or ‘$*$’

• C. $\text{‘op’}$ is ‘$\uparrow$’ or ‘$+$’

• D. not possible to evaluate without storing

Comments

I fail to understand the answer provided below.

Using parenthesis around $(a * b)$ compels us to evaluate this expression first, which will require one register to store the result of the evaluation, irrespective of the operation $op$.

Shouldn't the answer be option $D$? What am I missing?

---

 

+11votes

answered Nov 3, 2017 by Shatadru RC (257 points)

Let say, the expression is one of the below:

(a*b)*c+d

(a*b)*c*d

(a*b)*c^d

In any case, brackets has the highest priority always. So I have to compute brackets first. Now, for + and *, I can do the rest of the operation and save results in the same register. But for exponentiation, I have to store the result of a*b, then do the computation of c^d, then multiply these two results.

So option A is correct

Answer 1

Correct Option: A

$\uparrow$ has higer precedence than $\{*,+,-,/ \}$

So, if op $ = \uparrow$ implies, we need to evaluate the right hand side of $\uparrow$ first and then do the lhs part, which would definitely require us to store the value of lhs

but if its a '$+$' or '$*$' , we don't need to store the values evaluated, and on the go can do the operation directly on one register.

Comments

why will we evaluate RHS of ↑ first, coz in C language, either side of a binary operator can be evaluated first, it is undefined!

---

considering one operand can be in memory, right??

Answer 2

Let say, the expression is one of the below:

(a*b)*c+d

(a*b)*c*d

(a*b)*c^d

In any case, brackets has the highest priority always. So I have to compute brackets first. Now, for + and *, I can do the rest of the operation and save results in the same register. But for exponentiation, I have to store the result of a*b, then do the computation of c^d, then multiply these two results.

So option A is correct.

Comments

considering one operand can be in memory, right??

---

It is given single register a*b will be there, no need of considering one operand in memory

---

Here's how you can perform the calculations for each expression using a single register (R1) for the cases where it's possible:

For expression 1 (a * b) * c + d:

1. Load R1, a
2. Multiply R1, b (R1 = a * b)
3. Multiply R1, c (R1 = (a * b) * c)
4. Add R1, d (R1 = (a * b) * c + d)

For expression 2 (a * b) * c * d:

1. Load R1, a
2. Multiply R1, b (R1 = a * b)
3. Multiply R1, c (R1 = (a * b) * c)
4. Multiply R1, d (R1 = (a * b) * c * d)