Infix to RPN/postfix
P.J. Drongowski
16 October 2004
Background
* One of the simplest notations for arithmetic expression is
Reverse Polish Notation (RPN) also called "postfix" notation
+ Invented by Polish logician Jan Lukasiewicz
+ Does not require parentheses
* PostScript, which is stack-based, uses a form of RPN for everything,
including arithmetic
* Stacks are an easy way to evaluate an RPN expression once an infix
expression has been converted to RPN
Algorithm for converting infix to postfix (RPN)
Given:
* An infix expression consisting of tokens: constants, variables,
operators and parentheses; constants and variables are operands
* Precedence between operators; A left parenthesis has a lower
precedence than any operator
* A place to hold or output the postfix expression
* A stack which is used to store operators
Steps
1. Initialize the stack to its empty state
2. While no error has occurred and the end of the infix expression
has not been reached:
a. Get the next input token
b. If the token is:
Left parenthesis Push it onto the stack
Right parenthesis Pop and output stack elements until a left
parenthesis is encountered. Pop the left
parenthesis. If the stack becomes empty, the
parens are unbalanced and an error is reported
Operator If the stack is empty or the token has a higher
priority than the top stack element, push token
on the stack
Otherwise, pop and output the top stack element
and repeat comparison of token with the new
top of stack
Operand Output the operand
3. When the end of the infix expression is reached, pop and output
any stack items until the stack is empty
Source: ADTs, Data Structures and Problem Solving with C++,
Larry Nyhoff, Pearson Prentice Hall
****************************************************************
Example (Nyhoff)
Expression Stack Output Action
------------------ -------- ---------- -----------------
7 * 8 - ( 2 + 3 ) 7 Output 7
* 8 - ( 2 + 3 ) * 7 Push *
8 - ( 2 + 3 ) * 7 8 Output 8
- ( 2 + 3 ) 7 8 * Pop and output *
- ( 2 + 3 ) - 7 8 * Push -
( 2 + 3 ) - ( 7 8 * Push (
2 + 3 ) - ( 7 8 * 2 Output 2
+ 3 ) - ( + 7 8 * 2 Push +
3 ) - ( + 7 8 * 2 3 Push 3
) - ( 7 8 * 2 3 + Pop and output +
) - 7 8 * 2 3 + Pop (
7 8 * 2 3 + - Pop and output -
****************************************************************
Another statement of the conversion algorithm
Given:
* A set of operators and operator precedence {+, -, *, /}
where * and / have higher precedence than + and -
* A stack to hold operand (e.g., variable, number) and operator symbols
* A place to put the postfix expression ("the output")
1. Variables and numbers are copied to the output
2. Left parentheses are pushed on the stack
3. When a right parenthesis is encountered, the symbol at the top of the
stack is popped and is copied to the output until the symbol at the
top of the stack is a left parenthesis. When a left parenthesis is found,
both parentheses are discarded.
4. If the current symbol has a higher precedence than the symbol on top
of the stack, the current symbol is pushed.
5. If the precedence of the current symbol is lower than or equal to the
precedence of the symbol on the top of the stack, then the stack is
popped to the output until a symbol of lower or equal precedence
6. When the terminating symbol is reached, the stack is popped to the
output and the algorithm terminates.
7. If the top of the stack is a left parenthesis and the terminating
symbol is scanned, or a right parenthesis is scanned when the terminating
symbol is at the top of the stack, the parentheses of the original
expression were unbalanced and an unrecoverable error has occurred.
Source: Bob Brown, Southern Polytechnic State University