Exercise Postfix..Prefix..Infix

I) Infix to Prefix Notation Translation for Expressions
• Translation defined inductively as: Prefix(E) where E is an expression

1) If E is a variable or constant then Prefix(E)=E
2) If E is E1 op E2 then Prefix (E) = Prefix (E1 op E2) = op Prefix (E1) Prefix (E2)
3) If E is (E1) then Prefix(E1) = Prefix(E1)

Example:

Infix A*B+C/D to Prefix +*AB/CD

Prefix ((A*B)+(C/D))
+ prefix(A*B) prefix (C/D)
+* prefix (A) prefix (B) / prefix (C) prefix (D)
Ans: +*AB/CD

II a)Prefix to Infix

• Translation defined inductively as: Prefix(E) where E is an expression

1) If E is a variable or constant then Infix(E)=E
2) If E is E1 op E2 then Infix (E) = Infix (op E1 E2) = Infix (E1) op Infix (E2)
3) If E is (E1) then Infix(E1) = Infix(E1)

Example:
Infix( - ( / A B ) (* C D) )
= ( Infix ( / A B ) - Infix( * C D ) )
= ( ( Infix (A) * Infix (B) ) - ( ( Infix (C) / Infix (D) )
Ans: ( ( A / B ) - ( C * D ) )
II b). Postfix to Infix
1) If E is a variable then Infix(E) = E
2) If E is E1 E2 op then Infix(E) = Infix(E1 E2 op) = Infix (E1) op Infix (E2)
3) If E is (E1) then Infix(E) = Infix (E1)
Example:
Infix( ( A B + ) C + )
= ( Infix(A) + Infix(B) ) + Infix(C)
Ans: ( A + B ) + C


III) Postfix to Prefix Notation Translation for Expressions
• Translation defined inductively as: Prefix(E) where E is an expression

1) If E is a variable or constant then Prefix(E)=E
2) If E is E1 op E2 then Prefix (E) = Prefix (E1 E2 op) = op Prefix (E1) Prefix (E2)
3) If E is (E1) then Prefix(E1) = Prefix(E1)

Example:
a) From Postfix((AB*)(CD/)+)
Prefix ((AB*)(CD/)+)
= + Prefix((AB*)) Prefix((CD/))
= + Prefix(AB*) Prefix(CD/)
= + * Prefix (A) Prefix (B) / Prefix (C) Prefix (D)

Ans: + * AB / CD or (+(*AB)(/CD))