评估数学表达式
我正在寻找一种可以用来评估数学表达式的算法。 我已经看到了几个关于SO的问题，但是答案是C＃/ Delphi或python特有的。 我需要在C中编写算法:)
我试图解决的问题是给用户输入，如
3*(2*x + 1)/x 我可以评估任何x值的表达式。
有哪些算法可以做到这一点？ 如果您想建议一个已经执行此操作的库，那么我更喜欢C库
谢谢
实现自己的解析器和表达式求值程序的另一种方法是链接一个提供一个供您使用的库。 一个有趣的选择是一个易于嵌入的脚本语言，如Lua 。
设置一个Lua解释器实例并传递它要表达的表达式是直接的，返回一个函数来调用它来计算表达式。 你甚至可以让用户拥有变量……
更新：LE，一个使用Lua的简单表达式求值程序
这是一个基于Lua解释器的简单表达式求值程序的粗略实现。 我编译了这个并尝试了几个案例，但在生产代码中肯定不应该信任它而不需要注意error handling等等。 所有常见的警告都适用于此。
我使用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 #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 #include #include #include 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具有丰富的标准数学函数库，这不错。
您可以在其下面使用图灵完备语言，这将是一个简单的扩展，允许用户定义完整的函数以及评估简单表达式。
我向谷歌询问了“递归下降表达式解析器”（我不会责怪你不知道该找什么），并通过递归下降找到解析表达式，它提供了一些有用的解析技术的介绍。
另外，关于递归下降解析器的维基百科文章在C中包含了一个相当完整的例子。
你需要的算法是Shunting Yard算法 。
这允许您将in-fix表达式转换为Reverse Polish表示法 ，这非常容易以编程方式进行评估。
Shunting Yard算法非常复杂，但我的经验是你可以像编写它一样编写代码并且一切正常 – 你不必去分析它。
如果您想建议一个已经执行此操作的库，那么我更喜欢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代码慢几个百分点。
您可以使用Shunting-yard算法 ，它工作得很好，使您可以轻松地解析function等。 它实际上并不计算它，但它将表达式转换为ONP，可以非常容易地进行计算。