评估数学表达式

Question

我正在寻找一种可以用来评估数学表达式的算法.我已经看到了几个关于SO的问题,但是答案是C#/ Delphi或python特有的.我需要用C编写算法:)

我试图解决的问题是给用户输入,如

3*(2*x + 1)/x

我可以评估任何x值的表达式.

有什么算法可以做到这一点？如果您想建议一个已经这样做的库,那么我更喜欢C库

谢谢

Answer 1

我向谷歌询问了"递归下降表达式解析器"(我不会责怪你不知道该找什么),并通过递归下降找到了解析表达式,它提供了一些有用的解析技术的介绍.

另外,关于递归下降解析器的维基百科文章在C中包含了一个相当完整的例子.

Answer 2

这里需要的算法是Shunting Yard算法.

这允许您将in-fix表达式转换为Reverse Polish表示法,这非常容易以编程方式进行评估.

Shunting Yard算法非常复杂,但我的经验是你可以像编写它一样编写它并且一切正常 - 你不必去分析它的麻烦.

Answer 3

实现自己的解析器和表达式求值程序的另一种方法是链接一个提供一个供您使用的库.一个有趣的选择是一个易于嵌入的脚本语言,如Lua.

设置一个Lua解释器实例,然后传递它要表达的表达式,返回一个调用表达式的函数来直接进行评估.你甚至可以让用户拥有变量......

更新:LE,一个使用Lua的简单表达式求值程序

这是一个基于Lua解释器的简单表达式求值程序的粗略实现.我编译了这个并尝试了几个案例,但在生产代码中肯定不应该信任它而不需要注意错误处理等等.所有常见的警告都适用于此处.

我使用Lua for Windows的 Lua 5.1.4在Windows上编译和测试了这个.在其他平台上,您必须从常用来源或www.lua.org找到Lua.

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以11步从0.0变为1.0来对其进行求值:

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

备注

上面的示例包含189行代码,包括一系列注释,空行和演示.对于知道如何评估一个变量的合理任意表达式的快速函数求值器来说,并且在其beck和call上具有丰富的标准数学函数库也不错.

您可以在其下面使用图灵完备语言,这将是一个简单的扩展,允许用户定义完整的函数以及评估简单表达式.