Expressions: They are calculations involving operators and operands.
example: A+B%C*D++.
Infix Expressions: these are basic expressions containing 1 operator between 2 operands.
example: A-B
(A+B)%(C*D).
Postfix Expressions: these expressions are formed by placing the operator after both operands.
example: 1) AB+
2) (AB+)(CD*)%.
in example 1 you can clearly see that there is addition between A and B, but "+" is placed after both the operands, thus making it a postfix expression.
in example 2 there are three calculations:
1) A+B, written as AB+
2) C*D, written as CD*
3) 1)%2), written as (AB+)(CD*)%
thus making it a prefix expression.
Prefix Expressions: these expressions are formed by placing the operator before both the operands.
example: +AB
in the given example you can see that there is an addition between A and B, but "+" is placed before both the operands, thus making it a prefix expression.
Infix to Postfix/ Prefix Conversion:
Before converting an Infix expression to Post/ Prefix expression we should be aware of 2 things:
1) Placement of Brackets:
Before converting any infix expression to pre/ postfix expression, every individual calculation should be placed in brackets according to its operator precedence.
2) Operator precedence:
This is related to the execution priority of operators. Following is the operator precedence while converting an expression:
The above table is showing the operator precedence from high to low. Operators in same cell have same priority and if they occurs consecutively then they must be executed from left to right order as there occurrence in the expression.
Infix to Postfix:
It has 2 steps:
a) Place brackets correctly
b) Execute all brackets one by one from innermost to outer one.
let us understand the same with an example:
Infix Expression : A + B * C / (E - F)
Postfix Conversion: A + (B * C) / (E - F) : place B*C in bracket as * & / have same priority, but * occurs to left
A + ((B * C) / (E - F)) : place operands with / in bracket
now execute:
A + ((B * C) / (E - F))
= A + ((BC*) / (EF-)) : place * after B&C, also - after E&F
= A + (BC * EF- /) : now place / between both operands (BC*) and (EF-)
= ABC * EF- /+ : finally place + after both operands (A) and (BC * EF- /)
Infix to Prefix:
It also has 2 steps similar to previous conversion.
so, let us understand the same with an example:
Infix Expression : A + B * C / (E - F)
Prefix Conversion: A + (B * C) / (E - F) : place B*C in bracket as * & / have same priority, but * occurs to left
A + ((B * C) / (E - F)) : place operands with / in bracket
now execute:
A + ((B * C) / (E - F))
= A + ((*BC) / (-EF)) : place * before B&C, also - before E&F
= A + (/ * BC - EF) : now place / between both operands (*BC) and (-EF)
= +A / * BC - EF : finally place + before both operands (A) and (/ * BC - EF)
Practice Question:
Convert the following infix expressions to postfix expression
1) A+B*C%D/E-F/(G+H)
Solu: first place the brackets,
let us see in detail how brackets are placed,
= A+B*C%D/E-F/(G+H)
since *, /, % have same priority so we will approach left to right rule, here * is at leftmost position so it will be enclosed first,
= A+(B*C)%D/E-F/(G+H)
now % operation will be enclosed,
= A+((B*C)%D)/E-F/(G+H)
now both / operations
= A+(((B*C)%D)/E)-(F/(G+H))
now we have + & - operations with same priority, but + is at left position so it will be enclosed first.
= (A+(((B*C)%D)/E))-(F/(G+H))
now, solve all brackets one by one from innermost to outer one.
= (A+(((BC*)%D)/E))-(F/(GH+))
= (A+((BC*D%)/E))-(FGH+/)
= (A+(BC*D%E/))-(FGH+/)
= (ABC*D%E/+)-(FGH+/)
finally, execute last operation( subtraction)
= ABC*D%E/+FGH+/-
No comments:
Post a Comment