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.


    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
            return false

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

        def to_n
            return self.to_f if self.float?

            return self.to_i if self.integer? 

    @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


    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
                if i-last_empty >1
                expr.insert last_empty, "("
                expr.insert i+1, ")"
            when /\^/
                expr.insert i+1, "("
            when '('
                last_empty=i+1 if expr[i+1] !='('
            when ')'
                last_empty=i+1 if expr[i+1].match /[0-9\+\-]/


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

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

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 /[\+\-\^]/
                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
            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
                unless @error
                    @error = true
                    puts "Problem evaluating expression at index:#{@d}"
                    puts "Char '#{expr[@d]}' not recognized"

        return array
  • \$\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\$ Jan 30, 2015 at 4:50

1 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.


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
  '-' {
    def apply(a, b)
     a - b

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

rule space
 ' '*

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.


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.

  • \$\begingroup\$ Are formal grammars written in formal grammars? \$\endgroup\$ Jan 27, 2015 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\$ Jan 27, 2015 at 21:35
  • \$\begingroup\$ Would people consider using a formal grammar as opposed to implementing one's own parser cheating in a way? \$\endgroup\$ Jan 27, 2015 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\$ Jan 28, 2015 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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