MExpr

”Category”: math library
”Release: 05/2012
”Technologies”: C++, Bison, Lex
”Platforms”: Linux, Mac OS X
”Download: Github
 

Library that parses mathematical expressions with implicit multiplications.

The library uses bison and flex to parse a string that represents a mathematical expression. The parser was made to manage complex expressions like this:

2 + 2yx^2 - 3(_sum(1,2) + _sum(1,2,3))(-5x)

Implicit multiplications

If you write xy, the parser understands that you want to multiply two variables: x and y. But this is not the only case where you can have an implicit multiplication, there are some other examples:

-3xy^2
(3+3)(5-3)
-(3-2)

But for this reason, you can’t use variables that have more than a single character. Infact, if you write xy, the parser can’t distinguish between the variable xy and the multiplication x * y.

Functions

Another problems, is that if you write f(x) the parser can’t distinguish between the function f called with the x argument and the variable f that multiplies the (x) expression. For this reason, the functions always start with the _ character. Now, _f(x) calls the f function and f(x) is a multiplication between the f and x variables.

The function can have more than one argument. For example, you can define the function _sum(a,b) that adds two numbers. Furthermore, you can define _sum(a,b,c) too, that adds three numbers. In fact, the parser can manage overloaded functions distinguishing the functions by the number of arguments.

Environment

The parser has a dynamic environment, that maintains all the value associated to a variable symbol. Moreover, for each function symbol, it maintains a pointer to the associated function. Also, you can redefine a defined function, or change the value of a defined variable (especially if you’re drawing a plot).

STDFunctions

The library has a set of standard functions that you can use in your expressions. This functions are the same of the math.h standard library.

For example:

_sqrt(_floor(_exp(5)))

uses the math.h functions: sqrt, floor and exp.

The standard constants (like pi and e) will be introduced with the multiple-character variables.

How it works

The library parses the input string and then it builds an AST Tree. For example, with the expression -3xy^2, the parser builds this tree:

[ * ]─[ -1 ]
  └───[ * ]─[ 3 ]
        └───[ * ]─[ x ]
              └───[ ^ ]─[ y ]
                    └───[ 2 ]

Now, the library can evaluate the expression using the tree (this is done browsing recursively this tree).

In some cases, for example when you want to draw a plot, you need to evaluate the same expression changing only the value of a variable. For this reason, the library can “compiles” the AST Tree to have a more efficient representation of the expression. The generated code is a simple bytecode, that uses a stack to compute operations (similarly to the Java bytecode).

This is the representation of the bytecode generated using the previous expression:

VAL: -1
VAL: 3
VAR: x
VAR: y
VAL: 2
POW
MUL
MUL
MUL

Functions and variables

The Environment has two maps: one for the variables and one for the functions. After that the expression is parsed, the AST Tree (and the code too) contains the name of the variables (or the name of the functions) and not their values. On the contrary, in the evaluation phase the environment is questioned to get the values and the function pointers.

To distinguish the functions with the same name, but different number of arguments, the environment uses different names. For example, the function _foo with one argument is internally called _foo_1, the other function, with the same name but with two arguments, is internally called _foo_2. This makes the things simpler, instead of using va_arg

How to use it

The Makefile is configured to create a shared library, you can use it with your C++ programs dynamically linking this library.

Let’s me show an example of a little program that use it:

#include <iostream>
#include <MExpr.h>
using namespace std;

void myfunc(MExpr::StackType* s){ //myfunc(n) = n*3
    s->stack[s->stp-1] *= 3;
}

void myDiv(MExpr::StackType* s){ //myDiv(a,b) = a/b
    MExpr::ValueType arg1, arg2;
    arg1 = s->stack[s->stp-2];
    arg2 = s->stack[s->stp-1];
    s->stack[s->stp-2] = arg1 / arg2;
    s->stp--;
}

void mySum2(MExpr::StackType* s){ //mySum2(a,b) = a+b
    s->stack[s->stp-2] = s->stack[s->stp-2] + s->stack[s->stp-1];
    s->stp--;
}
void mySum3(MExpr::StackType* s){ //mySum2(a,b,c) = a+b+c
    s->stack[s->stp-3] = s->stack[s->stp-3]
                       + s->stack[s->stp-2]
                       + s->stack[s->stp-1];
    s->stp -= 2;
}

int main(int argc, char** argv){
    MExpr::Expression* e;
    MExpr::ValueType ris;

    string expr(argv[1]);

    try{
        /*the Expression constructor parse the string and make the AST Tree */
        e = new MExpr::Expression(expr);
    }catch(MExpr::Error ex){
        cout << "Err: " << ex.what() << endl;
        return 0;
    }

    try{
        //example variables definitions
        e->setVariable('x', 3);
        e->setVariable('y', 2);
        e->setVariable('z', 3);
        e->setVariable('x', 5); //variable redefinition

        //example functions definitions
        e->setFunction("_math", &myfunc, 1);
        e->setFunction("_div", &myDiv, 2);
        e->setFunction("_sum", &mySum2, 2); //example of overloaded function
        e->setFunction("_sum", &mySum3, 3); //example of overloaded function

    }catch(MExpr::Error ex){
        /* Catch errors if variable has strange symbols or function names 
         * doesn't start with '_' */
        cout << "Err: " << ex.what() << endl;
    }

    try{
        e->setVariable('-', 3); //the error will be catch
    }catch(MExpr::Error ex){
        cout << "Err: " << ex.what() << endl;
    }
    try{
        e->setFunction("nounderscore", &mySum3, 3); //the error will be catch
    }catch(MExpr::Error ex){
        cout << "Err: " << ex.what() << endl;
    }

    cout << "AST Tree:" << endl;
    string* s = e->getExprTreeString();
    cout << *s;
    delete s;

    try{
        cout << "Result: " << e->evaluate() << endl;
    }catch(MExpr::Error ex){
        cout << "Err: " << ex.what() << endl;
    }

    e->compile();
    cout << "Compiled Expression Code:" << endl;
    s = e->getExprCodeString(); //if you have not compiled s will be NULL
    if(s != NULL){ cout << *s; delete s; }

    try{
        /* if you compiled the evaluation is made using the code (most efficient)
         * it you have not compiled it is made navigating the AST tree */
        cout << e->evaluate() << endl;
    }catch(MExpr::Error ex){
        cout << "Err: " << ex.what() << endl;
    }

    delete e;
    return 0;
}

Now we need to compile it specifing the mexpr library:

$ g++ -o myexample -lmexpr myexample.cpp

And now we can test all we want:

$ ./myexample "_sum(2+2yx^2, -735)-3(_sum(1,2) + _sum(1,2,3))(-5x)"

How to compile

  • Ensure that you satisfy the requirements.
  • Open the Makefile and set your OS changing the OperatingSystem variable.
  • Type make to compile the library

If you want to install the library in /usr/local/lib type sudo make install

Common issues

  • Mac OS X, by default, doesn’t have the /usr/local/lib and /usr/local/include folders, check that you have these folders.
  • You can have some problems compiling your examples if you don’t install it before. If you don’t want to install it, ensure that the DYLD_LIBRARY_PATH (or the LD_LIBRARY_PATH) was proudly configured.

Requirements

Now, the library is done to work with Mac OSX an Linux. To compile the library you need: bison, flex and g++.

2 comments on “MExpr

  1. Look in your header file where you dlacere the functional prototype. This is the “myfile.h” file. Or, it may be towards the top of the .c or .cpp file. Do a global search in your entire project.In it, you may have miss-declared the function. Make sure it is dlacered exactly like your function. ie:double average(double s1, double s2, double s3, double s4);You may have more than four arguments dlacered there and only four in your actual function. Don’t know if this is your problem–just something to check.Good luck.

Leave a Reply

Your email address will not be published. Required fields are marked *

*