c# - 我如何构建一个算法来根据一组公式计算对象的值？

Question

假设我有以下 Field 对象的集合:

public class Field
{
    public string Formula { get; set; }
    public string Name { get; set; }
    public double Value { get; set; }
}

每个字段都有一个唯一的名称。有些字段有一个公式。该公式是一个数学表达式，用于计算字段的值，其中输入是集合中由其名称表示的其他字段。我给出的集合可能看起来像这样:

• 姓名:“A”；公式: ””;值(value):0.0
• 姓名:“B”；公式: ””;值(value):0.0
• 姓名:“C”；公式:“A+B”；值(value):0.0
• 姓名:“D”；公式:“E+F”；值(value):0.0
• 姓名:“E”；公式:“C+14”；值(value):0.0
• 姓名:“F”；公式: ””;值(value):0.0
• 姓名:“G”；公式“D * .05”；值(value):0.0

现在假设 Name == "A"字段的值更改为 25.0。当发生这种情况时，C 需要计算为“25.0 + 0.0”，这将需要计算 E。但是计算 E 首先需要计算 D，计算 D 还需要计算 G。

是否有标准算法或数据结构可以确定 a) 应计算哪些字段值，以及当任何给定字段的值发生变化时应计算哪些字段值，以及 b) 以必要的正确顺序计算这些字段？

作为奖励，确定在如下场景中集合中的公式配置中是否存在任何无限(左？)递归可能会很好:

• 姓名:“A”；公式:“B”；值(value):0.0
• 姓名:“B”；公式:“A*10”；值(value):0.0
• 姓名:“C”；公式:“A+B”；值(value):0.0
• 姓名:“D”；公式:“B+C”；值(value):0.0

我已经有一段时间没有做这样的事情了(自从大学以来就没有了)，如果能帮助我走上正确的道路，我将不胜感激。如果我写的任何内容需要澄清，请告诉我。

谢谢。

Answer 1

构造一个表达式图，并应用topological sort给它。如果您的表达式包含循环，拓扑排序算法会检测到它，并报告您的表达式不是无环图。以反向拓扑顺序评估节点可让您计算表达式的值。

为了找到哪些节点需要重新评估，构造一个逆依赖图，并计算它的transitive closure .当节点在运行时更改状态时，请查阅预先计算的闭包以查找需要重新评估的所有节点的列表作为结果。这些节点需要按照与拓扑排序一致的顺序重新求值。