评估数学表达式 [英] Evaluating mathematical expressions
问题描述
我正在寻找一种可用于评估数学表达式的算法.我在 SO 上看到了一些类似的问题，但答案是 C#/Delphi 或 python 特定的.我需要用 C 语言编写算法 :)
我试图解决的问题是给定的用户输入，如
3*(2*x + 1)/x我可以为 x 的任何值计算表达式.
有哪些算法可以做到这一点?如果您想推荐一个已经这样做的库，那么我更喜欢 C 库
谢谢
实现自己的解析器和表达式求值器的另一种方法是链接到一个提供供您使用的库.一个有趣的选择是易于嵌入的脚本语言，例如 Lua.
设置一个 Lua 解释器实例很简单，并传递给它的表达式进行计算，返回一个函数来调用来计算表达式.你甚至可以让用户拥有变量...
更新:LE，一个使用 Lua 的简单表达式求值器
这是一个基于 Lua 解释器的简单表达式求值器的粗略实现.我编译了这个并在一些情况下尝试了它，但是如果不注意错误处理等，它肯定不应该在生产代码中被信任.所有常见的警告都适用于此.
我使用来自 Lua for Windows 的 Lua 5.1.4 在 Windows 上编译并测试了它.在其他平台上，您必须从通常的来源或 www.lua.org 中找到 Lua.
LE 的公共接口
这是le.h文件:
/* LE 库的公共 API.*/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);双 le_getvar(char *name);使用 LE 的示例代码
这是文件 t-le.c，演示了该库的简单使用.它接受它的单个命令行参数，将其作为表达式加载，并在 11 个步骤中使用全局变量 x 从 0.0 变为 1.0 来计算它:
#include #include "le.h"int main(int argc, char **argv){内部饼干;国际我;字符 *msg = NULL;如果(！le_init()){printf("无法初始化 LE
");返回 1；}如果(argc<2){printf("用法:t-le "表达式"
");返回 1；}cookie = le_loadexpr(argv[1], &msg);如果(味精){printf("无法加载:%s
", msg);免费(味精)；返回 1；}printf(" x %s
""------ --------
", argv[1]);对于 (i=0; i<11; ++i) {双 x = i/10.;双y;le_setvar("x",x);y = le_eval(cookie, &msg);如果(味精){printf("无法求值:%s
", msg);免费(味精)；返回 1；}printf("%6.2f %.3f
", x,y);}} 这是 t-le 的一些输出:
<前>E:...>t-le "math.sin(math.pi * x)"x math.sin(math.pi * x)------ ------0.00 0.0000.10 0.3090.20 0.5880.30 0.8090.40 0.9510.50 1.0000.60 0.9510.70 0.8090.80 0.5880.90 0.3091.00 0.000电子:...>LE 的实施
这是 le.c，实现 Lua 表达式求值器:
#include #include #include #include 静态 lua_State *L = NULL;/* 通过创建 Lua 状态来初始化 LE 库.** 新的 Lua 解释器状态具有常用"标准库* 打开.*/int le_init(){L = luaL_newstate();如果 (L)luaL_openlibs(L);返回!!L;}/* 加载一个表达式，返回一个可以稍后使用的cookie* 选择此表达式以通过 le_eval() 进行评估.注意* le_unref() 最终必须被调用以释放表达式.** cookie 是 lua_ref() 对评估* 调用时的表达式.假定表达式中的任何变量* 引用全局环境，在解释器中是_G.* 一种改进可能是将功能环境与* 全局变量.** 该实现将 expr 重写为 "return "..expr，以便* lua_load() 实际产生的匿名函数如下所示:** function() 返回 expr 结束*** 如果有错误且 pmsg 参数为非 NULL，则字符 ** 它指向填充了错误信息.消息是* 由 strdup() 分配，因此调用者负责释放* 贮存.** 返回一个有效的 cookie 或常量 LUA_NOREF (-2).*/int le_loadexpr(char *expr, char **pmsg){错误；字符 *缓冲；如果(！L){如果(消息)*pmsg = strdup("LE 库未初始化");返回 LUA_NOREF；}buf = malloc(strlen(expr)+8);如果(！buf){如果(消息)*pmsg = strdup("内存不足");返回 LUA_NOREF；}strcpy(buf, "返回");strcat(buf, expr);错误 = luaL_loadstring(L,buf);免费(缓冲)；如果(错误){如果(消息)*pmsg = strdup(lua_tostring(L,-1));lua_pop(L,1);返回 LUA_NOREF；}如果(消息)*pmsg = NULL;返回 luaL_ref(L, LUA_REGISTRYINDEX);}/* 评估加载的表达式.** 如果有错误且 pmsg 参数为非 NULL，则字符 ** 它指向填充了错误信息.消息是* 由 strdup() 分配，因此调用者负责释放* 贮存.** 返回结果或出错时返回 0.*/double le_eval(int cookie, char **pmsg){错误；双退;如果(！L){如果(消息)*pmsg = strdup("LE 库未初始化");返回0；}lua_rawgeti(L, LUA_REGISTRYINDEX, cookie);错误 = lua_pcall(L,0,1,0);如果(错误){如果(消息)*pmsg = strdup(lua_tostring(L,-1));lua_pop(L,1);返回0；}如果(消息)*pmsg = NULL;ret = (double)lua_tonumber(L,-1);lua_pop(L,1);返回 ret;}/* 释放加载的表达式.*/void le_unref(int cookie){如果(！L)返回;luaL_unref(L, LUA_REGISTRYINDEX, cookie);}/* 设置一个用于表达式的变量.*/void le_setvar(char *name, double value){如果(！L)返回;lua_pushnumber(L,value);lua_setglobal(L,name);}/* 检索变量的当前值.*/双 le_getvar(char *name){双退;如果(！L)返回0；lua_getglobal(L,name);ret = (double)lua_tonumber(L,-1);lua_pop(L,1);返回 ret;} 备注
上面的样例共189行代码，包括乱七八糟的注释、空行和演示.对于知道如何评估一个变量的合理任意表达式的快速函数评估器来说还不错，并且具有 丰富的标准数学函数库 随叫随到.
你有一个完整的图灵语言，它是一个简单的扩展，允许用户定义完整的函数以及计算简单的表达式.
I am looking for an algorithm that I can use to evaluate mathematical expressions. I've seen a few questions on SO that are simmilar but the answers are C#/Delphi or python specific. I need to write the algorithm in C :)
The problem I am trying to solve is given a user input like
3*(2*x + 1)/x
I can evaluate the expression for any value of x.
What algorithms are available to do this? If you would like to suggest a library that already does this, then I would prefer a C library
Thank you
An alternative to implementing your own parser and expression evaluator would be to link against a library that provides one for you to use. An interesting choice would be an easily embedded scripting language such as Lua.
It is straightforward to set up a Lua interpreter instance, and pass it expressions to be evaluated, getting back a function to call that evaluates the expression. You can even let the user have variables...
Update: LE, A simple expression evaluator using Lua
Here is a sketchy implementation of a simple expression evaluator based on a Lua interpreter. I compiled this and tried it for a few cases, but it certainly should not be trusted in production code without some attention to error handling and so forth. All the usual caveats apply here.
I compiled and tested this on Windows using Lua 5.1.4 from Lua for Windows. On other platforms, you'll have to find Lua from your usual source, or from www.lua.org.
Public interface to LE
Here is the file 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);
Sample code using LE
Here is the file t-le.c, demonstrating a simple use of this library. It takes its single command-line argument, loads it as an expression, and evaluates it with the global variable x changing from 0.0 to 1.0 in 11 steps:
#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
");
return 1;
}
if (argc<2) {
printf("Usage: t-le "expression"
");
return 1;
}
cookie = le_loadexpr(argv[1], &msg);
if (msg) {
printf("can't load: %s
", msg);
free(msg);
return 1;
}
printf(" x %s
"
"------ --------
", 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
", msg);
free(msg);
return 1;
}
printf("%6.2f %.3f
", x,y);
}
}
Here is some output from 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:...>
Implementation of LE
Here is le.c, implementing the Lua Expression evaluator:
#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;
}
Remarks
The above sample consists of 189 lines of code total, including a spattering of comments, blank lines, and the demonstration. Not bad for a quick function evaluator that knows how to evaluate reasonably arbitrary expressions of one variable, and has rich library of standard math functions at its beck and call.
You have a Turing-complete language underneath it all, and it would be an easy extension to allow the user to define complete functions as well as to evaluate simple expressions.
这篇关于评估数学表达式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
