Skip to content

Instantly share code, notes, and snippets.

@wolflee

wolflee/Rakefile

Created July 21, 2014 09:54
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save wolflee/ba741cb5ba60e2a68bec to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save wolflee/ba741cb5ba60e2a68bec to your computer and use it in GitHub Desktop.
Download ZIP
Arithmometer
Raw
calculator.rb
$:.unshift(File.dirname(__FILE__))
require 'calculator/stack'
require 'calculator/lexer'
require 'calculator/rpn'
require 'calculator/rpn_calculator'
class Calculator
def initialize(expression)
@expression = expression
end
def run
tokens = Lexer.lex(@expression)
rpn = RPN.new(tokens).build
RPNCalculator.calculate(rpn)
end
end
Raw
calculator_lexer_spec.rb
require_relative 'spec_helper'
describe Calculator::Lexer do
it ".lex tokenizes an expression" do
code = "( 2 + ( ( 4 + 6 ) * sqrt(5)) / 2 )"
assert_equal Calculator::Lexer.lex(code),
[[:lparen, "("],
[:sp, " "],
[:int, "2"],
[:sp, " "],
[:op, "+"],
[:sp, " "],
[:lparen, "("],
[:sp, " "],
[:lparen, "("],
[:sp, " "],
[:int, "4"],
[:sp, " "],
[:op, "+"],
[:sp, " "],
[:int, "6"],
[:sp, " "],
[:rparen, ")"],
[:sp, " "],
[:op, "*"],
[:sp, " "],
[:sqrt, "sqrt"],
[:lparen, "("],
[:int, "5"],
[:rparen, ")"],
[:rparen, ")"],
[:sp, " "],
[:op, "/"],
[:sp, " "],
[:int, "2"],
[:sp, " "],
[:rparen, ")"]]
end
it ".next_token knows '('" do
code = "("
input = ::StringScanner.new(code)
assert_equal Calculator::Lexer.next_token(input), [:lparen, "("]
end
it ".next_token knows ')'" do
code = ")"
input = ::StringScanner.new(code)
assert_equal Calculator::Lexer.next_token(input), [:rparen, ")"]
end
it ".next_token knows space" do
code = " ( 2 + 2 )"
input = ::StringScanner.new(code)
assert_equal Calculator::Lexer.next_token(input), [:sp, " "]
end
it ".next_token knows numbers" do
code = "14 *3 "
input = ::StringScanner.new(code)
assert_equal Calculator::Lexer.next_token(input), [:int, "14"]
end
it ".next_token knows operators" do
code = "+-*/"
input = ::StringScanner.new(code)
assert_equal Calculator::Lexer.next_token(input), [:op, "+"]
assert_equal Calculator::Lexer.next_token(input), [:op, "-"]
assert_equal Calculator::Lexer.next_token(input), [:op, "*"]
assert_equal Calculator::Lexer.next_token(input), [:op, "/"]
end
it ".next_token knows sqrt" do
code = "sqrt(5)"
input = ::StringScanner.new(code)
assert_equal Calculator::Lexer.next_token(input), [:sqrt, "sqrt"]
end
it "figures out unknown token" do
code = "unknown"
input = ::StringScanner.new(code)
assert_equal Calculator::Lexer.next_token(input), [:unknown, ""]
end
it "figures out end of input" do
code = ""
input = ::StringScanner.new(code)
assert_nil Calculator::Lexer.next_token(input)
end
end
Raw
calculator_rpn_calculator_spec.rb
require_relative 'spec_helper'
describe Calculator::RPNCalculator do
it "#calculate" do
rpn = %w(1 2 * 3 + 4 sqrt 2 / 5 - +)
assert_equal 1,
Calculator::RPNCalculator.calculate(rpn)
end
end
Raw
calculator_rpn_spec.rb
require_relative 'spec_helper'
describe Calculator::RPN do
it "#build an expression from tokens" do
tokens = [[:int, "1"],
[:op, "+"],
[:sp, " "],
[:int, "2"]]
assert_equal %w(1 2 +),
Calculator::RPN.new(tokens).build
end
it "#build an expression from tokens with sqrt" do
tokens = [[:int, "1"],
[:op, "+"],
[:sqrt, "sqrt"],
[:lparen, "("],
[:int, "5"],
[:rparen, ")"]]
assert_equal %w(1 5 sqrt +),
Calculator::RPN.new(tokens).build
end
it "#build correct sequence" do
tokens = [[:int, "1"],
[:op, "*"],
[:int, "2"],
[:op, "+"],
[:int, "3"],
[:op, "-"],
[:int, "4"],
[:op, "/"],
[:int, "2"]]
assert_equal %w(1 2 * 3 + 4 2 / -),
Calculator::RPN.new(tokens).build
end
it "#build elimantes ()" do
tokens = [[:int, "9"],
[:op, "+"],
[:lparen, "("],
[:int, "1"],
[:op, "+"],
[:lparen, "("],
[:int, "2"],
[:op, "*"],
[:int, "3"],
[:rparen, ")"],
[:rparen, ")"],
[:op, "/"],
[:lparen, "("],
[:int, "4"],
[:op, "-"],
[:int, "5"],
[:rparen, ")"]]
assert_equal %w(9 1 2 3 * + 4 5 - / +),
Calculator::RPN.new(tokens).build
end
end
Raw
calculator_spec.rb
require_relative 'spec_helper'
describe Calculator do
it "#run" do
expr = ' ( 2 + ( ( 4 + 6 ) * (9 * 2) - ( 5 - 1)))'
c = Calculator.new(expr)
assert_equal eval(expr), c.run
end
it "evaluates sqrt correctly" do
expr = '( 2 + ( ( 4 + 6 ) * sqrt(5)) / 2 )'
c = Calculator.new(expr)
assert_equal eval(expr.gsub(/sqrt/, "Math.sqrt")), c.run
end
end
Raw
calculator_stack_spec.rb
require_relative 'spec_helper'
describe "Calculator" do
describe "Stack" do
it "#pops" do
s = Calculator::Stack.new()
s.push "answer"
s.push 42
assert_equal 42, s.pop
end
it "#pops nil when empty" do
s = Calculator::Stack.new()
assert_nil s.pop
end
it "#top" do
s = Calculator::Stack.new()
s.push "object"
assert_equal "object", s.top
refute_empty s
end
it "#top is nil when empty" do
s = Calculator::Stack.new()
assert_nil s.top
end
it "#empty?" do
s = Calculator::Stack.new()
s.push ("item")
s.pop
assert_empty s
end
end
end
Raw
lexer.rb
require 'strscan'
class Calculator
class Lexer
def self.lex(code)
input = ::StringScanner.new(code)
output = []
while token = self.next_token(input)
output << token
end
output
end
def self.next_token(input)
if input.scan(/\d+/)
[:int, input.matched.downcase]
elsif input.scan(/\(/)
[:lparen, input.matched.downcase]
elsif input.scan(/\)/)
[:rparen, input.matched.downcase]
elsif input.scan(/[\+\-\*\/]/)
[:op, input.matched.downcase]
elsif input.scan(/sqrt/)
[:sqrt, input.matched.downcase]
elsif input.scan(/\s+/)
[:sp, input.matched.downcase]
elsif input.eos?
nil
else
[:unknown, ""]
end
end
end
end
Raw
Rakefile
task :test do
$:.unshift('lib', 'spec')
Dir.glob('./spec/**/*_spec.rb') { |f| require f }
Dir.glob('./lib/**/*.rb') { |f| require f }
end
Raw
rpn.rb
class Calculator
class RPN
def initialize(tokens)
@tokens = tokens
end
def build
result = []
s = Stack.new
@tokens.each do |token|
case token[0]
when :int
result << token[1]
when :lparen
s.push token[1]
when :rparen
begin
top = s.pop
if top == '('
break
else
result << top
end
end while true
result << s.pop if s.top == "sqrt"
when :sqrt
s.push(token[1]) if token[1] == "sqrt"
when :op
begin
if s.empty? || s.top == '(' || prior?(token[1], s.top)
s.push(token[1])
break
else
result << s.pop
end
end while true
end
end
until s.empty?
result << s.pop
end
result
end
private
def priority(op)
case op
when "+", "-"
1
when "*", "/"
2
when "(", ")"
3
end
end
def prior?(op1, op2)
priority(op1) > priority(op2)
end
end
end
Raw
rpn_calculator.rb
class Calculator
class RPNCalculator
def self.calculate(expression)
operand_stack = Stack.new
expression.each do |i|
case i
when /[0-9]+/
operand_stack.push(i.to_i)
when "sqrt"
operand_stack.push(Math.sqrt(operand_stack.pop))
when "+"
operand_stack.push(operand_stack.pop + operand_stack.pop)
when "-"
subtractor = operand_stack.pop
operand_stack.push(operand_stack.pop - subtractor)
when "*"
operand_stack.push(operand_stack.pop * operand_stack.pop)
when "/"
divisor = operand_stack.pop
operand_stack.push(operand_stack.pop / divisor)
end
end
operand_stack.pop
end
end
end
Raw
spec_helper.rb
$:.unshift(File.dirname(__FILE__))
require 'minitest/autorun'
Dir.glob('./lib/**/*.rb') { |f| require f }
if __FILE__ == $0
$:.unshift('lib', 'spec')
Dir.glob('./spec/**/*_spec.rb') { |f| require f }
end
Raw
stack.rb
class Calculator
class Stack
def initialize
@stack = []
end
def push(item)
@stack << item
end
def pop
@stack.slice!(-1)
end
def top
@stack[-1]
end
def empty?
@stack.empty?
end
end
end
@wolflee
Copy link
Author

wolflee commented Jul 21, 2014

directory structure

.
├── Rakefile
├── lib
│   ├── calculator
│   │   ├── lexer.rb
│   │   ├── rpn.rb
│   │   ├── rpn_calculator.rb
│   │   └── stack.rb
│   └── calculator.rb
└── spec
    ├── calculator_lexer_spec.rb
    ├── calculator_rpn_calculator_spec.rb
    ├── calculator_rpn_spec.rb
    ├── calculator_spec.rb
    ├── calculator_stack_spec.rb
    └── spec_helper.rb

rake test

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