Mathematical expression evaluator and equation solver

Question

I'm trying to implement a mathematical expression evaluator and equation solver, and based on extensive online research and my own experimentation have come to the conclusion that the best way of writing one is by first parsing the expression and breaking it down and then feeding it into an evaluator/parser.

Note I want to make this language independent, from C to Ruby (which I've chosen).

I'm looking to know if my methodology in general and my specific implementation of my methodology are:

• An efficient way of tackling this problem
• Make it easy to add more features(such as multivariable equations, functions like cos and log, and bitwise math).
• If there is any way to make them more generalized in their applications(to parse more than mathematical expressions)

Also, my implementation is recursive. Is there a problem with this?

My methodology for parsing the expression is as follows:

1. Run the scopify method which is aware of the various associativity of the operators and inserts parenthesis as necessary to break down the scope.

   For instance, scopify "1+2*3" => "1+(2*3)".

2. Break down scopified expression into a tree, which makes it easy to run any type of analysis it.

   break "1+(2*3)" => [1, +, [2, *, 3]]

3. Feed it into the solver/evaluator(which I haven't implemented.

Helpers

    class String
        def integer?
            [                          # In descending order of likeliness:
                /^[-+]?[1-9]([0-9]*)?$/, # decimal
                /^0[0-7]+$/,             # octal
                /^0x[0-9A-Fa-f]+$/,      # hexadecimal
                /^0b[01]+$/              # binary
            ].each do |match_pattern|
                return true if self =~ match_pattern
            end
            return false
        end

        def float?
            pat = /^[-+]?[1-9]([0-9]*)?\.[0-9]+$/
            return true if self=~pat 
            false 
        end

        def to_n
            return self.to_f if self.float?

            return self.to_i if self.integer? 
        end
    end


    @operators = {
        :+ => lambda { |a,b| a+b },
        :- => lambda { |a,b| a-b},
        :* => lambda { |a,b| a*b},
        :/ => lambda { |a,b| a/b},
        :^ => lambda { |a,b| a**b},

    }


    @d = 0
    @error = false
    #manipulate an array by reference

Scopify

    def scopify expr
        last_empty = 0
        i          = 0
        pA         = 0
        scope      = 0
        numPow     = 0
        until i == expr.length-1
            to_incr =1
            # puts "#{expr} :#{expr[i]}"
            case expr[i]
            when /[\+\-]/
                if numPow>0
                    expr.insert i, ")"*numPow
                    numPow=0
                    to_incr+=numPow+1
                end
                if i-last_empty >1
                expr.insert last_empty, "("
                expr.insert i+1, ")"
                to_incr+=2
                end
                last_empty=i+to_incr
            when /\^/
                numPow+=1
                expr.insert i+1, "("
                to_incr+=1
            when '('
                last_empty=i+1 if expr[i+1] !='('
            when ')'
                last_empty=i+1 if expr[i+1].match /[0-9\+\-]/
            else
            end

            i+=to_incr
        end
        i=expr.length

        unless expr[last_empty] == "(" || expr[last_empty..i].integer? || last_empty==0
            expr.insert last_empty, "("
            expr.insert expr.length, ")"
        end

        if numPow>0
            expr.insert i, ")"*numPow
            numPow=0
        end
        expr
    end

Break into Tree

    def calc_expr expr, array
        until @d == expr.length
            c = expr[@d]
            case c
            when "("
                @d += 1
                array.push calc_expr(expr, Array.new)
            when ")"
                @d += 1
                return array
            when /[\*\/]/
                @d +=1
                array.push c.to_sym
            when /[\+\-\^]/
                @d+=1
                array.push c.to_sym
            when /\./
                if expr[@d-1]=~/[0-9]+/
                    x = array.pop.to_s + c + expr[@d+1]
                    array.push x.to_n
                end
                @d+=2
            when /[0-9x]/
                if expr[@d-1]=~/[0-9\.x]/ && array.count>0
                    x = array.pop.to_s + c 
                    array.push x.to_n
                else array.push c.to_n
                end
                @d+=1
            else
                unless @error
                    @error = true
                    puts "Problem evaluating expression at index:#{@d}"
                    puts "Char '#{expr[@d]}' not recognized"
                end
                return
            end
        end

        return array
    end

Answer 1

Software that takes an arbitrary string of characters as input and transforms it into an executable form has a long history within computing. Much of that history is directly related to the design of compilers and interpreters. Over the years, computer scientists have developed a number of techniques based on the mathematics of computation.

Grammar

One useful technique when defining a computational language is to write a formal grammar. This helps insure that the rules are consistent with themselves and complete. Fortunately, there are tools for this in many languages. For example, Treetop in Ruby. The example code for the grammar Arithmetic illustrates some of the advantages of using a domain specific language and a formal grammar definition.

Example Grammar

Snippet from the Treetop example code.

 rule additive_op
   '+' {
     def apply(a, b)
       a + b
     end
   }
 /
  '-' {
    def apply(a, b)
     a - b
    end
   }
end

rule number
  ([1-9] [0-9]* / '0') {
    def eval(env={})
      text_value.to_i
    end
  }
end

rule space
 ' '*
end

Grammar Advantage

Using a formal grammar is consistent with the bulleted goals in the question.

• Once over the initial learning curve, writing a new language using the tool will tend to be more efficient than writing it without such a tool.

• The domain specific language makes the code easier to read; rule is more descriptive than when and grammar Arithmetic is clearer than def scopify expr when communicating with other programmers.

• There is extensive research into formal grammars and a significant number of accessible resources and learning materials exist to support this approach. For example StackOverflow is a resource for Treetop.

• Being underpinned by computational science increases the odds that any particular implementation will approach correctness and completeness. The methods of computer science make covering corner cases more likely.

To put this in perspective, a formal grammar facilitates overloading a token. For example, a calculation engine may want to use the token - as both a binary operator for subtraction 3 - 4 and a unitary operator when representing the results of the subtraction as -1. Tools for defining grammars make this an easily solved problem.

Caveat

Obviously learning any class of new tool comes with a learning curve and that learning curve is not just about the mechanics of the tool itself but also about the entire class of problems the tool addresses. Writing grammars is non-trivial. Then again so is seriously writing a calculation engine for general applicability over the long term.