Reverse Polish Notation Parser

March 22, 2009 / category: Parsing / 8 comments

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.

My eBook: “Memoirs of a Software Team Leader”
Read more »


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. Moreover, methods like '%', 'div' and '**' also work!

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

require_relative 'rpn_parser'

parser = RPNParser.new

loop do
  begin
    print '>> '
    puts parser.parse(gets)
  rescue RuntimeError
    puts 'Error occured: ' + $!.backtrace.join("\n")
  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.

Comments

There are 8 comments / Submit your comment

AdronRBO
June 23, 2009 08:02 PM

Enjoyed your article on RPN especially since I'm a long time fan of HP RPN calculators. Using the "send" method was a nice touch and one of the powerful features in Ruby. Hope to put your class to use calculating ion chromatograms from mass spectrometry data.

FABRE hugo
February 09, 2013 07:19 PM

Hello,

I'm a french student, and i'm learning ruby by myself, i tried your code and it's not working (Runtime error):

parsing.rb:22:in `parse':undefined method `+456*789/98' for nil:NilClass (NoMethodError)

Lukasz Wrobel
February 10, 2013 04:47 PM

@Fabre:

While I see at least two slight modifications that my code requires to interact properly with modern Ruby interpreters, there could be another problem. Your expression may not be valid in the terms of Reverse Polish notation.

Please provide me with exact source code you're using, including its invocation and Ruby interpreter version. I'll try to help.

FABRE hugo
March 10, 2013 09:04 AM

I have just seen your answer, effectively i used a wrong expression but i think that the error come from something else.

I use the last version of ruby (1.7.x i think) the source code is a copy/paste from your's.

FABRE hugo
March 10, 2013 09:08 AM

Op sorry, it's 1.9.3p385

Lukasz Wrobel
March 10, 2013 03:57 PM

@Fabre:

I've just installed the same Ruby version as you. There are two problems with the demonstration script:

  • Since Ruby 1.9, current directory is no longer in LOAD_PATH. It's better to use require_relative instead of require.
  • RuntimeError can't be converted into string, one have to call to_s directly or use backtrace for more verbosity.

Both problems are fixed in the article now. If this won't help, please paste your source code, expression you're using and error message.

FABRE hugo
March 13, 2013 04:31 PM

It's now working, thank you, but your parser doesn't work if user doesn't space between number, it's not working but maybe you do it on purpose.

Lukasz Wrobel
March 13, 2013 08:53 PM

@Fabre:

I'm glad to hear that it's working now.

if user doesn't space between number, it's not working

I'm sorry, but I don't get your point. The lexer part is actually very simple, it treats input parts either as:

  • numbers with an optional decimal separator
  • method's names

If there is no space between two numbers, the lexer is not able to guess which part belongs to which number. However, there is no need for putting a space between a number and method name, like in 2 3+. Why? Because method name in Ruby can't begin with a number.

You can use Markdown in your comments if you wish. Examples:

*emphasis*
emphasis
**strong**
strong
`inline code`
inline code
[My blog](http://lukaszwrobel.pl)
My blog
# use 4 spaces to indent
# a block of code
    def my_method(x)
      x = x + 1
    end
def my_method(x)
  x = x + 1
end

* First.
* Second.
  • First.
  • Second.

> This is a citation.
> Even more citation.

I don't agree with you.

This is a citation. Even more citation.

I don't agree with you.


Submit your comment

(required)

(optional)

(required, Markdown supported)


Preview:

My eBook: “Memoirs of a Software Team Leader”

Read more »