是否有优化表达式的算法？

Question

例如，我有表达式x+2*(4*7)的标记数组

{ "x" , "+" , "2" , "*" , "(" , "4" , "*" , "7" , ")" }

我需要像x+56那样的输出。这是一个简单的例子，可能要困难得多。我知道Dijkstra的分流码算法，但不确定这是否能为优化提供具体帮助。坦率地说，我不知道如何理解这个表达式最大的优化，因为我不能看到所有可能的优化方法。也许有一种算法能考虑到所有的细微差别？

Answer 1

在您的问题中，用于优化表达式的技术称为常折叠。它找到每个值都是常量的表达式，并将该表达式替换为操作的结果。

Start with x+2*(4*7)
Notice 4*7 is an operation with constant arguments
Compute 4*7=28, replace in expression to get x+2*(28)
Notice (28) can be de-bracketed, to get x+2*28
Notice 2*28 is an operation with constant arguments
Compute 2*28=56, replace in expression to get x+56
Notice there are no more operations with all constant arguments
End with x+56

另请参阅：

• 优化编译器 (其他优化技术)
• 上下文自由文法 (启动将文本转换为更易于使用的树结构的路径)。

Answer 2

你可能要找的是一个计算机代数系统。有可用的几种开放源码系统；如果限制每月使用几千次api调用，也可以免费使用Wolfram Alpha API。