1. How did you decide the priority of + is greater than -. ?

The Gateway to Computer Science Excellence

+19 votes

Consider the following grammar (the start symbol is $E$) for generating expressions.

- $E \rightarrow T - E \mid T + E \mid T$
- $T \rightarrow T * F \mid F$
- $F \rightarrow 0 \mid1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9$

With respect to this grammar, which of the following trees is the valid evaluation tree for the expression $2*3*4 - 5*6+7$?

+19 votes

Best answer

0

+ is right associate ( ie right most + will be solve among all +) , - is also right associative ( ie right most - will be solve among all -) , but how to decide associativity between + and - ??

+2

@tsvkp1 As, both + and - are generated by same LHS so, both have the same precedence, Now the question is which one to evaluate first, So, When Precedence fails we go for associativity of the operator as + and - are right associative so the operator which is in Rightmost (+) will be evaluated first hence + will be evaluated first among + and -.

I hope now it is clear.

+3 votes

**#TheQuickApproach**

Here we know

* has high priority (Left to Right Associativity)+,- (Right to Left associativity)

Now if we evaluate the given expression using above data then it will give us

2∗3∗4−5∗6+7=-13

Now due to * has high priority with Left to right associativity** 2*3 should ****done first.**

which is done by Option B and D only. so except this 2 remaining options are eliminated.

Now Option B only gives result -13 and D gives 1 as result of Expression tree evaluation.

Henceis Ans.Option B

0 votes

$*$ has the highest precedence and is left associative. So, $((2*3)*4)...$ is done first.

Options A, C and E are eliminated.

After that, $5*6$ should be done.

B and D comply to that.

Now, $+$ and $-$ have equal priority, so treat them as same symbol: $((2∗3)∗4)<symbol>(5∗6)<symbol>7$

And they both are right associative.

So, treat the right symbol first.

=> Do addition first, then subtraction.

Hence, Option B is correct, and D is incorrect.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,292 answers

198,224 comments

104,909 users