Skip to content

Instantly share code, notes, and snippets.

@malandrina
Created September 18, 2012 18:26
Show Gist options
  • Save malandrina/3744867 to your computer and use it in GitHub Desktop.
Save malandrina/3744867 to your computer and use it in GitHub Desktop.
Implementing a Reverse Polish Notation Calculator in Ruby

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
@JohnSmall
Copy link

@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

@stvhay
Copy link

stvhay commented Sep 7, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment