c# - 重新创建复杂订单的算法

Question

我在为操作设计算法时遇到问题，我想寻求帮助。由于这相当抽象，因此这只是伪 C#。

我有一个列表中的对象列表:

Object A
Object B
Object C

这个列表来自一个存储区，但是用户可以通过两种方法在列表中创建新元素:复制一个对象或者将两个对象合并在一起。 因此，在用户交互之后，列表可能如下所示:

Object A
Object A1 - Clone of A
Object B
Object C
Object BC - Merge of B and C

每个新对象都存储它的“父对象”，因此可以追踪每个对象的来源。 但是可以链式复制和组合方法，所以第三代可能是这样的:

Object A
Object A1 - Clone of A
Object B
Object A1B - Merge of A1 and B
Object A1B2 - Cloe onf A1b
Object C
Object BC - Merge of B and C
Object BC2 - Clone of BC

现在我陷入困境:有时必须从示例 1 中的存储中重新生成此列表。虽然重新创建“普通”复制或合并对象很容易，但我想不出一个好的算法来识别顺序，必须重新创建组合。 查看迭代 3:要重新创建 A1B2，我必须先克隆 A1，然后将 A1 和 B 合并到 A1B，然后克隆此对象。 是否有某种算法可以确定必要的顺序？

Answer 1

您的符号可能模棱两可:

  Object A
  Object B
  Object A1 - clone A
  Object B1 - clone B
  Object B2 - clone B1
  Object A1B2 - is it a merge of A1 and B2 or clone of A1B1?

我建议使用(至少在内部)RPN(逆波兰表示法)， 让，例如，操作是

  ' for clone 
  + for merge

所以，例如

  A        - just A
  A'       - clone A
  A''      - clone A, then clone the result again
  AB+      - merge A and B
  A'B'+    - clone A, clone B, merge the clones
  A'B+'    - clone A, merge with B, clone the result
  AB'+C'+' - A merged with cloned B merged with cloned C and finally cloned 

RPN 是明确的并且可以轻松地转换(您可以将 RPN 展开成树)到任何其他 表示