simple_interactive_interpreter.rb

# A simple Ruby interpreter designed to evaluate mathematical expressions.
#
# USAGE:
# interpreter = Interpreter.new
# interpreter.input('1 + 1') => 2
# interpreter.input('2 - 1') => 1
# interpreter.input('2 * 3') => 6
# interpreter.input('8 / 4') => 2
# interpreter.input('7 % 4') => 3
# interpreter.input('x = 1') => 1
# interpreter.input('x') => 1
# interpreter.input('x + 3') => 4
# interpreter.input('4 + 2 * 3') => 10
# interpreter.input('4 / 2 * 3') => 6
# interpreter.input('7 % 2 * 8') => 8
# interpreter.input('(4 + 2) * 3') => 18
# interpreter.input('(7 + 3) / (2 * 2 + 1)') => 2
# interpreter.input('(8 - (4 + 2) * 3)') => -10
# interpreter.input('(10 / (8 - (4 + 2))) * 3') => 15

class Interpreter
  OPERATORS  = [:*, :/, :%, :+, :-]
  PRECEDENCE = { :'(' => 0, :')' => 0, :'=' => 1, :+ => 2, :- => 2, :* => 3, :/ => 4, :% => 5 }

  def initialize
    @tokens = []
    @functions = {}
    @vars = {}

    OPERATORS.inject({}) do |_, operator|
      @functions[operator] = lambda { |*args| args.reduce(&operator) }
    end
  end  

  def input(expr)
    @tokens = tokenize(expr).map{ |a| a[0] }
    eval(parse(lex(@tokens)))
  end

  private

  def eval(exp)
    if !exp
      ""
    elsif exp.is_a? Numeric
      exp
    elsif @functions.has_key?(exp)
      @functions[exp]
    elsif @vars.has_key?(exp)
      @vars[exp]
    elsif exp =~ /^[A-Za-z_]$/
      raise "ERROR: Invalid identifier. No variable with name \'#{exp}\' was found."
    elsif exp[0] == :'='
      _, var, e = exp
      @vars[var] = eval(e)
    else
      func = eval(exp[0])
      args = exp[1..-1].map{ |arg| eval(arg) }
      func.call(*args)
    end
  end

  def parse(tokens)
    stack, prefix = [], []

    tokens.reverse.each do |token|
      if token == :')'
        stack << token
      elsif token == :'('
        top = stack.pop
        while top != :')'
          prefix.unshift(top)
          top = stack.pop
        end
      elsif PRECEDENCE.has_key?(token)
        while !stack.empty? && PRECEDENCE[stack.last] >= PRECEDENCE[token]
          prefix.unshift(stack.pop)
        end
        stack.push(token)
      else
        prefix.unshift(token)
      end
    end

    while !stack.empty?
      prefix.unshift(stack.pop)
    end

    while !prefix.empty?
      token = prefix.pop
      if !PRECEDENCE.has_key?(token)
        stack << token
      else
        exp = [token]
        exp << stack.pop unless stack.empty?
        exp << stack.pop unless stack.empty?
        stack.push(exp)
      end
    end

    stack.pop
  end

  def lex(tokens)
    tokens.map do |token|
      if token =~ /^\d+$/
        token.to_i
      else
        token.to_sym
      end
    end
  end

  def tokenize program
    return [] if program == ''
    regex = /\s*([-+*\/\%=\(\)]|[A-Za-z_][A-Za-z0-9_]*|[0-9]*\.?[0-9]+)\s*/
    "(#{program})".scan(regex).select { |s| !(s =~ /^\s*$/) }
  end
end