Оценка математических выражений

Ответ 1

Альтернативой реализации собственного анализатора парсера и выражения будет ссылка на библиотеку, которая предоставляет вам один из них. Интересным выбором будет легко внедренный язык сценариев, например Lua.

Просто настроить экземпляр интерпретатора Lua и передать его выражения для оценки, возвращая функцию для вызова, которая оценивает выражение. Вы даже можете позволить пользователю иметь переменные...

Обновление: LE, простой оценщик выражений с использованием Lua

Вот схематичная реализация простого оценщика выражений на основе интерпретатора Lua. Я скомпилировал это и попробовал его для нескольких случаев, но его, конечно, не следует доверять производственному коду, не обращая внимания на обработку ошибок и т.д. Здесь применяются все обычные оговорки.

Я скомпилировал и протестировал это в Windows с помощью Lua 5.1.4 от Lua для Windows. На других платформах вам нужно будет найти Lua из вашего обычного источника или с сайта www.lua.org.

Открытый интерфейс для LE

Вот файл 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);

Пример кода с использованием LE

Вот файл t-le.c, демонстрирующий простое использование этой библиотеки. Он принимает свой единственный аргумент командной строки, загружает его как выражение и оценивает его с изменением глобальной переменной x с 0.0 до 1.0 на 11 шагов:

#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);
    }
}

Вот несколько результатов из 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:...>

Реализация LE

Вот le.c, реализующий оценщик выражения Lua:

#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;
}

Примечания

Вышеприведенный образец состоит из 189 строк кода, включая разметку комментариев, пустые строки и демонстрацию. Неплохо для быстрого анализатора функций, который умеет оценивать разумно произвольные выражения одной переменной и имеет богатую библиотеку стандартных математических функций на своих страницах и звоните.

У вас есть полный язык Turing под всем этим, и это будет простое расширение, позволяющее пользователю определять полные функции, а также оценивать простые выражения.

Ответ 2

Я попросил Google "рекурсивный синтаксический анализатор спуска" (я не виню вас за то, что не знаю, что искать) и нашел Разбор выражений рекурсивным Descent, в котором содержится введение в некоторые полезные методы анализа.

Кроме того, статья Википедии о Рекурсивный парсер спуска включает довольно полный пример в C.

Ответ 3

Алгоритм, который вам нужен, это Алгоритм Shunting Yard.

Это позволяет вам преобразовать выражение in-fix в обратную польскую нотацию, которую довольно просто оценить программно.

Алгоритм Shunting Yard Algorithm довольно востребован, но мой опыт заключается в том, что вы можете его кодировать так же, как и его написанное, и все это работает - вам не нужно идти на труд, чтобы проанализировать его.

Ответ 4

Если вы хотите предложить библиотеку, которая уже делает это, тогда я предпочла бы библиотеку C

Вы должны взглянуть на TinyExpr. Он выполняет именно то, что вы ищете, является автономным в одном исходном файле ANSI C и разрешен для лицензии (лицензия zlib).

Вот какой код будет выглядеть, чтобы решить вашу проблему с примером 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);
}

Обратите внимание, что вы можете "скомпилировать" один раз, а затем многократно оценивать с разными значениями x. Для некоторых выражений это всего на несколько процентов медленнее, чем собственный C-код.

Ответ 5

Вы можете использовать алгоритм Shunting-yard, он отлично работает и позволяет вам легко разбирать функции и т.д. Он фактически не вычисляет его, но преобразует выражение в ONP, которое можно легко оценить.