Polish Notation (Prefix Notation) in Data Structures

The name comes from the Polish mathematician/logician Lukasiewicz, who introduced it. There are 3 different ways to write an algebraic expressions:

• Infix form
• Prefix form
• Postfix form

Infix form

Is exactly the fully parenthesized notation we have just introduced. Let me remind you once again the Recursive definition

infix-expression := (infix-expression operand infix-expression) 
infix-expression := atom 

Examples

(3 * 7) 
((1 + 3) * 2) 
((1 + 3) * ( 2 - 3)) 

Main Feature:

the binary operator is between the two operands.

Question: what if we do not put all the parentheses? Then there are ambiguities on how to interpret an expression: is 1+2*3 the same as (1+2)*3 or the same as 1+(2*3)? The precedence of operators solves this problem.

Prefix form

Main Feature:

the operator preceeds the two operands.

Recursive definition of fully parenthesized version:

prefix-expression := (operand prefix-expression prefix-expression) 
prefix-expression := atom 

Recursive definition of classic version, without parentheses (we do not need them, because there is no longer any ambiguity on how to match the operands to the operators):

prefix-expression := operand prefix-expression prefix-expression 
prefix-expression := atom 

Examples

(* 3 7) or simply * 3 7 
(* ( + 1 3) 2) or simply * + 1 3 2 
( * ( + 1 3) ( - 2 3)) or simply * + 1 3 - 2 3 

Postfix form

Main Feature:

the operator is after the two operands. Recursive definition

postfix-expression := (operand postfix-expression postfix-expression) 
postfix-expression := atom 

Recursive definition of classic version, without parentheses (we do not need them, because there is no longer any ambiguity on how to match the operands to the operators):

postfix-expression := operand postfix-expression postfix-expression 
postfix-expression := atom 

Examples

(3 7 *) or simply 3 7 * 
((1 3 + ) 2 *) or simply 1 3 + 2 * 
((1 3 +) ( 2 3 -) * ) or simply 1 3 + 2 3 - * 

Associativity

Associativity describes the rule where operators with the same precedence appear in an expression. For example, in the expression a + b ? c, both + and – have the same precedence, then which part of the expression will be evaluated first, is determined by associativity of those operators. Here, both + and ? are left associative, so the expression will be evaluated as (a + b) ? c.

Precedence and associativity determine the order of evaluation of an expression. Following is an operator precedence and associativity table (highest to lowest) ?

The above table shows the default behavior of operators. At any point of time in expression evaluation, the order can be altered by using parenthesis. For example ?

In a + b*c, the expression part b*c will be evaluated first, with multiplication as precedence over addition. We here use parenthesis for a + b to be evaluated first, like (a + b)*c.

Why?

Why use PREFIX and POSTFIX notations when we have simple INFIX notation? INFIX notations are not as simple as they seem especially while evaluating them. To evaluate an infix expression we need to consider Operators’ Priority and Associative property

• E.g. expression 3+5*4 evaluate to 32 i.e. (3+5)*4 or to 23 i.e. 3+(5*4).

To solve this problem Precedence or Priority of the operators was defined. Operator precedence governs the evaluation order. An operator with higher precedence is applied before an operator with lower precedence.

The following table briefly tries to show the difference in all three notations ?