This article describes the Evaluation of Infix/Postfix; what is Infix, Postfix, and Prefix. How to perform conversion among them.
Table of Contents
Expression
An expression is the combination of operands and operators, resulting in equations to return the answer. E.g., A+B, 2+4, C*2, 6/2, etc.
Infix
Infix refers to the operator exits between the operands. It makes the expression in the form of A operator B., E.g., 2+3, (5+6)*5-9, A+B, where A and B are the operands and “+” is the operator.
Postfix
Postfix (Reverse Polish) refers to the operator that exits after the pair of operands. It makes the expression in the form of an <operand><operand> <operator>. E.g., AB+, (4+5)*78 = 4 5 + 78*.
Prefix
Prefix (also called Polish) refers to the existence of the operator always before the pair of operands. In other words, the operator always comes before the operator. It makes the expression in the form of an <operator> <operand><operand>. E.g., +AB, *CD, (4+5)*78 = *+4 5 7 8.
Why need for Postfix Expression?
The computer reads the equation from left to right or right to left.
Consider the following example –
A + B * C + D
The computer first scans the whole expression and later evaluates the expression according to the high precedence of the operator. In this expression, the computer first evaluates the expression B * C, then again scans the rest of the expression and adds the result to A, then scans the rest expression and finally adds the result to D.
It is clearly understood that the computer scans the expression operator to find the high precedence to solve the expression, and this action is repetitive according to the expression length, which makes the procedure time taking.
This repetitive procedure of scanning makes the evaluation procedure slow and inefficient. That’s why Postfix evaluation comes into play.
The above-given expression can be solved easily through Postfix using Stack.
Following rules for precedence and associativity:
- ()
- ^ associativity R-L
- / and * associativity L-R
- + and – associativity L-R
Let’s take some examples:
Infix | Postfix | Prefix |
A + B * C + D | ABC*+D+ | ++A*BCD |
4/5 | 45/ | /45 |
2+3*5 | 235*+ | +2*35 |
(6+2) * (5-1) | 62 + 51 – * | *+ 62 – 51 |
Infix to Postfix manual conversion rule:
- Parenthesize the Infix expression according to the operator’s high precedence value.
- Start solving the expression from left to right and move each operator to its right parentheses.
- Remove all parentheses.
Prefix manual conversion rule:
- Parenthesize the Infix expression according to the operator’s high precedence value.
- Start solving the expression from left to right and move each operator to its left parentheses.
- Remove all parentheses.
Note: Write the Infix expression in the parentheses if not already.
Example 1: Conversion of Infix equation to Postfix and Prefix.
Postfix
Expression: A + B * C + D
Step 1: ([A + B] * [C + D]) #write infix expression into parentheses as per precedence value.
Step 2: ([A B +] * [C D +]) #Move the operator to its right parentheses.
Step 3: AB + C D + * #Remove the brackets.
Prefix
Expression: A + B * C + D
Step 1: ([A + B] * [C + D]) #write infix expression into parentheses as per precedence value.
Step 2: ([+ A B] * [+ C D]) #Move the operator to its left parentheses.
Step 3: *+ AB + CD #Remove the brackets.
Example 2: Conversion of Infix equation to Postfix and Prefix.
Postfix
Expression: ( AX + [B * C] )
Step 1: (AX + [B * C]) #write infix expression into parentheses as per precedence value.
Step 2: (AX + [B C *]) #Move the operator to its right parentheses.
Step 3: AX B C *+ #Remove the brackets.
Prefix
Expression: ( AX + [B * C] )
Step 1: (AX + [B * C]) #write infix expression into parentheses as per precedence value.
Step 2: (+ AX [* B C]) #Move the operator to its left parentheses.
Step 3: + AX * B C #Remove the brackets.
Example 3: Conversion of Infix equation to Postfix and Prefix.
Postfix
Expression: ( [A + B] * [C + E] )
Step 1: ( [A + B] * [C + E] ) #write infix expression into parentheses as per precedence value.
Step 2: ([A B +] * [C E +]) #Move the operator to its right parentheses.
Step 3: A B + C E +* #Remove the brackets.
Prefix
Expression: ( [A + B] * [C + E] )
Step 1: ( [A + B] * [C + E] ) #write infix expression into parentheses as per precedence value.
Step 2: ( [+ A B] * [+ C E] ) #Move the operator to its left parentheses.
Step 3: *+ A B + C E #Remove the brackets.
Example 4: Conversion of Infix equation to Postfix and Prefix.
Postfix
Expression: ( [ AX + [B * CY] ] / [D - E] )
Step 1: ( [ AX + [B * CY] ] / [D - E] ) #write infix expression into parentheses as per precedence value.
Step 2: ( [ AX + [B CY *] ] / [D E – ] ) #Move the operator to its right parentheses.
Step 3: A X BCY * + D E – / #Remove the brackets.
Prefix
Expression: ( [ AX + [B * CY] ] / [D - E] )
Step 1: ( [ AX + [B * CY] ] / [D - E] ) #write infix expression into parentheses as per precedence value.
Step 2: ( [ + AX [* B CY] ] / [- D E] ) #Move the operator to its left parentheses.
Step 3: / + A X * BCY – D E #Remove the brackets.
Example 5: Conversion of Infix equation to Postfix and Prefix.
Postfix
Expression: ( AX * [ BX * [ [ [CY + AY ] + BY ] * CX ] ] )
#write infix expression into parentheses as per precedence value.
Step 1: ( AX * [ BX * [ [ [CY + AY ] + BY ] * CX ] ] )
#Move the operator to its right parentheses.
Step 2: ( AX * [ BX * [ [ [CY AY + ] BY +] CX *] ] )
#Remove the brackets.
Step 3: AX BX CY AY + BY + CX ***
Prefix
Expression: ( AX * [ BX * [ [ [CY + AY ] + BY ] * CX ] ] )
#write infix expression into parentheses as per precedence value.
Step 1: ( AX * [ BX * [ [ [CY + AY ] + BY ] * CX ] ] )
#Move the operator to its left parentheses.
Step 2: ( * AX[ * BX [ [ [ + CY AY] + BY] * CX ] ] )
#Remove the brackets.
Step 3: * AX * BX *++CY AY BY CX
Conclusion
Evaluating infix and postfix expressions is a fundamental task in programming and mathematics. While infix notation is the standard notation we are familiar with, postfix notation offers simplicity and ease of evaluation advantages. Converting infix expressions to postfix notation simplifies the evaluation process and eliminates ambiguity. Understanding these notations and their evaluation methods is valuable for anyone working with mathematical expressions and programming languages.
