Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Applications

 

Consider the following expression:

  equation6183

In order to determine the value of this expression, we first compute the sum 5+9 and then multiply that by 2. Then we compute the product tex2html_wrap_inline61390 and add it to the previous result to get the final answer. Notice that the order in which the operations are to be done is crucial. Clearly if the operations are not done in the correct order, the wrong result is computed.

The expression above is written using the usual mathematical notation. This notation is called infix  notation. What distinguishes this notation is the way that expressions involving binary operators are written. A binary operator  is an operator which has exactly two operands, such as + and tex2html_wrap_inline61394. In infix notation, binary operators appear in between their operands.

Another characteristic of infix notation is that the order of operations is determined by operator precedence . For example, the tex2html_wrap_inline61394 (multiplication) operator has higher precedence than does the + (addition) operator. When an evaluation order is desired that is different from that provided by the precedence, parentheses , ``('' and ``)'', are used to override precedence rules. I.e., an expression in parentheses is evaluated first.

As an alternative to infix, the Polish logician Jan tex2html_wrap61408 ukasiewicz  introduced notations which require neither parentheses nor operator precedence rules. The first of these, the so-called Polish notation , places the binary operators before their operands. I.e., for Equation gif we would write:

displaymath61382

This is also called prefix notation, because the operators are written in front of their operands.

While prefix notation is completely unambiguous in the absence of parentheses, it is not very easy to read. A minor syntactic variation on prefix is to write the operands as a comma-separated list enclosed in parentheses as follows:

displaymath61383

While this notation seems somewhat foreign, in fact it is precisely the notation that is used for function calls in C++:

operator+ (operator* (operator+ (5,9) ,2), operator* (6,5));

The second form of tex2html_wrap61408 ukasiewicz notation is the so-called Reverse-Polish notation  (RPN ). Equation gif is written as follows in RPN:

  equation6214

This notation is also called postfix notation for the obvious reason--the operators are written after their operands.

Postfix notation, like prefix notation, does not make use of operator precedence nor does it require the use of parentheses. A postfix expression can always be written without parentheses that expresses the desired evaluation order. E.g., the expression tex2html_wrap_inline61400, in which the multiplication is done first, is written tex2html_wrap_inline61402; whereas the expression tex2html_wrap_inline61404 is written tex2html_wrap_inline61406.




next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.