Dav*_*uve 7 math performance parsing rpn shunting-yard
出于学术目的,我必须编写一个绘制用户输入表达式的应用程序,如:f(x)= 1 - exp(3 ^(5*ln(cosx))+ x)
我选择编写解析器的方法是使用Shunting-Yard算法转换RPN中的表达式,将原始函数如"cos"视为一元运算符.这意味着上面写的函数将被转换为一系列令牌,如:
1, x, cos, ln, 5, *,3, ^, exp, -
问题是绘制我必须要评估它的函数很多次,因此对每个输入值应用堆栈评估算法将是非常低效的.我怎么解决这个问题？我是否必须忘记RPN的想法？
小智 3
“很多次”是多少？一百万？
可以输入什么样的函数？我们可以假设它们是连续的吗？
您是否尝试过衡量代码的性能？
（抱歉，一开始就带着问题！）
您可以尝试下面简要描述的两种方法之一（或两者）（可能还有更多）：
您可以创建一个解析树。然后执行大多数编译器所做的操作来优化表达式、常量折叠、公共子表达式消除（可以通过将公共表达式子树链接在一起并缓存结果来实现）等。
然后您可以使用惰性求值技术来避免整个子树。例如，如果你有一棵树
*
/ \
A B
当 A 的计算结果为 0 时，您可以完全避免计算 B，因为您知道结果为 0。使用 RPN，您将失去惰性计算的机会。
假设您的函数是连续的，您可以使用多项式插值来高精度逼近您的函数。这样，您可以对函数进行几次复杂的计算（基于您选择的多项式的次数），然后在其余时间进行快速多项式计算。
要创建初始数据集，您可以仅使用方法 1 或仅坚持使用 RPN，因为您只会生成几个值。
所以如果你使用插值，你可以保留你的 RPN...
希望有帮助！