This algorithm is a variation of Dijkstra's "shunting yard" algorithm for processing a infix expression left-to-right, and generating the corresponding RPN (postfix) expression.
It assumes that the expressions are composed of tokens which can be one of: operands, such as variable and constants; operators, which have a precedence of evaluation (and may have other properties such as associativity); or '(' or ')' which come in pairs and override operator precedence. Typical operator precedence levels are shown at the end.
- Open the input and the output.
- Do:
- Get next token from input.
- Choose:
- if token is an operand, then write it to output.
- else if token is an operator, then:
- while ( (token's precedence) ≤ (precedence of the operator on top of the operator-stack) ):
- pop the top operator from the operator-stack and write it to output.
- push the token onto the operator-stack.
- else if token is '(', then push it onto the operator-stack (with precedence
-1).
- else if token is ')', then:
- while (the top of the operator-stack is not a '(' ):
- pop the top operator from the operator-stack and write it to output.
- if the operator-stack becomes empty, then a parentheses-balancing error has occurred. Complain bitterly.
- pop the '(' off the operator-stack; discard it and the token.
- else some token error has occurred. Abandon the conversion.
- Repeat these steps as long as input tokens are available.
- While (the operator-stack is not empty):
- pop the top operator from the operator-stack and write it to output.
- If (the top of the operator-stack is a '(' ), then a parentheses-balancing error has occurred. Complain bitterly.
- Close the input and the output.
| precedence | operator | (typical operation) |
| 9 | ^ | exponentiation |
| 9 | - | unary negation (right-associative) |
| 8 | * | multiplication |
| 8 | / | division |
| 8 | % | remainder |
| 6 | + | addition |
| 6 | - | subtraction |
| -1 | ( | begin-grouping |
| ? | ) | end-grouping (no precedence) |
The levels in this table are arbitrary, spaced to permit insertions of additional operators conveniently (sort of like old-style FORTRAN or BASIC line numbers). Only the relative ordering is important. Note, however, that '(' must have the "absolute lowest" precedence to make the precedence-comparison step work properly, while ')' doesn't have any precedence since it is never compared to any operators.
Some links to material about RPN; in no particular order.
(In the links below, "Ł" should look like a capital "L" with a slanted bar through it.)
- wikipedia article
- More detail about RPN; similar description of the conversion algorithm.
- Postfix Notation Mini-Lecture
- Description and animation of RPN in action; discussion of Tanenbaum's presentation of the conversion algorithm
- Using Reverse Polish (Postfix) Notation
- Writeup by Stephen Schmitt, including references to Łukasiewicz' work.
- Teaching FORTH
- Old FORTH magazine, discussing aspects of RPN calculations (FORTH language is based on RPN).
- Art of Assembly - pdf format
- Art of Assembly - html pages
- Art of Assembly - Chapter 16, section 6
- This online Assembly textbook shows an assembly-language infix-to-postfix conversion program in Chapter 16, section 6.
- hpmuseum.org
- An overview of RPN in the context of H-P calculators.
- Jan Łukasiewicz
- Jan Łukasiewicz (1878 - 1956)
- Some biographies of Jan Łukasiewicz.
- Łukasiewicz's Logic and Prime Numbers
- Introduction and table of contents to a book on Łukasiewicz logics. In pdf format.