Reverse Polish Notation - An Introduction

Reverse Polish Notation (RPN) is a stack-based method for performing operations on data. It is used on some Hewlett-Packard scientific calculators and in computer languages such as PostScript and FORTH. Its advantages over normal `infix' notation are a) simplicity of implementation, b) avoidance of ambiguity and the need to parentheses.

Imagine a stack as being like a pile of plates. You can add plates to the top of the stack, or you can remove plates from the top. You cannot remove or insert plates anywhere other than at the top of the stack.

Operators, such as AND, OR and NOT remove one (or more) items from the top of the stack and replace them with other items.

Imagine the stack contains the values:

                TRUE
                FALSE
                ...
                ...

i.e. the top two values on the stack are the logical values TRUE and FALSE. The OR operator would take the top two values off the stack. It would then perform a logical OR between them and place the result back on the stack. Thus, after using the OR operator, the stack would contain:

                TRUE
                ...
                ...

If one had used an AND operator instead, the stack would contain:

                FALSE
                ...
                ...

The NOT operator acts in much the same way, but takes just one logical value from the top of the stack and replaces it with the opposite value. Thus if one starts with the stack:

                FALSE
                ...
                ...

and uses the NOT operator, the resulting stack will be:

                TRUE
                ...
                ...

In KabatMan, each entry in the database effectively has a stack associated with it. When a WHERE clause is issued (for example res(L29) = P), a value of TRUE is placed on top of each stack for which the condition is true. i.e. for every entry where residue L29 is a proline a TRUE is placed on that entry's stack. For every other entry, a FALSE is placed on its stack.

When a logical operator is used, it is applied to every entry's stack. If the stack does not contain enough entries for the operator to act on, or the stack contains more than one entry after all the logical operators have been applied, an error message is displayed.


The concept of the stack means that the same query can be expressed in different ways. For example, the query:

SELECT pir
WHERE  source   includes mouse
       antigen  includes lysozyme   AND
       complete eq       true       AND

could also be expressed as:

SELECT pir
WHERE  source   includes mouse
       antigen  includes lysozyme   
       complete eq       true       AND  AND

Both are equally correct, but the first is simpler to understand and uses less entries in the stack.

In the first example, the first where clause (source includes mouse) places an entry onto the stack as does the second clause (antigen includes lysozyme). The AND takes the top two items off the stack and places a single item (the logical AND of the two items) onto the stack - there is now just one entry on the stack. The third where clause (complete eq true) adds one entry onto the stack (so there are now two entries on the stack) and the final AND takes the two items off the stack and replaces them with the logical AND of these two items. Thus the stack depth is never greater than 2.

In the second example, the first where clause (source includes mouse) places an entry onto the stack as do the second (antigen includes lysozyme) and third (complete eq true) clauses. The stack now contains three entries. The first AND takes the top two items off the stack and places a single item (the logical AND of the two items) onto the stack; there are now two entries on the stack. The second AND does the same, leaving a single entry on the stack. Thus, the maximum stack depth during this process was 3.

KabatMan allows a maximum stack depth of 10 which should be enough for pretty much every conceivable query. It is almost always possible to rephrase a long query to reduce stack usage. If you really need more stack depth than this, please EMail me.


Copyright (c) 1995-2005, Andrew C.R. Martin, UCL