calculator.rb

#!/usr/bin/env ruby

# Task:  Fill in the lines commented 'HERE' to create a working calculator.
# Check: Check your work by executing the file after filling in the lines.

class Lexer
  def initialize(input)
    @input = input.gsub(/\s/, '')
    @tokens = []
  end

  def tokenize
    index = 0

    loop do
      break if index >= @input.size

      case @input[index]
      when '('
        @tokens << [:LPAREN, '(']
        index += 1
      when ')'
        @tokens << [:RPAREN, ')']
        index += 1
      when '+'
        @tokens << [:PLUS, '+']
        index += 1
      when '-'
        @tokens << [:MINUS, '-']
        index += 1
      when '*'
        @tokens << [:TIMES, '*']
        index += 1
      when '/'
        @tokens << [:DIV, '/']
        index += 1
      else
        number = @input.match(/([-+]?\d*\.?\d+)(?:[eE]([-+]?\d+))?/, index)

        if number
          value = Regexp.last_match[0]

          @tokens << [:NUMBER, value.to_f]
          index += value.length
        else
          fail "Unknown token: #{@input[index..-1]}"
        end
      end
    end

    @tokens << [:EOF, '']
    @tokens
  end
end

class Parser
  def initialize(input)
    @tokens = Lexer.new(input).tokenize
  end

  def parse
    inner = addsub
    expect(:EOF)

    inner
  end

  private

  #
  # Recursive descent
  #

  # Addition and subtraction
  def addsub
    left = muldiv

    if accept(:PLUS)
      AddNode.new(left, addsub)
    elsif accept(:MINUS)
      SubNode.new(left, addsub)
    else
      left
    end
  end

  # Multiplication and division
  def muldiv
    left = negpos

    if accept(:TIMES)
      MulNode.new(left, muldiv)
    elsif accept(:DIV)
      DivNode.new(left, muldiv)
    else
      left
    end
  end

  # Negation and position
  def negpos
    if accept(:MINUS)
      NegNode.new(negpos)
    elsif accept(:PLUS)
      group
    else
      group
    end
  end

  # Parenthetical expressions
  def group
    if accept(:LPAREN)
      inner = addsub
      expect(:RPAREN)

      inner
    else
      number
    end
  end

  # Numbers
  def number
    value = expect(:NUMBER)
    NumberNode.new(value[1])
  end

  #
  # Token processing helpers
  #

  def accept(type)
    @tokens.shift if @tokens.first[0] == type
  end

  def expect(type)
    accept(type) || fail("Expected token :#{type}")
  end

  #
  # AST Nodes
  #

  class NumberNode
    attr_accessor :value

    def initialize(value)
      @value = value.to_f
    end

    def perform
      @value
    end
  end

  class BinaryNode
    attr_accessor :left, :right

    def initialize(left, right)
      @left  = left
      @right = right
    end
  end

  class UnaryNode
    attr_accessor :child

    def initialize(child)
      @child = child
    end
  end

  class AddNode < BinaryNode
    def perform
      # HERE
    end
  end

  class SubNode < BinaryNode
    def perform
      # HERE
    end
  end

  class MulNode < BinaryNode
    def perform
      # HERE
    end
  end

  class DivNode < BinaryNode
    def perform
      # HERE
    end
  end

  class NegNode < UnaryNode
    def perform
      # HERE
    end
  end
end

class Calculator
  def self.evaluate(expression)
    Parser.new(expression).parse.perform
  end

  def self.test
    test_expr "42"
    test_expr "-42"
    test_expr "2 + 2"
    test_expr "3 - 7"
    test_expr "4 * 4"
    test_expr "2 / 3"
    test_expr "2 + 3 * 5"
    test_expr "2 * 3 + 5"
    test_expr "(2 + 3) * 5"
  end

  def self.test_expr(expr)
    puts "#{expr} == #{evaluate(expr)}"
  end
end

Calculator.test