Evaluating mathematical expressions

Question

I am looking for an algorithm that I can use to evaluate mathematical expressions. I've seen a few questions on SO that are simmilar but the answers are C#/Delphi or python specific. I need to write the algorithm in C :)

The problem I am trying to solve is given a user input like

3*(2*x + 1)/x

I can evaluate the expression for any value of x.

What algorithms are available to do this? If you would like to suggest a library that already does this, then I would prefer a C library

Thank you

Answer 1

You can use Shunting-yard algorithm, it work's great and enables you to parse functions etc. at ease. It doesn't actually compute it, but it converts an expression to ONP, which can be evaluated very easily.

Answer 2

If you would like to suggest a library that already does this, then I would prefer a C library

You should take a look at TinyExpr. It does exactly what you're looking for, is self-contained in a single ANSI C source file, and is permissibly licensed (zlib license).

Here's what the code would look like to solve your example problem of 3*(2*x + 1)/x:

/* Store variable name(s) and pointer(s). */
double x;
te_variable vars[] = {{"x", &x}};

/* Compile the expression. */
int err;
te_expr *expr = te_compile("3*(2*x + 1)/x", vars, 1, &err);

if (expr) {
    x = 7.5; /* Set x to desired value. */
    const double result = te_eval(expr); /* Evaluate it. */

    /* Set x to a different value and re-evaluate as many times as needed. */

    te_free(expr); /* Free the memory used by the compiled expression. */

} else {

    /* TinyExpr identifies right where it found an error. */
    printf("Parse error at %d\n", err);
}

Note that you can "compile" once and then evaluate many times with different values of x. For some expressions, it's only a few percent slower than native C code.

Answer 3

The algorithm you need here is the Shunting Yard Algorithm.

This allows you to convert an in-fix expression into Reverse Polish notation, which is quite simple to evaluate programatically.

The Shunting Yard Algorithm is quite involved, but my experiences is that you can code it up just as its written and it all works - you don't have to go to the trouble of analysing it.

Answer 4

I asked Google for "recursive descent expression parser" (I don't blame you for not knowing what to look for) and found Parsing Expressions by Recursive Descent which provides an introduction to some useful parsing techniques.

Also, the Wikipedia article on Recursive descent parser includes a fairly complete example in C.

Answer 5

An alternative to implementing your own parser and expression evaluator would be to link against a library that provides one for you to use. An interesting choice would be an easily embedded scripting language such as Lua.

It is straightforward to set up a Lua interpreter instance, and pass it expressions to be evaluated, getting back a function to call that evaluates the expression. You can even let the user have variables...

Update: LE, A simple expression evaluator using Lua

Here is a sketchy implementation of a simple expression evaluator based on a Lua interpreter. I compiled this and tried it for a few cases, but it certainly should not be trusted in production code without some attention to error handling and so forth. All the usual caveats apply here.

I compiled and tested this on Windows using Lua 5.1.4 from Lua for Windows. On other platforms, you'll have to find Lua from your usual source, or from www.lua.org.

Public interface to LE

Here is the file le.h:

/* Public API for the LE library.
 */
int le_init();
int le_loadexpr(char *expr, char **pmsg);
double le_eval(int cookie, char **pmsg);
void le_unref(int cookie);
void le_setvar(char *name, double value);
double le_getvar(char *name);

Sample code using LE

Here is the file t-le.c, demonstrating a simple use of this library. It takes its single command-line argument, loads it as an expression, and evaluates it with the global variable x changing from 0.0 to 1.0 in 11 steps:

#include <stdio.h>
#include "le.h"

int main(int argc, char **argv)
{
    int cookie;
    int i;
    char *msg = NULL;

    if (!le_init()) {
    printf("can't init LE\n");
    return 1;
    }
    if (argc<2) {
    printf("Usage: t-le \"expression\"\n");
    return 1;
    }
    cookie = le_loadexpr(argv[1], &msg);
    if (msg) {
    printf("can't load: %s\n", msg);
    free(msg);
    return 1;
    }
    printf("  x    %s\n"
       "------ --------\n", argv[1]);
    for (i=0; i<11; ++i) {
    double x = i/10.;
    double y;

    le_setvar("x",x);
    y = le_eval(cookie, &msg);
    if (msg) {
        printf("can't eval: %s\n", msg);
        free(msg);
        return 1;
    }
    printf("%6.2f %.3f\n", x,y);
    }
}

Here is some output from t-le:

E:...>t-le "math.sin(math.pi * x)"
  x    math.sin(math.pi * x)
------ --------
  0.00 0.000
  0.10 0.309
  0.20 0.588
  0.30 0.809
  0.40 0.951
  0.50 1.000
  0.60 0.951
  0.70 0.809
  0.80 0.588
  0.90 0.309
  1.00 0.000

E:...>

Implementation of LE

Here is le.c, implementing the Lua Expression evaluator:

#include <lua.h>
#include <lauxlib.h>

#include <stdlib.h>
#include <string.h>

static lua_State *L = NULL;

/* Initialize the LE library by creating a Lua state.
 *
 * The new Lua interpreter state has the "usual" standard libraries
 * open.
 */
int le_init()
{
    L = luaL_newstate();
    if (L) 
    luaL_openlibs(L);
    return !!L;
}

/* Load an expression, returning a cookie that can be used later to
 * select this expression for evaluation by le_eval(). Note that
 * le_unref() must eventually be called to free the expression.
 *
 * The cookie is a lua_ref() reference to a function that evaluates the
 * expression when called. Any variables in the expression are assumed
 * to refer to the global environment, which is _G in the interpreter.
 * A refinement might be to isolate the function envioronment from the
 * globals.
 *
 * The implementation rewrites the expr as "return "..expr so that the
 * anonymous function actually produced by lua_load() looks like:
 *
 *     function() return expr end
 *
 *
 * If there is an error and the pmsg parameter is non-NULL, the char *
 * it points to is filled with an error message. The message is
 * allocated by strdup() so the caller is responsible for freeing the
 * storage.
 * 
 * Returns a valid cookie or the constant LUA_NOREF (-2).
 */
int le_loadexpr(char *expr, char **pmsg)
{
    int err;
    char *buf;

    if (!L) {
    if (pmsg)
        *pmsg = strdup("LE library not initialized");
    return LUA_NOREF;
    }
    buf = malloc(strlen(expr)+8);
    if (!buf) {
    if (pmsg)
        *pmsg = strdup("Insufficient memory");
    return LUA_NOREF;
    }
    strcpy(buf, "return ");
    strcat(buf, expr);
    err = luaL_loadstring(L,buf);
    free(buf);
    if (err) {
    if (pmsg)
        *pmsg = strdup(lua_tostring(L,-1));
    lua_pop(L,1);
    return LUA_NOREF;
    }
    if (pmsg)
    *pmsg = NULL;
    return luaL_ref(L, LUA_REGISTRYINDEX);
}

/* Evaluate the loaded expression.
 * 
 * If there is an error and the pmsg parameter is non-NULL, the char *
 * it points to is filled with an error message. The message is
 * allocated by strdup() so the caller is responsible for freeing the
 * storage.
 * 
 * Returns the result or 0 on error.
 */
double le_eval(int cookie, char **pmsg)
{
    int err;
    double ret;

    if (!L) {
    if (pmsg)
        *pmsg = strdup("LE library not initialized");
    return 0;
    }
    lua_rawgeti(L, LUA_REGISTRYINDEX, cookie);
    err = lua_pcall(L,0,1,0);
    if (err) {
    if (pmsg)
        *pmsg = strdup(lua_tostring(L,-1));
    lua_pop(L,1);
    return 0;
    }
    if (pmsg)
    *pmsg = NULL;
    ret = (double)lua_tonumber(L,-1);
    lua_pop(L,1);
    return ret;
}


/* Free the loaded expression.
 */
void le_unref(int cookie)
{
    if (!L)
    return;
    luaL_unref(L, LUA_REGISTRYINDEX, cookie);    
}

/* Set a variable for use in an expression.
 */
void le_setvar(char *name, double value)
{
    if (!L)
    return;
    lua_pushnumber(L,value);
    lua_setglobal(L,name);
}

/* Retrieve the current value of a variable.
 */
double le_getvar(char *name)
{
    double ret;

    if (!L)
    return 0;
    lua_getglobal(L,name);
    ret = (double)lua_tonumber(L,-1);
    lua_pop(L,1);
    return ret;
}

Remarks

The above sample consists of 189 lines of code total, including a spattering of comments, blank lines, and the demonstration. Not bad for a quick function evaluator that knows how to evaluate reasonably arbitrary expressions of one variable, and has rich library of standard math functions at its beck and call.

You have a Turing-complete language underneath it all, and it would be an easy extension to allow the user to define complete functions as well as to evaluate simple expressions.