2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ The first thing you need to do is decide the characteristics of the equations you wish to solve, and make sure there are algorithms that could be used or devised to solve those equations. Considering that many esteemed mathematicians have worked for years trying to solve certain equations, and have come up empty, it's pie-in-the-sky to think that you could write a general equation-solver. It's a waste of time to develop a front-end and then only later tackle the hard part. \$\endgroup\$ – Cary Swoveland Jan 30 '15 at 4:50
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Are formal grammars written in formal grammars? \$\endgroup\$ – theideasmith Jan 27 '15 at 20:43
  • \$\begingroup\$ @theideasmith It is probably a better abstraction to imagine the tooling implemented at a lower layer and eventually, of course, it has to be. \$\endgroup\$ – ben rudgers Jan 27 '15 at 21:35
  • \$\begingroup\$ Would people consider using a formal grammar as opposed to implementing one's own parser cheating in a way? \$\endgroup\$ – theideasmith Jan 27 '15 at 23:08
  • \$\begingroup\$ @theideasmith Obviously, it is ethically questionable for a person to claim to have done something they did not do. The ethical liability varies with context and with the degree to which the claim stretches important facts. In an academic context, claiming to have done something without some specific tool on an assignment for grade where the tool's use is prohibited is clearly cheating. However, people who work on designing computer languages use tools for creating languages. Tools like lex and yacc and make have been around for forty years. \$\endgroup\$ – ben rudgers Jan 28 '15 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.