Main Index Algebraic structures Algebraic operations
  Subject Index
comment on the page

Notation Used for Operations

The conventional notation for arithmetic and logic formulas expressions in which the expressions are written using parentheses placed according to the precedence rules is called the infix notation. In this form the operators are written between the operands they act on (that is in the infix-style form). In fully parenthesized infix notation the parentheses surrounding groups of operands and operators are used to indicate the intended order in which operations are to be performed. To reduce the number of parentheses certain precedence rules conventions are used to determine the order of operations.

Generally speaking the infix notation as it is used in  common arithmetic and logical expressions  is not as simple to parse by computer as the so-called prefix notation or postfix notation. However,  many programming languages use because of its familiarity.

In the 1920’s , Polish logician, mathematician, and philosopher Jan Łukasiewicz* (1878-1956)  [1],  [2], [3]  developed a formal logic system which allowed mathematical parentheses-free notation in which the operators are placed  before (the so called prefix notation) or after (the so called postfix notation) the operands. Prefix notation is also called Polish notation in the honor of Łukasiewicz and the postfix notation is now called reverse Polish notation. In prefix notation, the operators are placed before the operand. In postfix notation, this order is reversed.

Actually, the reverse Polish notation was invented by  Australian philosopher and computer scientist Charles Hamblin in the 1950s, to enable zero-address memory stores, and it was derived from the Polish notation. Hamblin presented his work at a conference in June 1957, and published it in 1957 and 1962 [4],  [5]  .

In the years that followed, it was realized that the postfix notation is more efficient for computer computations in comparison with the infix notation. The postfix expression is scanned from left to right and the operands are simply placed into a last-in, first-out (LIFO) stack , while the operators may be immediately applied to the operands at the bottom of the stack. By contrast, the infix notation requires that the realization of operators actions be delayed until some later point. Therefore the compilers on almost all modern computers convert statements to postfix notation for execution [6].   

It is reported that the first computers which implement architectures enabling postfix notation were the English Electric Company’s KDF9 machine   , announced in 1960 and available commercially in 1963, and the American Burroughs B5000, announced in 1961 and also delivered in 1963. One of the designers of the B5000   was R. S. Barton who developed the postfix notation independently of Hamblin, sometime in 1958, before as he was aware of Hamblin’,s work, and was motivated by a a textbook on symbolic logic. Friden introduced postfix notation to the desktop calculator market with the EC-130 in June of 1963 .

The postfix notation was popularized to engineering and scientific community by Hewlett-Packard desktop calculator 9100A.  The first handheld scientific calculator using postfix notation HP-35 produced from 1972.  

Postfix notation

Postfix notation is a parentheses-free way of writing algebraic expressions without the use of rules of operator precedence. The expression is written as in postfix notation.

The expression can be written as , but also as . In both cases it is assumed that arity of the operator is known. Evaluation (or implementation) of postfix notation is stack-based . The operands are popped from a stack, and results of calculations are pushed back onto it. Though this seems very obscure, the in formal systems (like computers) the expression can be easily analyzed and precessed.

For example, Postscript uses postfix notation.

Evaluating postfix notation

The best way how to explain the evaluation process is to use a stack. The postfix expression to be evaluated is scanned from the left to right. The constants (or variables) are successively how encountered pushed onto the stack. When an operator, say -ary operation, is encountered, the indicated action is performed on the group of the top elements of the stack, and the result replaces this group of operands under action.

Example: 12  2  +  11  4  -  /     gives

Converting conventional infix notation to postfix

Start by inserting all the implicit brackets that show the order of evaluation, i.e. the parenthesization of the expression should correspond to the standard rules of operators precedence. For instance, and   (or and ) have the same precedence, but and have higher precedence than or .  Then enclose the whole expression into the surrounding pairs of parentheses . After that, the expression is processed according to the following rules:

• every left parenthesis is pushed onto the stack when encountered
• when a right parenthesis is encountered, the operator symbol at the top of the stack is popped off the stack and copied to the output. At the top of the stack there is a left parenthesis, and both parentheses are discarded.
• when the stack is empty the procedure finishes.

Example:    gives

If we use the standard infix notation without additional parenthisisation the we can proceed as follows:

• we place a terminating symbol, say  , at the end of the infix expression. This will serve as a marker for the end of input. Simultaneously we also push this symbol onto the stack .
• constants (or variables) are sent to the output
• left parentheses are always pushed onto the stack
• when a right parenthesis is encountered pop the top of the stack until a left parenthesis is at the top of the stack
• if the operator being scanned is an operator of a higher precedence than the operator  at the top of the stack, the symbol being scanned is pushed onto the stack
• if the precedence of the operator being scanned is lower than or equal to the precedence of the operator at the top of the stack the top element of the stack is popped to the output and the scan pointer does not advance. Instead, the symbol being scanned will be compared with the new top element on the stack, and the procedure will be repeated until a operator of lower precedence Then push the operator onto the stack.
• when the terminating symbol is scanned the remaining operator on the stack are popped to the output, and the algorithm terminates.¹

Example:    gives

A very natural is the conversion using trees representation of fully parenthesized expressions:

Prefix notation

Another possibility for ordering of functions and operands. In prefix notation the function precedes all its operands, e.g. becomes .  Commutative law for addition has in the prefix notation form: , and the associative one: .

Prefix notation corresponds more closely to many natural language constructions like “add 3 to 5”, i.e. , or with connection with functions ” of ", etc.

LISP is probably the best known programming language to use prefix notation.

Consider expression . In the prefix notation it becomes . Scanning this expression from left to fight we find out that:

• we are going to be subtracting one number from another
• then we are going to add the first encountered number to some other number
• this second summand is a result of a multiplication; the factors of the product are given directly as and yielding the product
• since the addition requires two summands we can complete it getting 7
• continuing the scanning we find out that we have to subtract from the result of a division of yielding , and subtracting this from we get .

In postfix notation the above expression looks like this . This example shows that the evaluation of a prefix formula requires to remember the executed operation until we finally get the numbers to plug in. In contrast to a postfix formula, we never have to remember the operation, we have only remember the numbers before we learn what we shall do with them.     

Notes

1	If a left parenthesis is at the top of the stack when the terminating symbol is scanned, or a right parenthesis is scanned when the terminating symbol is at the top of the stack , the parenthesization of the original expression was unbalanced and an unrecoverable error has occurred

References

Cite this web-page as: