基于栈的表达式求值在数学解析中的效率

Question

出于学术目的，我必须编写一个应用程序来绘制用户输入表达式，如: f(x) =1- exp(3^(5*ln(cosx)) + x)

我选择的编写解析器的方法是使用Shunting-Yard算法转换RPN中的表达式，将"cos“等原始函数视为一元运算符。这意味着上面编写的函数将转换为一系列标记，如下所示：

1, x, cos, ln, 5, *,3, ^, exp, -

问题是，要绘制函数图，我必须对其进行多次求值，因此对每个输入值应用堆栈求值算法将非常低效。我该如何解决这个问题呢？我必须忘记RPN的想法吗？

Answer 1

“很多次”是多少？一百万？

可以输入什么类型的函数？我们能假设它们是连续的吗？

你有没有试过测量你的代码的执行情况？

(抱歉，从问题开始！)

您可以尝试下面简要描述的两种方法中的一种(或两种)(可能还有更多)：

1)解析树。

您可以创建一个Parse Tree。然后执行大多数编译器所做的优化表达式、常量折叠、公共子表达式消除(您可以通过将公共表达式子树链接在一起并缓存结果)等操作。

然后，您可以使用惰性评估技术来避免整个子树。例如，如果你有一棵树

    *
   / \
  A   B

当A的计算结果为0时，您可以完全避免计算B，因为您知道结果为0。使用RPN，您将失去懒惰评估的机会。

2)插值

假设你的函数是连续的，你可以使用Polynomial Interpolation将你的函数近似到很高的精度。这样，您可以多次执行函数的复杂计算(基于您选择的多项式次数)，然后在其余时间进行快速多项式计算。

要创建初始数据集，您可以使用方法1或坚持使用您的RPN，因为您将只生成几个值。

所以如果你使用插值，你可以保持你的RPN..。

希望这能有所帮助！

Answer 2

为什么要重新发明轮子呢？改用一种快速的脚本语言。将像lua这样的东西集成到您的代码中将花费很少的时间，并且非常快。

你通常可以对表达式进行字节编译，这应该会导致代码运行得非常快，对于简单的一维图来说肯定足够快了。

我推荐lua，因为它速度快，并且比其他脚本语言更容易与C/C++集成。另一个很好的选择是python，但是虽然它更为人所知，但我发现它更难集成。

Answer 3

为什么不使用解析树(我松散地使用" tree“，在您的例子中它是一个操作序列)，并相应地标记输入变量？(例如，对于输入x，y，z等，用0注释"x“表示第一个输入变量，用1注释"y”表示第二个输入变量，等等)

这样，您就可以解析表达式一次，保留解析树，接受一组输入，然后应用解析树进行计算。

如果您担心计算步骤(与解析步骤)的性能方面，我认为除非您开始进行矢量化(将解析树立即应用于输入向量)或将操作硬编码到固定函数中，否则您不会做得更好。