找到多个方程的评估顺序的算法

Question

我的文本内容充满了这样的表达:

a = 1
d = b + c 
b = a * c
c = 2 - a
...

这个表达式可以以随机顺序书写。我可以提取这些表达式中的每一个并评估它们中的每一个，但我需要找到最佳算法来避免循环评估，例如:

a = 1
d = ? (skip)
b = ? (skip)
c = 2 - a = 1
...
d = ? (skip)
b = a * c = 1
...
d = b + c = 2
...

有没有办法通过所涉及的参数“排序”方程以避免额外的计算通过，例如:

a = 1
c = 2 - a = 1
b = a * c = 1
d = b + c = 2
...

?

Answer 1

对于每个表达式，在图中创建一个节点，其中传入边是它所依赖的其他表达式。然后使用拓扑排序来确定评估顺序。

例子:

表达式:

a = 1
d = b + c 
b = a * c
c = 2 - a

图节点:

a()
d(b,c)
b(a,c)
c(a)

拓扑排序:

begin
    process a
        process a's dependencies (none)
        output a
        mark a as done
    process d
        process d's dependencies
            process b
                process b's dependencies
                    process a (already done)
                    process c
                        process c's dependencies
                            process a (already done)
                        output c
                        mark c as done
                output b
                mark b as done
            process c (already done)
        output d
        mark d as done
    process b (already done)
    process c (already done)
end

结果:

a c b d