Implementing a Reverse Polish Notation Calculator in Ruby

gistfile1.md

Implementing a Reverse Polish notation calculator in Ruby

A couple weeks ago I had a go at implementing an RPN calculator in Ruby. I knew I wanted the calculator to function by popping operands out of an array populated with the values of the input expression, operating upon the operands with the appropriate operator, and pushing the result back into the stack of operands.

I was able to implement this in version 1, but it took forever and the resulting code was not very beautiful. Why?

• I started coding before I had a thorough understanding of RPN

  Wait, 20 10 5 4 + * - is what now?

• I also jumped into coding before doing research on potentially relevant public methods

  Oh hey there,#send and #eval. Guess I can delete all those instance methods I created for each operator ...

• Also, I am a noob.

RPN calculator, version 1 (the long, ugly one):

class RPNCalculator
        # Define methods for addition, multiplication, and subtraction
	def sum(array)
		result = 0
		array.each do |i|
			result += i.to_i
		end
		result
	end

	def product(array)
		result = 1
		array.each do |i|
			result *= i.to_i
		end
		result
	end

	def difference(array)
		if array.length < 2
			0
		else
			array[0].to_i - array[1].to_i
		end
	end

        # Define a method which evaluates an expression in RPN
	def evaluate(expression)
		expression_array = expression.split
		operands = []

		if expression_array.length == 1
			evaluation = expression_array
		end

		expression_array.each do |i|
			if i.match(/[0-9]/) != nil
				operands.push(i)
			elsif i == "+"
				operands.push(sum(operands.pop(2)))
			elsif i == "*"
				operands.push(product(operands.pop(2)))
			elsif i == "-"
				operands.push(difference(operands.pop(2)))
			end
		end
		puts operands
	end
end

When I wrote version 2 of the calculator, I had two goals: To make it shorter and more elegant, and to augment its functionality by including division and exponentiation.

Et voilà!

RPN calculator, version 2:

class RPNCalculator
	def evaluate(expression)
		expression = expression.split
		operands = []
		evaluation = []

		expression.each do |x|
			case x
				when /\d/
					evaluation.push(x.to_f)
				when "-", "/", "*", "+", "**"
					operands = evaluation.pop(2)
					evaluation.push(operands[0].send(x, operands[1]))
			end
		end
		puts evaluation
	end
end

Here is cool implementation of a Reverse Polish Notation Calculator by @wrobellukasz.
http://lukaszwrobel.pl/blog/reverse-polish-notation-parser

# 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

@malandrina Your version 2 is impressively short!

That is really sexy!

can you help explain what this line means?

operands[0].send(x, operands[1])

Thanks!

@buluidong the send method passes on an arbitrary message to object, that message was created by doing pretty much this (evaluation.pop(2))[0]. The second half of your question being about what (x, operands[1]) does. I think that what this does is push the variable created in case x, and the product of operands[1] as a whole, due to only wanting to use the send method on operands[0] and not the whole contents of the parentheses. in conclusion evaluation uses push on the result of operands[0].send, as well as (x, operands[1]. I could be way off but this is my 2 cents. Hope this helps.

• Kyle

I know it's been so long, but I was looking into this kind of problem and came up with a different solution. Hope it helps!

class RPNCalculator
  OPERATORS = %w(+ - * / **)

  def initialize(expression)
    @elements = expression.split
    @stack = Array.new
  end

  def call
    @elements.each do |element|
      if OPERATORS.include? element
        calculate(element)
      else
        @stack.push(element.to_i)
      end
    end

    @stack.first
  end

  def calculate(operator)
    operands = @stack.pop(2)
    result = operands.inject(operator)
    @stack.push(result)
  end
end

Here's a short version (albiet CoffeeScript) that goes a little farther to also return the result (no eval)
https://gist.github.com/mikesmullin/a6918611ed7abbab8f09d5a5001b4a00

@iagomoreira

It should be

 @stack.last

not

 @stack.first

If you use "19 0 4 5 *" you'll see the problem. You get back 19 not 20 because pop and push operate on the end of the array so to get back the last pushed value you have to use @stack.last

Here's mine.

https://github.com/tablador/rpn_calc/blob/master/rpn_calc.rb