# 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