TIFR CSE 2012 | Part B | Question: 8

Question

Consider the parse tree

Assume that $*$ has higher precedence than $+$, $-$ and operators associate right to left (i.e $(a + b + c= (a + (b + c)))$. Consider

1. $2 + a - b$
2. $2 + a - b * a + b$
3. $(2 + ((a - b) * (a + b)))$
4. $2 + (a - b) * (a + b)$

The parse tree corresponds to

• A. Expression (i)
• B. Expression (ii)
• C. Expression (iv) only
• D. Expression (ii), (iii), and (iv)
• E. Expression (iii) and (iv) only

Comments

@srestha Ma'am

I don't know whether they expect "most appropriate" answer or not but I think there is no need of choice 3 if choice 4 is sufficient. as "*" has highest precedence then anyhow it wont perform "+" over "*" so no need of parentheses there. Please explain.

---

"*" has highest precedence then anyhow it wont perform "+" over "*"

that is true, that is why option iv is true

but iii also correct

if both are correct, we need to say both correct. We cannot eliminate one without any reason

---

There is an extra closing bracket in option iii ?

Answer 1

e is correct

Because as the precedence is right to left, expression evaluated in (ii) is $2+(a-((b*a)+b)),$ which is not a correct evaluation as the given parse tree.

Comments

Firstly b*a shud perform first becz * has Higher precedence in 2^nd part..However it doesn't affect the Final Answer..

---

Can you elloborate a bit ?

---

for option (ii)

2+a−(b∗a)+b // * has high precedency

now +,- have same precedency so we will apply right to left associativity

(2+(a−((b∗a)+b))) is the result of option B.

---

I agree with Rajesh. b*a will be evaluated first.

---

As given in the question that '*' has higher priority but in the parse tree shown '*' is defined at a level above  '-'. Though the parse tree corresponds to iii) and iv), isn't the priority given wrong here?

---

$\mathbf *$ should come first that isn't necessary if parenthesis are being used.

Answer 2

Although given answer is correct one can approach in another way if one wants more visualization to this problem

Write the "postfix" expression of given parse tree keeping in mind precedences order & associativity as per question we will get      { 2ab-ab+*+ }

Now write the postfix expressions of options 3 & 4 you will see same and for option 2 you will get different

 

(E) correct answer

Comments

Right approach but when we take infix of tree that match to (ii) option