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.
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