EXPRESSION FORMATS

TOPIC 01 – PREFIX NOTATION

 

 

LESSON NOTE

 

 

INFIX NOTATION

 

In mathematics, we are used to writing arithmetic expressions with the operator being placed between the operands.

 

For example, below, the + operator is placed between the operand 2 and the operand 4.

 

            2 + 4

 

This approach is called infix notation and is the only approach that most people have seen.  However, in computing, there is the prefix notation (and postfix notation) that does come up in some programming languages.

 

PREFIX NOTATION

 

The idea of prefix notation, also known as Polish notation, is quite simple.  The operator is placed before the operands.  So the 2 + 4 expression from above would be written like this instead:

 

            + 2 4

 

And the same applies for the – operator, the * operator (meaning multiplication) and the / operator (for division).

 

For example, here are the prefix expressions for 3 – 2, 5 * 4 and 7 / 2:

 

a)    – 3 2

b)    * 5 4

c)    / 7 2    

 

PREFIX NOTATION FOR BOOLEAN ALGEBRA

 

We can also apply prefix notation form for Boolean algebra expressions.  Here are a few examples:

 

INFIX NOTATION

PREFIX NOTATION

A AND B

AND A B

A XOR B

XOR A B

A AND B OR C

AND A OR B C

 

PREFIX NOTATION FOR MORE ADVANCED EXPRESSIONS

 

Let's consider expressions in infix notation and re-write them in prefix notation:

 

a)    3 + 6 – 2

Solution:
– + 3 6 2

 

b)    A + B / C

Solution:
+ / B C A

c)    (A + B) * C

Solution:
* + A B C

d)    A + B + C + (D – E)

Solution
+ + + A B C – D E

 

Notice that the prefix solutions don’t require brackets.

Later we will look at an approach to converting these expression from one form to another.

 

ARITY OF OPERATIONS

 

The arity of operations is the number of operands that are used for an operation.  For example, the + symbol is used between two numbers.  So it has an arity of 2.

 

Many (most) other operators in math also have an arity of 2 including minus, multiplication and division.  The square root operator is an example of an operator with an arity of 1.

 

It should be noted that infix notation does tend to encourage operations to have an arity of 2.  However, this is no longer a requirement of prefix.  We can add numbers 5, 18 and 22 using a single + sign like this:

 

            + 5 18 22


In the above situation, the + operator has an arity of 3.

 

PREFIX WAS INVENTED BECAUSE…

 

It was invented because all arithmetic expressions could be written without the need for brackets.  However, to do this, it is required that the arity of all operators be static.

 

In other words, when one encounters an operator, one must know how many operands that operator applies to.