TIFR CSE 2021 | Part B | Question: 3

Question

What is the prefix expression corresponding to the expression:

$\left ( \left ( 9+8 \right ) \ast 7+\left ( 6\ast \left ( 5+4 \right ) \right )\ast 3\right )+2?$

You may assume that $\ast$ has precedence over $+$?

• A. $\ast + +\: 987 \ast \ast \: 6 + + \:5432$
• B. $\ast + + +\: 987 \ast \ast \: 6 + \:5432$
• C. $+ \ast + +\: 987 \ast \ast \: 6 + \:5432$
• D. $+ + \ast +\: 987 \ast \ast \: 6 + \:5432$
• E. $+ \ast + \ast \: 987+ + \: 6 \ast \:5432$

Answer 1

Option (D) 

Given Infix Expression: ((9+8)∗7+(6∗(5+4))∗3)+2

We know that if an infix expression is a operator b, then the prefix expression will be operator a b.

Start converting to prefix

Solve the innermost brackets first.

((+98)*7+(6*(+54)*3)+2

Now, group the following and apply prefix operation.

((+98)*7+(6*(+54)*3)+2

We get

((*+987)+(*6+54)*3)+2

Now, group the following and apply prefix operation.

((*+987)+(*6+54)*3)+2

((*+987)+(**6+543)+2

Now, group the following and apply prefix operation.

((*+987)+(**6+543)+2

(+*+987**6+543)+2

Now, group the following and apply prefix operation.

(+*+987**6+543)+2

++*+987**6+5432 

Ans. Option (D)

Answer 2

In the given infix expression $3$ types of the operator are used:

1 Parenthesis $()$ operator has the highest precedence over remaining and associativity is left to right.

2  $*$ has the highest precedence over the $+$ operator given both have associativity is left to right.

So the order of precedence in descending order: $()>*>+$

Infix-to-prefix conversation steps are as follows:

$((9+8)∗7+(6∗(5+4))∗3)+2$

$\implies (+98 * 7 +(6*(5+4))*3)+2$

$\implies  ((+98) * 7+ (6* (+54))*3)+2$

$\implies ((+98)*7 +(*6+54)*3)+2$

$\implies (*+987)+ (*6+54)*3+2$

$\implies (*+987)+ (**6+543)+2$

$\implies (+*+987**6+543)+2$

$\implies ++*+987**6+5432$

Option $(D)$ is correct.

Answer 3

Option $(D)$

Steps to convert Infix to Prefix:

$1.$ Reverse the Infix expression, replace ‘(’ with ‘)’ and vice-versa.

$2.$ Convert into Postfix expression.

$3.$ Reverse the postfix expression.

 

Reversed expression: $2+(3*((4+5)*6))+7*(8+9))$

 

Check here https://gateoverflow.in/2633/gate1995-2-21 to see how to convert infix to postfix expression.

 

Postfix expression using operator stack: $2345+6**789+*++$

Reverse the above postfix expression to get the prefix expression: $++*+987**6+5432$