Skip to content

Instantly share code, notes, and snippets.

@MaxPleaner
Last active August 29, 2015 14:03
Show Gist options
  • Save MaxPleaner/7371257fdab06ec53cdb to your computer and use it in GitHub Desktop.
Save MaxPleaner/7371257fdab06ec53cdb to your computer and use it in GitHub Desktop.
http://i.imgur.com/mJcdyct.png
note: "brake" is an alias for "bundle exec rake"
class RPNCalculator
def initialize
@commands = []
@stack = []
end
def safe_add(operator)
if @commands.length >= 2
@commands.push(operator)
else
raise Exception.new("calculator is empty")
end
end
def push(num)
@commands.push(num)
end
def plus
safe_add("+")
end
def minus
safe_add("-")
end
def times
safe_add("*")
end
def divide
safe_add("/")
end
def self.compute(items)
case items[-1]
when "+"
items[-3..-1] = items[-2] + items[-3]
when "-"
items[-3..-1] = items[-3] - items[-2]
when "*"
items[-3..-1] = items[-3].to_f * items[-2].to_f
when "/"
items[-3..-1] = items[-3].to_f / items[-2].to_f
end
items[-1]
end
def self.value(commands, stack)
operator_index = []
commands.each_with_index do |item, index|
if item =~ /[\+\-\*\/]/
stack.push(commands[(index-2)..index])
operator_index = index
break
end
end
commands[(operator_index -2)..operator_index] = RPNCalculator.compute(stack)
stack = []
if commands.length > 1
RPNCalculator.value(commands, stack)
else
commands[-1]
end
end
def value
RPNCalculator.value(@commands, @stack)
end
end
# # Topics
# * arrays
# * arithmetic
# * strings
#
# # RPN Calculator
#
# "RPN" stands for "Reverse Polish Notation". (See [the wikipedia entry](http://en.wikipedia.org/wiki/Reverse_Polish_notation) for more information on this colorful term.) Briefly, in an RPN world, instead of using normal "infix" notation, e.g.
#
# 2 + 2
#
# you use "postfix" notation, e.g.
#
# 2 2 +
#
# While this may seem bizarre, there are some advantages to doing things this way. For one, you never need to use parentheses, since there is never any ambiguity as to what order to perform operations in. The rule is, you always go from the back, or the left side.
#
# 1 + 2 * 3 =>
# (1 + 2) * 3 or
# 1 + (2 * 3)
#
# 1 2 + 3 * => (1 + 2) * 3
# 1 2 3 * + => 1 + (2 * 3)
#
# Another advantage is that you can represent any mathematical formula using a simple and elegant data structure, called a [stack](http://en.wikipedia.org/wiki/Stack_(data_structure)).
#
# # Hints
#
# Ruby doesn't have a built-in stack, but the standard Array has all the methods you need to emulate one (namely, `push` and `pop`, and optionally `size`).
#
# See
# * <http://en.wikipedia.org/wiki/Reverse_Polish_notation>
# * <http://www.calculator.org/rpn.aspx>
#
require "calc1"
describe RPNCalculator do
attr_accessor :calculator
before do
@calculator = RPNCalculator.new
end
it "adds two numbers" do
calculator.push(2)
calculator.push(3)
calculator.plus
calculator.value.should == 5
end
it "adds three numbers" do
calculator.push(2)
calculator.push(3)
calculator.push(4)
calculator.plus
calculator.value.should == 7
calculator.plus
calculator.value.should == 9
end
it "subtracts the second number from the first number" do
calculator.push(2)
calculator.push(3)
calculator.minus
calculator.value.should == -1
end
it "adds and subtracts" do
calculator.push(2)
calculator.push(3)
calculator.push(4)
calculator.minus
calculator.value.should == -1
calculator.plus
calculator.value.should == 1
end
it "multiplies and divides" do
calculator.push(2)
calculator.push(3)
calculator.push(4)
calculator.divide
calculator.value.should == (3.0 / 4.0)
calculator.times
calculator.value.should == 2.0 * (3.0 / 4.0)
end
it "resolves operator precedence unambiguously" do
# 1 2 + 3 * => (1 + 2) * 3
calculator.push(1)
calculator.push(2)
calculator.plus
calculator.push(3)
calculator.times
calculator.value.should == (1+2)*3
# 1 2 3 * + => 1 + (2 * 3)
calculator.push(1)
calculator.push(2)
calculator.push(3)
calculator.times
calculator.plus
calculator.value.should == 1+(2*3)
end
it "fails informatively when there's not enough values stacked away" do
expect {
calculator.plus
}.to raise_error("calculator is empty")
expect {
calculator.minus
}.to raise_error("calculator is empty")
expect {
calculator.times
}.to raise_error("calculator is empty")
expect {
calculator.divide
}.to raise_error("calculator is empty")
end
# extra credit
it "tokenizes a string" do
calculator.tokens("1 2 3 * + 4 5 - /").should ==
[1, 2, 3, :*, :+, 4, 5, :-, :/]
end
# extra credit
it "evaluates a string" do
calculator.evaluate("1 2 3 * +").should ==
((2 * 3) + 1)
calculator.evaluate("4 5 -").should ==
(4 - 5)
calculator.evaluate("2 3 /").should ==
(2.0 / 3.0)
calculator.evaluate("1 2 3 * + 4 5 - /").should ==
(1.0 + (2 * 3)) / (4 - 5)
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment