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

• Cary Swoveland: 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.

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.

• theideasmith: Are formal grammars written in formal grammars?
• ben rudgers: @theideasmith It is probably a better abstraction to imagine the tooling implemented at a lower layer and eventually, of course, it has to be.
• theideasmith: Would people consider using a formal grammar as opposed to implementing one's own parser cheating in a way?
• ben rudgers: @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.