Evaluar expresiones matemáticas

9 minutos de lectura

avatar de usuario
hhafez

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 específicas de C#/Delphi o Python. Necesito escribir el algoritmo en C 🙂

El problema que estoy tratando de resolver se le da 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

  • Esta no es una respuesta C sino la de Bjarne Stroustrup El lenguaje de programación C++ dedica un capítulo a este problema exacto. Podrías adaptarlo a C.

    – Juan

    19 de julio de 2009 a las 23:07

  • C++ está lo suficientemente cerca;) pero no tengo el libro

    – hhafez

    19 de julio de 2009 a las 23:10

  • Eso es genial. La forma en que Stroustrup aborda el problema es el descenso recursivo, por lo que estará bien trabajando con los recursos en la respuesta que aceptó. Es el capítulo 6 (Expresiones y declaraciones) si alguna vez te interesa.

    – Juan

    22 de julio de 2009 a las 15:43

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

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

  • ¡Ding, ding, ding, ding! ¡Esa es la respuesta correcta! Es un problema de análisis de lenguaje.

    – NoMásZealots

    19 de julio de 2009 a las 23:23

  • Esta es también la forma correcta de responder cuando conocimiento la respuesta proporciona información sobre la búsqueda en Google que el OP no habría tenido. Bravo.

    – Bill el lagarto

    20 de julio de 2009 a las 16:05

El algoritmo que necesita aquí es el Algoritmo de patio de maniobras.

Esto le permite convertir una expresión in-fix en Notación polaca inversaque es bastante simple de evaluar programáticamente.

El algoritmo del patio de maniobras es bastante complicado, pero mi experiencia es que puede codificarlo tal como está escrito y todo funciona, no tiene que tomarse la molestia de analizarlo.

  • aunque la dificultad permanece en el analizador 🙂

    – hhafez

    19 de julio de 2009 a las 23:30

avatar de usuario
rberteig

Una alternativa a la implementación de su propio analizador y evaluador de expresiones sería establecer un vínculo con una biblioteca que proporcione uno para su uso. Una opción interesante sería un lenguaje de secuencias de comandos fácilmente incrustado, como Lúa.

Es sencillo configurar una instancia de intérprete de Lua y pasarle expresiones para que se evalúen, recuperando una función para llamar que evalúa la expresión. Incluso puedes dejar que el usuario tenga variables…

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

Aquí hay una implementación esquemática 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, etc. 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, tendrás que encontrar a Lua desde tu fuente habitual o desde www.lua.org.

Interfaz pública a 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);

Ejemplo de código 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.cimplementando 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 en total, incluidos algunos comentarios, líneas en blanco y la demostración. No está mal para un evaluador rápido de funciones que sabe cómo evaluar expresiones razonablemente arbitrarias de una variable y tiene rica biblioteca de funciones matemáticas estándar a su entera disposición.

Tiene un lenguaje completo de Turing debajo de todo, y sería una extensión fácil para permitir que el usuario defina funciones completas y evalúe expresiones simples.

  • @Imbue TinyExpr se ve bastante elegante. Le animo a que escriba la recomendación como una respuesta adecuada para que pueda obtener una reputación. Sería una mejor respuesta si todo lo que necesita son expresiones simples. Y para una serie de aplicaciones, ese será sin duda el caso. Lua comenzará a verse más interesante si también desea un archivo de configuración, o para permitir funciones definidas por el usuario, o para evaluar algoritmos que no se pueden escribir como una sola expresión. La gran sorpresa con Lua es que todo ese poder aún cabe en una biblioteca notablemente pequeña en comparación con cualquier otro lenguaje de programación.

    – R. Berteig

    22 de enero de 2016 a las 23:23

  • @RBerteig Seguí tu consejo y escribí una respuesta (quizás 7 años demasiado tarde, pero tal vez ayude a alguien). He usado a Lua en un par de proyectos diferentes y estoy de acuerdo en que es evidentemente increíble. Uno de mis idiomas favoritos, de hecho. Simplemente creo que es una exageración si en realidad no necesita/quiere un lenguaje de programación completo.

    – Imbuir

    5 de febrero de 2016 a las 19:30

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

Deberías echar un vistazo a TinyExpr. Hace exactamente lo que está buscando, está autocontenido en un solo archivo fuente ANSI C y tiene una licencia permitida (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 pequeño porcentaje más lento que el código C nativo.

Puedes usar Algoritmo de patio de maniobras, funciona muy bien y le permite analizar funciones, etc. con facilidad. En realidad, no lo calcula, pero convierte una expresión en ONP, que se puede evaluar muy fácilmente.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad