从C++调用Python或Lua来计算表达式,仅在需要时计算未知变量

Question

我有一个像这样的表达式/公式

 std::string expr="((A>0) && (B>5 || C > 10))";

我做了一些研究,似乎如果已知A,B,C值,通过在C++程序中嵌入Lua或Python,有些eval函数可以替代A,B和C并返回true或false.

但是当我不知道所有的价值时会发生什么？让我们说A是已知的,它是-1.如果A为-1,则无论B或C的值如何,公式都将评估为"假".

我可以在不事先知道所有变量的情况下评估公式吗？例如,如果A为10,则查找B的值并再次重新评估是有意义的.我们如何解决这些问题？想法？

Answer 1

我不知道有任何现有的库来处理这个问题.

通常的方法是构建表达式树并评估可能的内容 - 类似于编译器中的常量折叠:https: //en.wikipedia.org/wiki/Constant_folding

其中一个重要方面是知道变量的允许值,因此允许的部分评估,例如x*0(和0*x)是0if x是整数还是有限浮点数,但如果x是IEEE浮点数则无法求值(因为它可能是Nan或无穷大),或者如果x可能是矩阵,因为[1,1]*0它[0,0]不是标量0.

Answer 2

一种方法是将表达式解析为树并评估树.将全面评估已知所有变量的Subexpressions.效果将是简化树.

在您的示例中,树&&的顶部有两个子树,左侧是树A>0.为了评估树,我们评估左子树,返回-1,因此我们不需要评估正确的子树,因为运算符是&&.整棵树评估为假.

Answer 3

我不清楚你想要做什么或理解什么,但我对ivan_pozdeev关于短路评估和懒惰评估是好的.

布尔表达式从左到右进行求值,当结果已知时,评估停止并忽略右侧的内容.

使用Python:

E = "(A > 0) and (B > 5 or C > 10)"
A = -1
print(eval(E))

给

False

但

E = "(A > 0) and (B > 5 or C > 10)"
A = 1
print(eval(E))

给出错误" 名称'B'未定义 ".

Answer 4

听起来您面临两个挑战：

1. 计算某些变量值的成本很高，因此您希望避免计算计算表达式时不需要的值；和
2. 您的表达式以字符串形式存在，在运行时组成，因此您无法使用 C++ 的内置短路逻辑。

这意味着您需要某种方法在运行时计算表达式，并且如果可能的话您希望利用短路逻辑。Python 可能是一个不错的选择，如下例所示。

有一个简短的 Python 脚本 ( evaluate.py)，它定义了一个evaluate()可以从 C 或 C++ 程序中调用的函数。该evaluate()函数将尝试计算您给它的表达式（如果需要，将“&&”和“||”翻译为“and”和“or”）。如果它需要一个尚未定义的变量，它将通过调用get_var_value()C/C++ 程序中定义的函数来检索该变量的值（然后缓存该值以供以后使用）。

此方法将使用正常的短路行为，因此它只会请求完成计算表达式所需的变量值。请注意，这不会重新排列表达式以选择评估它所需的最小变量集；它只是使用标准的短路行为。

更新：我在最后添加了一个示例，该示例使用 .cpp 文件中的多行字符串文字定义 Python 脚本。如果您不想与可执行文件一起安装单独的评估.py 文件，这可能很有用。它还稍微简化了 Python 初始化。

以下脚本中的 C/Python 交互基于https://docs.python.org/2/extending/embedding.html和https://docs.python.org/2/c-api/arg 中的代码。 html。

以下是文件：

评估.py（Python 脚本）

# load embedded_methods module defined by the parent C program
from embedded_methods import get_var_value

# define a custom dictionary class that calls get_var_value(key) for any missing keys.
class var_dict(dict):
    def __missing__(self, var):
        self[var] = val = get_var_value(var)
        return val

# define a function which can be called by the parent C program
def evaluate(expr):
    # Create a dictionary to use as a namespace for the evaluation (this version 
    # will automatically request missing variables).
    # Move this line up to the module level to retain values between calls.
    namespace = var_dict()

    # convert C-style Boolean operators to Python-style
    py_expr = expr.replace("||", " or ").replace("&&", " and ").replace("  ", " ")

    print('evaluating expression "{}" as "{}"'.format(expr, py_expr))

    # evaluate the expression, retrieving variable values as needed
    return eval(py_expr, namespace)

evaluate.c（你的主程序；也可以是evaluate.cpp，用g++编译）

// on Mac, compile with gcc -o evaluate evaluate.c -framework Python
#include <Python/Python.h>  // Mac
// #include <Python.h> // non-Mac?

// retain values of argc and argv for equation evaluation
int argc;
char **argv;

/* 
   Calculate the value of a named variable; this is called from the Python 
   script to obtain any values needed to evaluate the expression. 
*/
static PyObject* c_get_var_value(PyObject *self, PyObject *args)
{
    int var_num;
    char *var_name;
    char err_string[100];
    long var_value;
    if(!PyArg_ParseTuple(args, "s:get_var_value", &var_name)) {
        PyErr_SetString(PyExc_ValueError, "Invalid arguments passed to get_var_value()");
        return NULL;
    }
    // change the code below to define your variable values
    // This version just assumes A, B, C are given by argv[2], argv[3], argv[4], etc.
    printf("looking up value of %s: ", var_name);
    var_num = var_name[0]-'A';
    if (strlen(var_name) != 1 || var_num < 0 || var_num >= argc-2) {
        printf("%s\n", "unknown");
        snprintf(
            err_string, sizeof(err_string), 
            "Value requested for unknown variable \"%s\"", var_name
        );
        PyErr_SetString(PyExc_ValueError, err_string);
        return NULL;  // will raise exception in Python
    } else {
        var_value = atoi(argv[2+var_num]);
        printf("%ld\n", var_value);
        return Py_BuildValue("l", var_value);
    }
}

// list of methods to be added to the "embedded_methods" module
static PyMethodDef c_methods[] = {
    {"get_var_value", c_get_var_value, METH_VARARGS, // could use METH_O
     "Retrieve the value for the specified variable."},
    {NULL, NULL, 0, NULL} // sentinel for end of list
};

int main(int ac, char *av[])
{
    PyObject *p_module, *p_evaluate, *p_args, *p_result;
    long result;
    const char* expr;

    // cache and evaluate arguments
    argc = ac;
    argv = av;
    if (argc < 2) {
        fprintf(
            stderr, 
            "Usage: %s \"expr\" A B C ...\n"
            "e.g.,  %s \"((A>0) && (B>5 || C > 10))\" 10 9 -1\n", 
            argv[0], argv[0]
        );
        return 1;
    }
    expr = argv[1];

    // initialize Python
    Py_SetProgramName(argv[0]);
    Py_Initialize();
    // Set system path to include the directory where this executable is stored
    // (to find evaluate.py later)
    PySys_SetArgv(argc, argv);

    // attach custom module with get_var_value() function
    Py_InitModule("embedded_methods", c_methods);

    // Load evaluate.py
    p_module = PyImport_ImportModule("evaluate");
    if (PyErr_Occurred()) { PyErr_Print(); }
    if (p_module == NULL) {
        fprintf(stderr, "unable to load evaluate.py\n");
        return 1;
    }

    // get a reference to the evaluate() function
    p_evaluate = PyObject_GetAttrString(p_module, "evaluate");
    if (!(p_evaluate && PyCallable_Check(p_evaluate))) {
        fprintf(stderr, "Cannot retrieve evaluate() function from evaluate.py module\n");
        return 1;
    }

     /*
        Call the Python evaluate() function with the expression to be evaluated.
        The evaluate() function will call c_get_var_value() to obtain any
        variable values needed to evaluate the expression. It will use 
        caching and normal logical short-circuiting to reduce the number 
        of requests.
     */
    p_args = Py_BuildValue("(s)", expr);
    p_result = PyObject_CallObject(p_evaluate, p_args);
    Py_DECREF(p_args);
    if (PyErr_Occurred()) {
        PyErr_Print();
        return 1;
    }
    result = PyInt_AsLong(p_result);
    Py_DECREF(p_result);

    printf("result was %ld\n", result);

    Py_DECREF(p_evaluate);
    Py_DECREF(p_module);
    return 0;
}

结果：

$ evaluate "((A>0) && (B>5 || C > 10))" -1 9 -1
evaluating expression "((A>0) && (B>5 || C > 10))" as "((A>0) and (B>5 or C > 10))"
looking up value of A: -1
result was 0

$ evaluate "((A>0) && (B>5 || C > 10))" 10 9 -1
evaluating expression "((A>0) && (B>5 || C > 10))" as "((A>0) and (B>5 or C > 10))"
looking up value of A: 10
looking up value of B: 9
result was 1

$ evaluate "((A>0) && (B>5 || C > 10))" 10 3 -1
evaluating expression "((A>0) && (B>5 || C > 10))" as "((A>0) and (B>5 or C > 10))"
looking up value of A: 10
looking up value of B: 3
looking up value of C: -1
result was 0

作为替代方案，您可以将所有这些代码合并到一个 .cpp 文件中，如下所示。这使用了 C++11 中的多行字符串文字功能。

独立的evaluate.cpp

// on Mac, compile with g++ evaluate.cpp -o evaluate -std=c++11 -framework Python
#include <Python/Python.h>  // Mac
//#include <Python.h> // non-Mac?

/* 
   Python script to be run in embedded interpreter.
   This defines an evaluate(expr) function which will interpret an expression
   and return the result. If any variable values are needed, it will call the
   get_var_values(var) function defined in the parent C++ program
*/
const char* py_script = R"(
# load embedded_methods module defined by the parent C program
from embedded_methods import get_var_value

# define a custom dictionary class that calls get_var_value(key) for any missing keys.
class var_dict(dict):
    def __missing__(self, var):
        self[var] = val = get_var_value(var)
        return val

# define a function which can be called by the parent C program
def evaluate(expr):
    # Create a dictionary to use as a namespace for the evaluation (this version 
    # will automatically request missing variables).
    # Move this line up to the module level to retain values between calls.
    namespace = var_dict()

    # convert C-style Boolean operators to Python-style
    py_expr = expr.replace("||", " or ").replace("&&", " and ").replace("  ", " ")

    print('evaluating expression "{}" as "{}"'.format(expr, py_expr))

    # evaluate the expression, retrieving variable values as needed
    return eval(py_expr, namespace)
)";

// retain values of argc and argv for equation evaluation
int argc;
char **argv;

/* 
   Calculate the value of a named variable; this is called from the Python 
   script to obtain any values needed to evaluate the expression. 
*/
static PyObject* c_get_var_value(PyObject *self, PyObject *args)
{
    int var_num;
    char *var_name;
    char err_string[100];
    long var_value;
    if(!PyArg_ParseTuple(args, "s:get_var_value", &var_name)) {
        PyErr_SetString(PyExc_ValueError, "Invalid arguments passed to get_var_value()");
        return NULL;
    }
    // change the code below to define your variable values
    // This version just assumes A, B, C are given by argv[2], argv[3], argv[4], etc.
    printf("looking up value of %s: ", var_name);
    var_num = var_name[0]-'A';
    if (strlen(var_name) != 1 || var_num < 0 || var_num >= argc-2) {
        printf("%s\n", "unknown");
        snprintf(
            err_string, sizeof(err_string), 
            "Value requested for unknown variable \"%s\"", var_name
        );
        PyErr_SetString(PyExc_ValueError, err_string);
        return NULL;  // will raise exception in Python
    } else {
        var_value = atoi(argv[2+var_num]);
        printf("%ld\n", var_value);
        return Py_BuildValue("l", var_value);
    }
}

// list of methods to be added to the "embedded_methods" module
static PyMethodDef c_methods[] = {
    {"get_var_value", c_get_var_value, METH_VARARGS, // could use METH_O
     "Retrieve the value for the specified variable."},
    {NULL, NULL, 0, NULL} // sentinel for end of list
};

int main(int ac, char *av[])
{
    PyObject *p_module, *p_evaluate, *p_args, *p_result;
    long result;
    const char* expr;

    // cache and evaluate arguments
    argc = ac;
    argv = av;
    if (argc < 2) {
        fprintf(
            stderr, 
            "Usage: %s \"expr\" A B C ...\n"
            "e.g.,  %s \"((A>0) && (B>5 || C > 10))\" 10 9 -1\n", 
            argv[0], argv[0]
        );
        return 1;
    }
    expr = argv[1];

    // initialize Python
    Py_SetProgramName(argv[0]);
    Py_Initialize();

    // attach custom module with get_var_value() function
    Py_InitModule("embedded_methods", c_methods);

    // run script to define evalute() function
    PyRun_SimpleString(py_script);
    if (PyErr_Occurred()) {
        PyErr_Print(); 
        fprintf(stderr, "%s\n", "unable to run Python script");
        return 1;
    }

    // get a reference to the Python evaluate() function (can be reused later)
    // (note: PyRun_SimpleString creates objects in the __main__ module)
    p_module = PyImport_AddModule("__main__");
    p_evaluate = PyObject_GetAttrString(p_module, "evaluate");
    if (!(p_evaluate && PyCallable_Check(p_evaluate))) {
        fprintf(stderr, "%s\n", "Cannot retrieve evaluate() function from __main__ module");
        return 1;
    }

    /*
       Call the Python evaluate() function with the expression to be evaluated.
       The evaluate() function will call c_get_var_value() to obtain any
       variable values needed to evaluate the expression. It will use 
       caching and normal logical short-circuiting to reduce the number 
       of requests.
    */
    p_args = Py_BuildValue("(s)", expr);
    p_result = PyObject_CallObject(p_evaluate, p_args);
    Py_DECREF(p_args);
    if (PyErr_Occurred()) {
        PyErr_Print();
        return 1;
    }
    result = PyInt_AsLong(p_result);
    Py_DECREF(p_result);

    printf("result was %ld\n", result);

    Py_DECREF(p_module);
    Py_DECREF(p_evaluate);
    return 0;
}