math - 用于数学解析的基于堆栈的表达式评估的效率

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)解析树。

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

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

    *
   / \
  A   B

其中 A 评估为 0，您可以完全避免评估 B，因为您知道结果为 0。使用 RPN，您将失去惰性评估。

2) 插值

假设您的函数是连续的，您可以使用 Polynomial Interpolation 以高精度逼近您的函数.这样，您可以对函数进行几次复杂的计算(根据您选择的多项式次数)，然后在其余时间进行快速多项式计算。

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

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

希望有帮助!