Lukasz Wrobel - Renaissance programmer

In the introduction to building a math parser I already mentioned the Reverse Polish notation, also called "postfix notation".

Its main advantage is unambiguity: you can simply read expression from left to right and calculate its value at the same time. You have to neither set up operators priorities nor use parenthesis. Referer to the Reverse Polish notation description for further details.

There are many implementations of Reverse Polish notation parser available, but most of them seem to be too complicated. So I decided to write a very simple RPNParser Ruby class (RPN comes from "Reverse Polish notation"):

# Author::    Lukasz Wrobel 
# Url::       http://lukaszwrobel.pl/

class RPNParser
  def parse(input)
    stack = []

    input.lstrip!
    while input.length > 0
      case input
        when /\A-?\d+(\.\d+)?/
          stack.push($&.to_f)
        when /\S*/
          raise 'Syntax error' if stack.size < 2

          second_operand = stack.pop()
          first_operand = stack.pop()

          stack.push(first_operand.send($&, second_operand))
      end

      input = $'
      input.lstrip!
    end

    raise 'Syntax error' if stack.size != 1

    stack.pop()
  end
end

As you can see, the RPNParser class is very short and this is mostly because of the magic I'll describe later on. The parse() method reads the input from left to right and recognizes symbols either as numbers or operators, omitting white spaces if neccessary. If current symbol is a number, then it is pushed at top of the stack. If the symbol is an operator, like "+" or "/", two numbers are being taken from the top of the stack. Then the calculation is performed and its result is pushed to the top of the stack. After the input is read, there should be only one element left on the stack. It is the value of the whole expression.

Numbers can be expressed with or without decimal separator; minus sign is also available. For example, 3, 3.0, 17.6, -5 and -8.92 are valid numbers.

Currently, the parse() method assumes that all operators require 2 arguments. That is why there should be at least two elements on the stack before performing a calculation. The truth is that most of the math operators we use in expressions require exactly 2 arguments, so it shouldn't be a troublesome limitation.

Have you noticed that there is no case block to distinguish between operators? I mean something like this:

case operator
  when '+'
    result = first_operand + second_operand
  when '-'
    result = first_operand - second_operand
  when '*'
    result = first_operand * second_operand
  ...

Instead of doing distinction like this, I used the Ruby's send() method. It can be used to send any message (i.e. invoke a method) to the object. That is why all basic math operators work in our Reverse Polish notation parser. Morover, methods like '%', 'div' and '**' also work!

I wrote a simple demonstration script to interact easily with the parser:

require 'rpn_parser'

parser = RPNParser.new

loop do
  begin
    print '>> '
    puts parser.parse(gets)
  rescue RuntimeError
    puts 'Error occured: ' + $!
  end
end

Here is an example session with the Reverse Polish notation parser:

>> 2 5 +
7.0
>> 5 8 2 + *
50.0
>> 16 2 **
256.0
>> 45 18 div
2
>> 32 3 %
2.0

Let's try to use different number formats:

>> 8.2 0.8 1 + +
10.0
>> -5 3.0 *
-15.0
>> -9.521 -7 *
66.647

This is what happens when we type in a wrong expression:

>> 1 8 5 +
Error occured: Syntax error
>> 8.5 *
Error occured: Syntax error

By writing 20 lines of code and clever use of some Ruby's abilities, we made a quite useful Reverse Polish notation parser. Feel free to further experiment with the RPNParser class.