una - Evaluar expresiones matemáticas

evaluar expresiones algebraicas online

Question

Estoy buscando un algoritmo que pueda usar para evaluar expresiones matemáticas. He visto algunas preguntas sobre SO que son similares, pero las respuestas son C # / Delphi o específicas de Python. Necesito escribir el algoritmo en C :)

El problema que estoy tratando de resolver recibe una entrada de usuario como

3*(2*x + 1)/x

Puedo evaluar la expresión para cualquier valor de x.

¿Qué algoritmos están disponibles para hacer esto? Si desea sugerir una biblioteca que ya hace esto, entonces preferiría una biblioteca C

Gracias

Answer 1

El algoritmo que necesita aquí es el Algoritmo de yarda de derivación .

Esto le permite convertir una expresión en arreglo en notación polaca inversa , que es bastante simple de evaluar programáticamente.

El algoritmo de yarda de derivación es bastante complicado, pero mi experiencia es que puedes codificarlo tal como está escrito y funciona: no tienes que tomarse la molestia de analizarlo.

Answer 2

Le pedí a Google un "analizador de expresiones de descenso recursivo" (no te culpo por no saber qué buscar) y encontré el análisis de expresiones mediante el descenso recursivo, que proporciona una introducción a algunas técnicas útiles de análisis sintáctico.

Además, el artículo de Wikipedia sobre el analizador de descenso recursivo incluye un ejemplo bastante completo en C.

Answer 3

Puede usar el algoritmo de yarda de derivación , funciona bien y le permite analizar funciones, etc. a gusto. En realidad, no lo calcula, pero convierte una expresión en ONP, que se puede evaluar con mucha facilidad.

Answer 4

Una alternativa a la implementación de su propio analizador de expresiones y analizador de expresiones sería enlazar con una biblioteca que proporcione uno para su uso. Una opción interesante sería un lenguaje de scripting fácilmente incorporado como Lua .

Es fácil configurar una instancia de intérprete de Lua y pasarle las expresiones para que se evalúe, obteniendo una función para llamar que evalúa la expresión. Incluso puedes dejar que el usuario tenga variables ...

Actualización: LE, un simple evaluador de expresiones que usa Lua

Aquí hay una implementación incompleta de un evaluador de expresiones simple basado en un intérprete de Lua. Compilé esto y lo probé en algunos casos, pero ciertamente no se debe confiar en el código de producción sin prestar atención al manejo de errores y demás. Todas las advertencias habituales se aplican aquí.

Compilé y probé esto en Windows usando Lua 5.1.4 de Lua para Windows . En otras plataformas, deberá encontrar Lua desde su fuente habitual o desde www.lua.org.

Interfaz pública para LE

Aquí está el archivo 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);

Código de muestra usando LE

Aquí está el archivo t-le.c, que demuestra un uso simple de esta biblioteca. Toma su único argumento de línea de comando, lo carga como una expresión y lo evalúa con la variable global x cambiando de 0.0 a 1.0 en 11 pasos:

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

Aquí hay algunos resultados de 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:...>

Implementación de LE

Aquí está le.c , implementando el evaluador Lua Expression:

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

Observaciones

La muestra anterior consta de 189 líneas de código total, incluida una salpicadura de comentarios, líneas en blanco y la demostración. No está mal para un evaluador de funciones rápido que sabe cómo evaluar expresiones razonablemente arbitrarias de una variable, y tiene una rica biblioteca de funciones matemáticas estándar a su disposición.

Usted tiene un lenguaje completo de Turing debajo de todo, y sería una extensión fácil de permitir al usuario definir funciones completas así como evaluar expresiones simples.

Answer 5

Si desea sugerir una biblioteca que ya hace esto, entonces preferiría una biblioteca C

Deberías echarle un vistazo a TinyExpr . Hace exactamente lo que está buscando, es autónomo en un solo archivo de origen ANSI C, y tiene licencia permisible (licencia zlib).

Así es como se vería el código para resolver su problema de ejemplo de 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);
}

Tenga en cuenta que puede "compilar" una vez y luego evaluar muchas veces con diferentes valores de x . Para algunas expresiones, es solo un porcentaje un poco más lento que el código C nativo.