给定一个数学表达式,我想找出可以同时评估的部分。例如,给定以下表达式,
(a + b) * c - (d + e) / f
(a + b)
并且(d + e)
可以同时评估,因为它们彼此独立。
有没有为此目的的算法?或者甚至有没有实现这个功能的库?
这是用于创建数学解析器的简短而简单的分步手册。解析表达式后,持有表示解析表达式的树,您可以对其进行迭代,并且在每次迭代中,树的每一对叶子都将代表一个独立的表达式(可以同时评估)。[在每次迭代中,用它们的结果替换评估的表达式]
好的,让我们将示例视为一棵树:
-
(* /)
(c +) (+ f)
(a b) (d e)
(括号将节点配对为同一父节点的子节点)
如果简单的话,就可以得到那棵树,例如使用 Shutting Yard 算法。
现在观察,为了评估一个节点,您需要的只是该节点的子节点(但递归地如此)。因此,正如您所注意到的(a + b)
,(d + e)
不要相互依赖。也不(c * (a + b))
依赖(d + e)
或依赖((d + e) / f)
,((d + e) / f)
也不依赖(a + b)
。
一般来说,取一个节点n
,任何既不是n
祖先也不是后代的节点,可以同时进行评估。如果您正在使用计划,则必须添加“如果现在可以评估该节点” - 显然您无法在评估其后代之前评估节点。
我不确定您所指的“此目的”是什么。你想计算什么?
评估顺序取决于两个因素:
如果可能有一些涉及同时评估部分表达式的优化,我认为只能在JVM/CLR 级别完成,而不是使用库......
我相信你应该使用Reversed Polish Notation。
阅读以下内容了解更多详情:
这是一个用 C++ 编写的函数,可将正常符号转换为反向波兰符号。有人可能会帮助您将其转换为 C#: