存储数学表达式以进行计算的有效方法是什么？-解网

问：

我的目标是编写一个程序，可以解析包括变量在内的数学表达式 - 如“x^2+3y+sin（x）” - 然后在给定其值时计算它们（因此对于 x=0，y=1，输出将为 3）。

解析本身没有问题 - 我使用了调车场算法的一个版本，它运行良好。但是，我现在正在考虑如何以一种易于评估的方式存储输出。

一种方法是简单地将表达式中的所有变量替换为其值，然后对其进行计算。如果表达式被计算一次就好了 - 但是，我希望会有一个表达式，并且会插入许多不同的值。因此，我想找到一种方法来存储解析的表达式，以便快速替换变量并对其进行计算，并且具有合理的内存效率。有什么想法吗？

我想到的一种方法是将表达式存储为反向波兰符号的标记数组，可以有效地进行评估。可能看起来像这样：Token

enum TokenType {NUMBER, VARIABLE, OPERATOR, FUNCTION};

struct Token
{
  TokenType type;
  union
  {
    int value; // if type = NUMERIC
    int variable_index;  // if type = VARIABLE
    operator_params op;  // if type = OPERATOR
    function_params fun; // if type = FUNCTION
  }
}

变量值可以在一个简单的数组中进行排序，并由的访问。当值发生变化时，我们只需更新变量值数组 - 表达式保持不变。variable indexToken

我不确定存储此应用程序的运算符和函数的最佳方式是什么。我的想法是有一个指向正确操作的函数指针，但我不确定这是否是最好的方法。

C++ 解析符号数学

最简单的维护方式可能是简单地定义一个抽象类，然后从公式中构建一个表达式树。另一种选择是存储要执行的正确操作顺序，并使用堆栈来存储数据/中间结果，以确定最初将变量放置在堆栈上的方式，但这可能更难维护......class Expression { public: virtual Expression() = default; virtual double operator()(double* vars) = 0; };

0赞 Thomas Matthews 7/14/2023

在我的编译器类中，我们将变量名和函数名等名称转换为标记。大多数分析都是用代币进行的。由于标记是数字，因此处理比在任何地方使用字符串更有效。您必须进行分析或基准测试才能获得效率的真相。

答：

2赞 G. Sliepen 7/14/2023 #1

按 RPN 顺序对令牌进行排序是一种方法，并且性能非常高。标记可以是文字、变量或运算符。若要计算表达式，请按顺序处理标记，如果是文本或变量，则将其值推送到堆栈。如果是操作，则从堆栈中弹出一个或两个项目（取决于它是一元运算符还是二进制运算符），对这些项目应用操作，然后将结果推送回去。对于格式正确的表达式，最后在堆栈上将留下一个值，这是计算的最终结果。

另一种有效的方法是创建嵌套的 lambda 表达式，正如我在这篇 CodeReview 文章中所展示的那样。这样做的主要优点是解析表达式的结果是一个 lambda 函数，其工作方式与 C++ 中的常规函数几乎相同。

上一个：“解析”特定字符串的最快方法

下一个：这是在 C++ 中构造抽象语法树的语法节点的合理方法（或者是否有更安全或更节省内存的构造）？

存储数学表达式以进行计算的有效方法是什么？

What is an efficient way to store mathematical expressions for evaluation?

评论