Ruby arithmetic evaluator

arithmetic_evaluator.rb

# Copyright (c) 2012 Chris Parker <mrcsparker@gmail.com>
#
# Permission is hereby granted, free of charge, to any person obtaining a 
# copy of this software and associated documentation files (the "Software"), 
# to deal in the Software without restriction, including without limitation 
# the rights to use, copy, modify, merge, publish, distribute, sublicense, 
# and/or sell copies of the Software, and to permit persons to whom the Software is 
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in all 
# copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 
# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 
# IN THE SOFTWARE.

class ArithmeticEvaluator

  def is_numeric?(num)
    true if Float(num) rescue false;
  end

  def is_operator?(op)
    [ '+', '-', '*', '/' ].include? op
  end

  def tokenize(expr)

    expr = expr.gsub(" ", "")
    expr = expr.gsub("x", "*")

    stack = []
    number = []

    0.upto(expr.size - 1) do |i|
      c = expr[i].chr

      if is_numeric?(c) || c == '.'
        number << c
      else
        stack.push(number.join) unless number.empty?
        number = []
        stack << c
      end
    end

    stack.push(number.join) unless number.empty?

    stack
  end

  def order
    { 
      "*" => 2,
      "/" => 2,
      "+" => 1,
      "-" => 1 
    }
  end

  def to_postfix(m)
    tokens = tokenize(m)

    output = []
    stack = []

    tokens.each do |token|
      if is_numeric?(token)
        output.push(token)
      elsif is_operator?(token)
        # Token is an operator.
        # We will pop the operators of equal or higher presedence off of the
        # stack and append them
        while (!stack.empty? and is_operator?(stack.last))
          if (order[token] <= order[stack.last])
            output.push(stack.pop)
            next
          end
          break
        end
        # Push the new operator on the stack
        stack.push(token)
      elsif token == "("
        stack.push(token)
      elsif token == ")"
        while !stack.empty? and stack.last != "("
          output.push(stack.pop)
        end
        stack.pop # Pop the left parens
      end
    end

    # Pop the remaining operators off of the stack
    while !stack.empty?
      output.push(stack.pop)
    end

    output
  end

  def evaluate(expr)
    expr_list = to_postfix(expr)
    stack = []

    expr_list.each do |e|

      if is_operator?(e)
        second = Float(stack.pop)
        first = Float(stack.pop)

        if e == '*'
          stack.push(first * second)
        elsif e == '-'
          stack.push(first - second)
        elsif e == '+'
          stack.push(first + second)
        elsif e == '/'
          stack.push(first / second)
        end
      else
        stack.push(e)
      end
    end

    stack.first

  end

end

m = "3 - 2 + 7 + 1"
a = ArithmeticEvaluator.new
puts a.evaluate(m)