The Polish notation of the expression

Question

The Polish notation of the expression a + b * c + d ( where "+" is left associative):

A/ + + a * b c d

B/ + a * bc + d

C/ + + * a b c d

D/ + * bc + ad

Can anyone explain why the answer is A please? What is the best way to solve this kind of problem though?

Thanks

Answer 1

I assume that * has priority over +, but it is easier to show that explicitly using parentheses:

$a + (b*c) + d$

Now, you know that + is left associative, which means that this is evaluated as follows:

$(a + (b*c)) + d$

Finally, to show where the two + operators end up, let's label them:

$(a +_1 (b*c)) +_2 d$

OK, now put it in prefix (Polish notation) step by step:

$(a +_1 (b*c)) +_2 d \Rightarrow +_2 (a +_1 (b*c)) \: d \Rightarrow +_2 +_1 a \: (b*c) \: d \Rightarrow +_2 +_1 a * b \: c \: d$

And so that's $+ + a * b \: c \: d$

Answer 2

Work it out from the last operator backwards:

$$\quad \underbrace{+ \quad \underbrace{+ \quad a \quad \underbrace{ * \quad b \quad c}_{\color{red}{b \,\cdot\, c}}}_{\color{red}{a \,+\,} b \,\cdot\, c} \quad d}_{(a\,+\,b \,\cdot\, c) \color{red}{\,+\, d}}$$