如何从二进制结构中递归提取

Question

我有一个Python类：

class PointInfo(object):

    def __init__(self, pnt, vect, src1, src2, fun):

        self.point = pnt
        self.vector = vect
        self.src1 = src1
        self.src2 = src2
        self.func = fun

我已经创建了一个列表（imp\u list），该列表的每个元素都是PointInfo类型的对象，source1或source2可以引用某个基点（以“Original”开头），或者它们包含该列表中上一个元素的索引，该索引通过该元素创建了该对象。你知道吗

每个对象的构造都像（source1函数source2）函数是一些布尔运算，现在我想追溯每个点，找出每个点的来源，直到到达基点为止。你知道吗

例如，如果我有这样一个列表：

如果我想追溯点0的来源，它必须给我：(Ori1 & Ori2)

或者点1的来源必须给我：(Ori3 | (Ori1 & Ori2))

或者第2点从哪里来，必须给我：(Ori4 ^ (Ori1 & Ori2))

或者第3点的来源必须给我：(Ori5 & (Ori3 | (Ori1 & Ori2)))

以此类推，如何通过python实现这一点？你知道吗

Answer 1

有一种方法可以实现：

def trace_source(point):
    if str(point.src1).startswith("Ori") and str(point.src2).startswith("Ori"):
        return '('+point.src1+' '+str(point.func)+' '+point.src2+')'
    elif str(point.src1).startswith("Ori") and not str(point.src2).startswith("Ori"):
        return '('+point.src1+' '+str(point.func)+' '+trace_source(imp_list[point.src2])+')'
    elif not str(point.src1).startswith("Ori") and str(point.src2).startswith("Ori"):
        return '('+trace_source(imp_list[point.src1])+' '+str(point.func)+' '+point.src2+')'
    else:
        return '('+trace_source(imp_list[point.src1])+' '+str(point.func)+' '+trace_source(imp_list[point.src2])+')'

这是基本思想。您可能需要根据数据结构对代码进行一些调整。你知道吗

编辑

我使用给定的类使用以下列表测试了您的代码：

imp_list = []
imp_list.append(PointInfo(None, None, "Ori1", "Ori2", "&"))
imp_list.append(PointInfo(None, None, 0, "Ori3", "|"))
imp_list.append(PointInfo(None, None, 0, "Ori4", "^"))
imp_list.append(PointInfo(None, None, 1, "Ori5", "&"))
imp_list.append(PointInfo(None, None, 3, "Ori6", "&"))

for point in imp_list:
    print  trace_source(point)

结果是：

(Ori1 & Ori2)
((Ori1 & Ori2) | Ori3)
((Ori1 & Ori2) ^ Ori4)
(((Ori1 & Ori2) | Ori3) & Ori5)
((((Ori1 & Ori2) | Ori3) & Ori5) & Ori6)

所以，很显然这是可行的。你知道吗

Answer 2

只需使用@user2963623给出的递归过程执行深度优先搜索。递归的重要部分是：

1. 确定基本情况

2. 参数如何通过递归调用更改

3. 当当前级别结束时，我们返回到它的上级是什么样的结果

在您的特定情况下，给定一个点x，您可以继续跟踪src1或src2或两者的“链接”，直到到达“原点”

<强>1。基本情况：

如果src1和src2都以“origin”开头，则返回它

<强>2。递归探索

“src1”，如果它有到其他点的“链接”

或'src2'，如果它有一个'链接'到其他点

或'src1'和'src2'，如果两者都有到另一点的'link'