Stacks and Reverse Polish

We are accustomed to the 'infix' system of mathematical notation, as in '2+2', 'a*b-c', etc. There are two alternatives to placing the operators between the operands: one is to place the operator in front of its two operands (known as 'prefix'); the other is to place the operator after its two operands (known as 'postfix').

In prefix or Polish Notation '2+2' becomes '+2 2'; in postfix or Reverse Polish it becomes '2 2+'.

Prefix and postfix are important in computing because they provide a better mdel of how the arithmetic and logic unit (ALU) inside a CPU works. A program must present two operands to the ALU before it can perform an arithmetic or logical operation on them, such as add or AND. (It is also the way the brain works: there must be two operands before the brain can operate on them; or we have an operation in mind e.g. + so we need two operands to add together.)

One of the tasks of a compiler, therefore, is to convert the infix notation of programmers into the postfix order that the ALU can process. The program presented here converts from infix to postfix but does not calculate the answers to expressions: this is left to the reader to complete.

Some computer languages include postfix notation as an option (Logo, for example) and early calculators (notably those from HP) required input in postfix.

It was a Polish logician called Jan Lukasiewicz (hence the name Polish notation) who invented the prefix notaiton in the 1920s; he noticed that brackets were not required in prefix (or postfix) notation in order to guarantee correct observation of operator precedence (so long as each operator was binary - or that the 'arity' is fixed). In standard infix notation the expressions 'a*b+c' and 'a*(b+c)' have different outcomes but in Polish and Reverse Polish notation brackets are not required.

(Note that the scheme used here applies to binary operators only. Note also that unary minus e.g. -5 is prefix while unary factorial e.g. 5! is postfix.)

The postfix form of 'a*(b+c)' is: abc+*. This is evaluated by proceeding to the first operator (+) and applying to the two preceding operands; this makes a new operand (the result of b+c); the next operator is * and its operands are b+c and a. Analysis of postfix expressions is often done by underlining the operator-operands triplet:

abc+* and ad* (where d = b+c)

There are at least two ways to convert infix to postfix, one involving a binary tree structure and the other a stack. It happens that, if an expression is entered into a binary tree with the operators in parent nodes and the operands in child leaves (with no further links) the resulting tree structure can be traversed in the three standard ways to produce the three forms of expressions: inorder traversal gives an infix expression; preorder traversal gives prefix notation; and postorder traversal gives postfix notation. Try this with the following:

           *
         /    \
      +        c
    /    \
  a       b 

The second way to convert between infix and postfix is the one followed here, using a stack. Operators are placed on a stack and popped from it into the postfix expression according to their precedence.

For the program we create a form:

We make some declarations in the public section of the form class:

stack:array[1..50] of char;
expression:string;
rpnexpression:string;

Note that the stack is declared as an array of characters rather than as a string; this is so that the notation stack[top] can be used to access individual elements.

The algorithm we are seeking to implement in code is as follows:

• For the length of the infix expression do:
• get the next token from the infix expression
• evaluate the token: it might be:
• a left bracket : push it on the stack, what follows has a higher priority
• an operand : add it to the postfix expression
• an operator : if the stack is empty push it on the stack; if the stack is not empty compare the new operator with the operator at the top of the stack; if the priority of the new operator is greater than that on the stack then push the new operator onto the stack (e.g. * > + so add * to stack); if the priority of the new operator is less than or equal to the operator on the stack then add the current operator to the postfix expression (e.g. + < * so add + to the expression)
• a right bracket : pop elements from the stack and add them to the postfix expression until a left bracket is reached; pop the left bracket.
• when the end of the infix expression is reached pop the remaining items in the stack and add them to the postfix expression until the stack is empty.

Note that this algorithm provides an example of a push-down automaton, a simple model of a computer that includes a stack; the top of the stack can be used to determine the next transition and can manipulate the stack when performing a transition.

The work is done by the Convert button:

The comments should explain the program logic and mechanism.

An Object-Oriented Solution

We can make a better job of this program by employing some object oriented techniques. Instead of placing the procedures for manipulating the stack and generating the postfix expression inside the ButtonClick procedure we can create a class for the object and thus make its fields and members available to the rest of the program. When the procedures are declared inside the ButtonClick procedure they are, because of the rules of scope, only visible from within ButtonClick. By placing them in a class in the unit we can make them available to the unit as a whole and also to other units that want to use the class and its methods.

To begin this approach we define the stack as a class, simply by moving the elements of code we already have:

Back