Using Reverse Polish (Postfix) Notation

by Stephen R. Schmitt

Introduction

In algebra, or infix notation, operators appears between operands:

2 + 3 -> 5
6 - 4 -> 2
2 + 3×4 -> 2 + 12 -> 14
(4 + 5)×6 -> 9 × 6 -> 54

In prefix notation, operators precede operands:

+ 2 3 -> 5
- 6 4 -> 2
+ 2 × 3 4 -> + 2 12 -> 14
× + 4 5 6 -> × 9 6 -> 54

In postfix notation operators follow operands:

2 3 + -> 5
6 4 - -> 2
2 3 4 × + -> 2 12 + -> 14
4 5 + 6 × -> 9 6 × -> 54

RPN is easily implemented in a computer since it can be performed using a data structure called a stack. In a stack, objects are added to the top and removed from the top. This is sometimes called last-in, first-out or LIFO. As a postfix expression is read from left to right, operands are placed on top of the stack. Operators are applied to the operands at the top of the stack.

RPN algorithm

1. Get a token (operator or operand) from the input text.
2. If the token is an operand, push it onto the top of the stack.
3. If the token is an operator, pop the top two operands from the stack, perform the operation, and push the result onto the top of the stack.
4. Repeat 1...3 until there are no more tokens.

2 3 4 × +

token	action	stack
2	push 2	{2}
3	push 3	{2, 3}
4	push 4	{2, 3, 4}
×	pop 4, pop 3, multiply, push 12	{2, 12}
+	pop 12, pop 2, add, push 14	{14}

A more complex expression:

2 3 × 12 3 ÷ + 5 3 × 6 + -  

token	action	stack
2	push 2	{2}
3	push 3	{2, 3}
×	pop 3, pop 2, multiply, push 6	{6}
12	push 12	{6, 12}
3	push 3	{6, 12, 3}
÷	pop 3, pop 12, divide, push 4	{6, 4}
+	pop 4, pop 6, add, push 10	{10}
5	push 5	{10, 5}
3	push 3	{10, 5, 3}
×	pop 3, pop 5, multiply, push 15	{10, 15}
6	push 6	{10, 15, 6}
+	pop 6, pop 15, add, push 21	{10, 21}
-	pop 21, pop 10, subtract, push -11	{-11}

Zeno source code

Zeno 1.2 is an interpreter for the Zeno programming language. It is an easy to learn and is suitable for educational purposes.

• Download Page

var R : array[64] of real               % stack
var expn : string                       % for keyboard input
var i, len, n : int                     % global values

program

    while true
        put "enter an RPN expression:"
        get expn : *
        exit when strlen( expn ) = 0 
        put "expn: ",expn      
        rpn( expn )
    end while

end program

% interpret reverse polish (postfix) expression
procedure rpn( expn : string )

    var ch : string
    
    expn := expn & " "                  % must terminate line with space
    len := strlen( expn )

    i := 0
    n := 1
    R[n] := 0.0                         % push zero for unary operations

    while true

        exit when i >= len              % at end of line
        incr i

        continue when expn[i] = ' '     % skip white spaces

        if is_digit( expn[i] ) then     % push number onto stack
            incr n
            R[n] := get_number
        elsif expn[i] = '+' then        % add and pop stack
            if n < 2 then
                put "stack underflow"
            else
                R[n-1] := R[n-1] + R[n]
                decr n
            end if
        elsif expn[i] = '-' then        % subtract and pop stack
            if n < 2 then
                put "stack underflow"
            else
                R[n-1] := R[n-1] - R[n]
                decr n
            end if
        elsif expn[i] = '*' then        % multiply and pop stack
            if n < 2 then
                put "stack underflow"
            else
                R[n-1] := R[n-1] * R[n]
                decr n
            end if
        elsif expn[i] = '/' then        % divide and pop stack
            if n < 2 then
                put "stack underflow"
            else
                R[n-1] := R[n-1] / R[n]
                decr n
            end if
        else
            put duplicate( " ", i+5 ), "^ error"
            exit
        end if
    end while

    put "result: ", R[n]                % end of main program

end procedure

% extract a number from a string
function get_number : real

    var j : int := 1                    % start of number string
    var number : string                 % buffer for conversion

    while true                          % get integer part
        number[j] := expn[i]
        incr i
        incr j
        continue when is_digit( expn[i] )
        if expn[i] = '.' then          
            number[j] := expn[i]        % include decimal point
            incr i
            incr j
            while is_digit( expn[i] )   % get fractional part
                number[j] := expn[i]
                incr i
                incr j
            end while
        end if
        number[j] := chr( 0 )           % null terminate string
        exit
    end while

    return strreal( number )

end function

% check for digit character
function is_digit( ch : char ) : boolean

    return ('0' <= expn[i]) and (expn[i] <= '9')

end function

% duplicate string
function duplicate( s : string, n : int ) : string

    var rv : string := ""
    
    while n > 0
        rv := rv & s
        decr n
    end while

    return rv

end function

Sample output

enter an RPN expression:
? 2 3 +
expn: 2 3 +
result: 5
enter an RPN expression:
? 4 6 -
expn: 4 6 -
result: -2
enter an RPN expression:
? 7 -
expn: 7 -
result: -7
enter an RPN expression:
? 2 3 4 * +
expn: 2 3 4 * +
result: 14
enter an RPN expression:
? 2 3 * 12 3 / + 5 3 * 6 + -
expn: 2 3 * 12 3 / + 5 3 * 6 + -
result: -11
enter an RPN expression:
?

Reference

1. Lukasiewicz, Jan, ELEMENTY LOGIKI MATEMATYCZNEJ, Warsaw, 1st Edition 1929
2. English translation:
   Olgierd Wojtasiewicz, ELEMENTS OF MATHEMATICAL LOGIC, New York, The MacMillan Company, 1963

AbCd Classics - free on-line books