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. Refer 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 necessary. 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 occurred: ' + \$!.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 occurred: Syntax error
>> 8.5 *
Error occurred: 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 powered by Disqus