Tôi có cây nhị phân biểu thị một công thức logic được phân tích cú pháp. Ví dụ,f = a & b & -c | Được biểu thị bằng danh sách các danh sách theo ký hiệu tiền tố, trong đó các phần tử đầu tiên là toán tử (đơn phân hoặc nhị phân) và các phần tử sau là đối số của chúng:

f = [ |, [&, a, [&, b, [-, c]]], d]

Nhưng nếu bạn dịch (thông qua đệ quy) sang ký hiệu trung tố cổ điển thì kết quả vẫn như nhau.

f = (((-c & b) & a) | d) = a & b & -c |

Điều tôi muốn làm là chuyển đổi nó thành cây N-ary giữ nguyên thông tin, nghĩa là nếu bạn chuyển đổi lại thành công thức thì kết quả phải giống nhau. Như thế này:

f = {l: [{&: [a,b,{-:[c]}]}, d]}

Sau đây là các ký hiệu infix.

f = ((a & b & -c) | d) = a & b & -c |

Tôi chưa tìm thấy thư viện nào, vì vậy tôi đang cố gắng tự mình làm điều đó một cách đệ quy. Tuy nhiên, tôi chỉ triển khai mã này và không thành công trong một số trường hợp nhất định và nó không được trang nhã cho lắm...

    def Explore_tree(self,tree, Last_symbol, new_tree):
        if type(tree) != list: # Điều này đúng có nghĩa là gốc là một nguyên tử
            new_tree[last_symbol].append(cây)
            trở lại
        gốc = cây[0]
        nếu is_operator(root):
            nếu root != Last_symbol:
                nhánh = {gốc: []}
                new_tree[last_symbol].append(nhánh)
                #Dòng này dùng để tìm kiếm chỉ mục của đối tượng nhánh và mở rộng theo chúng
                self.explore_branches(cây, root, new_tree[last_symbol]
                                     [new_tree[last_symbol].index(branch)]) 
            khác:
                self.explore_branches(cây,root,new_tree)

chức năng khám phá_branches() Được gọi đệ quy để khám phá cây từ trái và phải (nếu có), nếu chuỗi đã cho là toán tử logic thì is_operator() Trả về true, chẳng hạn như & hoặc |.

Có ý tưởng nào khác về cách thực hiện việc này không?

Cảm ơn trước.

câu trả lời hay nhất

Trường hợp nhạy cảm duy nhất là phủ định. Ngoài ra, bạn có thể chỉ cần viết thuật toán của mình hoặc một cái gì đó tương tự như

từ nhập functools giảm
def op(cây):
    trả về 0 nếu loại(cây)!=danh sách cây khác[0]

def bin_to_n(cây):
    nếu op(cây)==0:
        cây trả về
    op_tree = cây[0]
    out = [op_tree]
    cho nút trong cây [1:]:
        flat_node = bin_to_n(nút)
        nếu op(nút) != op_tree:
            out.append(flat_node)
        khác:
            out += flat_node[1:]
    return out

Bây giờ về sự phủ định. Trường hợp thất bại của thuật toán trên là làm phẳng -(-(1)) đưa ra khi -1 thay vì 1

• Vì vậy, một sửa chữa rất cơ bản là

< if op(node) != op_tree
---
> nếu op(node) != op_tree hoặc op(node)=="-"

Có nghĩa là nếu tìm thấy "dấu trừ", bạn không bao giờ "kết nối" nó. Vì vậy điều này làm cho -(-(1)) Để nguyên như vậy.

Bây giờ chúng ta có thể đơn giản hóa hơn nữa, nhưng việc đơn giản hóa này có thể được thực hiện trước trên danh sách đầu vào. Vì vậy, nó thay đổi cây một cách "ngữ nghĩa" (mặc dù việc đánh giá vẫn giữ nguyên).

• Chỉ xử lý hai phủ định:

op_tree = cây[0]
> if op_tree == '-' và op(tree[1]) == '-':
> trả về bin_to_n2(cây[1][1])
out = [op_tree]

• Hoặc đến các tu sĩ và thực sự áp dụng Định luật De Morgan khi tìm ra sự phủ định

#thực sự nghịch đảo theo định luật demorgan
def bin_to_n3(cây, phủ định=Sai):
    nếu op(cây)==0:
        cây trả về

    op_tree = cây[0]

    nếu phủ định:
        nếu op_tree == '-':
            #double neg, bỏ qua nút
            trả về bin_to_n3(cây[1])

        #demorgan
        out = [ '+' if op_tree == '*' else '*' ]
        cho nút trong cây [1:]:
            flat_node = bin_to_n3(nút, Đúng)
            #lưu ý rằng vì chúng ta sửa đổi các toán tử nên chúng ta có 
            #lấy toán tử của cây kết quả
            nếu op(flat_node) != op_tree:
                out.append(flat_node)
            khác:
                out += flat_node[1:]
        return out

    nếu op_tree == '-' và op(op_tree)==0:
        #không chạm vào chiếc lá
        cây trả về

    #code giống như trên, không chơi chữ để phân tích nó
    out = [op_tree]
    cho nút trong cây [1:]:
        flat_node = bin_to_n3(nút)
        nếu op(flat_node) != op_tree:
            out.append(flat_node)
        khác:
            out += flat_node[1:]
    return out

Dưới đây là một số kiểm tra ngẫu nhiên để đảm bảo phép chuyển đổi giữ nguyên các giá trị của cây

từ nhập functools giảm
def op(cây):
    trả về 0 nếu loại(cây)!=danh sách cây khác[0]

def bin_to_n(cây):
    nếu op(cây)==0:
        cây trả về
    op_tree = cây[0]
    out = [op_tree]
    cho nút trong cây [1:]:
        flat_node = bin_to_n(nút)
        nếu op(node) != op_tree hoặc op(node)=='-':
            out.append(flat_node)
        khác:
            out += flat_node[1:]
    return out

def bin_to_n2(cây):
    nếu op(cây)==0:
        cây trả về

    op_tree = cây[0]
    nếu op_tree == '-' và op(tree[1]) == '-':
        trả về bin_to_n2(cây[1][1])
    out = [op_tree]
    cho nút trong cây [1:]:
        flat_node = bin_to_n2(nút)
        nếu op(nút) != op_tree:
            out.append(flat_node)
        khác:
            out += flat_node[1:]
    return out

#thực sự nghịch đảo theo định luật demorgan
def bin_to_n3(cây, phủ định=Sai):
    nếu op(cây)==0:
        cây trả về

    op_tree = cây[0]

    nếu phủ định:
        nếu op_tree == '-':
            #double neg, bỏ qua nút
            trả về bin_to_n3(cây[1])

        #demorgan
        out = [ '+' if op_tree == '*' else '*' ]
        cho nút trong cây [1:]:
            flat_node = bin_to_n3(nút, Đúng)
            #lưu ý rằng vì chúng ta sửa đổi các toán tử nên chúng ta có 
            #lấy toán tử của cây kết quả
            nếu op(flat_node) != op_tree:
                out.append(flat_node)
            khác:
                out += flat_node[1:]
        return out

    nếu op_tree == '-' và op(op_tree)==0:
        #không chạm vào chiếc lá
        cây trả về

    #code giống như trên, không chơi chữ để phân tích nó
    out = [op_tree]
    cho nút trong cây [1:]:
        flat_node = bin_to_n3(nút)
        nếu op(flat_node) != op_tree:
            out.append(flat_node)
        khác:
            out += flat_node[1:]
    return out

def calc(cây):
    nếu op(cây) == 0:
        cây trả về
    s = 0
    cây con = cây[1:]
    nếu op(cây)=='+':
        s = less(lambda x,y: x hoặc calc(y), cây con, Sai)
    Elif op(cây) == '-':
        s = không phải calc(cây con[0])
    khác:
        s = less(lambda x,y: x và calc(y), cây con, True)
    trả lại s

#được điều chỉnh từ https://stackoverflow.com/questions/6881170/is-there-a-way-to-autogenerate-valid-arithmetic-expressed
chắc chắn brute_check():
    nhập khẩu ngẫu nhiên
    ngẫu nhiên.seed(3)
    chắc chắn make_L(n=3):
        def expr(độ sâu):
            nếu độ sâu==1 hoặc ngẫu nhiên.random()<1.0/(2**độ sâu-1): 
                trả về ngẫu nhiên.choice([0,1])
            nếu ngẫu nhiên.random() <0,25:
                trả về ['-', expr(độ sâu-1)]
            return [random.choice(['+','*']), expr(độ sâu-1), expr(độ sâu-1)]
        trả về expr(n)

    cho tôi trong phạm vi (100):
        L = make_L(n=10)
        a = calc(L)
        b = calc(bin_to_n(L))
        c = calc(bin_to_n2(L))
        d = calc(bin_to_n3(L))
        nếu a != b:
            print('sự khác biệt', L,bin_to_n(L), a, b)

        nếu a != c:
            print('sự khác biệt', L,bin_to_n2(L), a, c)

        nếu a != d:
            print('sự khác biệt', L,bin_to_n3(L), ​​​​a, d)
brute_check()

Về Python - Cách chuyển đổi cây nhị phân thành cây N-ary giữ nguyên thông tin, chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/58883506/