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

there is one  brace extra in option(iii) at end

---

It took a bit time for me to understand why (E) is the correct option.

Though * has higher precedence than + and -, but brackets always have the highest precedence.

In the given parse tree, (a-b) and (a+b) are evaluated first, then multiplied and added with 2 at last, and the same happening in option iii and iv.

---

@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

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