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))

2 comments:

Iranina child said...
This comment has been removed by the author.
Anonymous said...

hello
how you can describe the parse tree for infix to prefix grammar.

for example my input is : 9+2*3

can you draw this parse tree?
thanks