Toy RPN Expression Evaluator

rpn.rb

require "forwardable"

class Operator
  # TODO: probably raise if stuff isn't implemented
  # TODO: probable register implementations
end

class Operand
  # TODO: probably raise if stuff isn't implemented
  # TODO: probable register implementations
end

class Constant < Operand
  def initialize(value)
    @value = value.to_i
  end

  def evaluate(*)
    self
  end

  def execute(*)
    value
  end

  def format
    value.to_s
  end

  private
  attr_reader :value
end

class Lookup < Operand
  attr_reader :key

  def initialize(key)
    @key = key
  end

  def evaluate(context)
    Evaluated.new(self, context.fetch(key.to_sym))
  end

  class Evaluated
    def initialize(lookup, value)
      @lookup = lookup
      @value = value
    end

    def execute
      value
    end

    def format
      "(#{lookup.key}: #{value})"
    end

    attr_reader :lookup, :value
  end
end

class Addition < Operator
  def perform(left, right)
    left + right
  end

  def format
    "+"
  end
end

class Multiplication < Operator
  def perform(left, right)
    left * right
  end

  def format
    "*"
  end
end

# NOTE: Represents the structure of an expression
class Expression
  attr_reader :operator, :left, :right

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

  def evaluate(context)
    # NOTE: evaluating everything in the same place makes debugging a bit easier
    Evaluated.new(
      expression: self,
      left_value: left.evaluate(context),
      right_value: right.evaluate(context),
    )
  end

  # NOTE: Represents the evaluated structure ready to be inspected prior to execution (e.g pretty printing)
  class Evaluated
    attr_reader :expression, :left_value, :right_value
    extend Forwardable # sigh, use delegate when ActiveSupport present
    def_delegators :@expression, :operator, :left, :right

    def initialize(expression:, left_value:, right_value:)
      @expression = expression
      @left_value = left_value
      @right_value = right_value
    end

    def execute
      # NOTE: Could log here:
      puts "executing #{operator} on #{left_value} and #{right_value}"
      operator.perform(left_value.execute, right_value.execute)
    end

    def format
      "(#{left_value.format} #{operator.format} #{right_value.format})"
    end
  end
end

### RPN Calc

class RPNCalculation
  def initialize
    @stack = []
  end

  def push(token)
    if token.is_a?(Operand)
      stack.push(token)
    else
      left = stack.pop
      right = stack.pop
      stack.push(Expression.new(operator: token, left: left, right: right))
    end
  end

  def expression
    raise "bad expression" if stack.length != 1
    stack.first
  end

  private

  attr_reader :stack
end

### Expression Parsing

class ExpressionParser
  def parse(lines)
    lines.each_with_object(RPNCalculation.new) do |line, rpn|
      token = token_parser.make(line)
      rpn.push(token)
    end.expression
  end

  def token_parser
    @token_parser ||= TokenParser.new
  end

  # NOTE: Allow the complexity of parsing tokens and constructing tokens to grow independently of their usage
  class TokenParser
    # TODO: could probably get rid of these lists by having operator and operand classes register themselves and their "command"
    OPERATORS = {
      :add => Addition,
      :mul => Multiplication,
    }

    OPERANDS = {
      :const => Constant,
      :lookup => Lookup,
    }

    def operand?(kind)
      OPERANDS.key?(kind.to_sym)
    end

    def operator?(kind)
      OPERATORS.key?(kind.to_sym)
    end

    def make(line)
      kind, *args = *line.split(" ")
      kind = kind.to_sym
      if operand?(kind)
        make_operand(OPERANDS.fetch(kind), args)
      elsif operator?(kind)
        make_operator(OPERATORS.fetch(kind), args)
      else
        raise "idk what #{kind} is"
      end
    end

    def make_operand(operand_class, args)
      operand_class.new(args[0])
    end

    def make_operator(operator_class, _args)
      operator_class.new
    end
  end
end

# Poor mans tests

lines = [
  'const 4',
  'const 2',
  'lookup a',
  'add',
  'mul',
]
expression = ExpressionParser.new.parse(lines)
# NOTE: notice execution is delayed even after evaluation
evaluated_expression = expression.evaluate({ :a => 10 })
puts evaluated_expression.execute # => 48
puts evaluated_expression.format # => (((a: 10) + 2) * 4)