Sunday, September 14, 2008

Infix, Prefix and Postfix

An operator is a function that specify specific actions on objects. Those objects which acts as an input to the operator is called an operand. For eg., in 3+5 , the symbol "+" is a addition function (operator) which operates on the operands "3" and "5" to produce the result 8. Depending on where we place this operator and the operands, we have three different notations.

Infix: This is the common notation that we use in mathematics. Here the operators are put in between the two operands as in 3+5. Infix operations either require parenthesis or order of precedence to correctly evaluate an expression.

Prefix: Also called Polish notation due to the Polish logician Jan Ɓukasiewicz, who invented this notation. In this, the operators are put before the operands. Eg., +AB , where + is the operator. A,B are operands which has some value. It is mainly developed to avoid parenthesis in expressions.

For eg., let us take 2 + 6 / 8
Here we can use a bracket around 3+5 or we can give higher priority to division and evaluate the expression as (2+6)/8 = 1 or 2+6/8 = 2+0.75 = 2.75
So if we want the correct results we need to use brackets or precedence rule. The same expression, in prefix notation, can be written as / + 2 6 8
= / + 2 6 8
= / 8 8 (Note: / A B means "divide A by B" and not "divide B by A")
= 1
Here / operates on "the result of + 3 5" and 8. The result of + 3 5 is 8. This eliminates the ambiguity on what to evaluate first in the expression. If we note here, in prefix notation, the number of operators will always be one less than the number of operands. In our case, 2 operators and 3 operands.

Postfix: In postfix notation, also called reverse polish notation (RPN), we place the operators after the operands. This notation was proposed by F. L. Bauer and E. W. Dijkstra to reduce computer memory access and utilize the stack to evaluate expressions. eg., 5 3 -
Note: 5 3 - equals 5 - 3 = 2 and not 3 - 5 = -2
Thus - 5 3 in prefix is the same as 5 3 - in postfix

These prefix and postfix operations are often used in computer languages and in calculators for ease of calculation in the background. Since we are much familiar with the infix notation, we generally have a user interface which is in infix notation.

Let us take the discriminant of quadratic equations, B2-4AC
Infix : B^2-4*A*C
Prefix : -^B2**4AC
Postfix: B2^4A*C*-