Mã python nào tạo ra tất cả các nhóm có thể (cây) cho các toán tử nhị phân

Question

Như đã giải thích trong một số câu hỏi SO, và trừu tượng hơn tại mathworld, chuỗi số Catalan xảy ra tương ứng với số nhóm cha mẹ có thể tạo số toán tử. Nhưng tôi đã không tìm thấy một thuật toán để tạo ra tất cả các nhóm này.

Thuật toán đặt ngoặc kép này tương ứng với Tamari Lattice và có thể được mô tả theo một số cách khác nhau. Việc sử dụng thực tế rõ ràng nhất cho thuật toán này là tạo ra tất cả các biểu thức có thể bằng mọi giá trị có thể có xung quanh toán tử nhị phân và số mà chúng hoạt động. Điều này có thể được sử dụng để kiểm tra toàn diện các loại hoạt động khác nhau trên cây nhị phân.

Tìm kiếm trên web đã tiết lộ one implementation in C# nhưng tôi nghĩ sẽ mất một thời gian để hiểu vì tôi không biết cú pháp C#.

Vì vậy, mã python tạo ra tất cả các nhóm có thể có dấu ngoặc đơn xung quanh toán tử (do đó có thể được sử dụng với biểu thức thực tế để tạo tất cả các khả năng)?Đầu ra sẽ trông như sau cho 2, 3 và 4:

AllBinaryTrees (2)

1. (x (xx))
2. ((xx) x)

AllBinaryTrees (3)

1. (((xx) x) x)
2. ((x (xx)) x)
3. ((xx) (xx))
4. (x ((xx) x))
5. (x (x (xx)))

AllBinaryTrees (4)

1. (x (x (x (xx))))
2. (x (x ((xx) x)))
3. (x ((xx) (xx)))
4. (x ((x (xx)) x))
5. (x (((xx) x) x))
6. ((xx) (x (xx)))
7. ((xx) ((xx) x))
8. ((x (xx)) (xx))
9. (((xx) x) (xx))
10. ((x (x (xx))) x)
11. ((x ((xx) x)) x)
12. (((xx) (xx)) x)
13. (((x (xx)) x) x)
14. ((((xx) x) x) x)

012.351.

Thậm chí tốt hơn sẽ là mã mà đã làm một cái gì đó như sau:

AllBinaryTrees ("2 + 3/4")

đầu ra:

1. 2+ (3/4)
2. (2 + 3)/4

Answer 1

Làm thế nào về

def allbinarytrees(s): 
    if len(s) == 1: 
     yield s 
    else: 
     for i in range(1, len(s), 2): 
      for l in allbinarytrees(s[:i]): 
       for r in allbinarytrees(s[i+1:]): 
        yield '({}{}{})'.format(l, s[i], r) 

sử dụng mẫu:

for t in allbinarytrees('1+2-3*4/5'): 
    print(t) 

Output:

(1+(2-(3*(4/5)))) 
(1+(2-((3*4)/5))) 
(1+((2-3)*(4/5))) 
(1+((2-(3*4))/5)) 
(1+(((2-3)*4)/5)) 
((1+2)-(3*(4/5))) 
((1+2)-((3*4)/5)) 
((1+(2-3))*(4/5)) 
(((1+2)-3)*(4/5)) 
((1+(2-(3*4)))/5) 
((1+((2-3)*4))/5) 
(((1+2)-(3*4))/5) 
(((1+(2-3))*4)/5) 
((((1+2)-3)*4)/5) 

Answer 2

Câu trả lời được chấp nhận chỉ hoạt động cho số chữ số duy nhất, và tôi sẽ để lại nó như là câu trả lời được chấp nhận vì nó minh họa các khái niệm trong một dễ dàng để đọc thời trang., Messier tìm phiên bản sửa đổi này làm việc cho tất cả các số, không chỉ là số chữ số duy nhất: sử dụng

def allbinarytrees(s): 
    if s.isdigit(): 
     yield s 
    else: 
     i = 0 
     while i < len(s)-1: 
      while i < len(s) and s[i].isdigit(): 
       i += 1 
      if i < len(s) - 1: 
       for left in allbinarytrees(s[:i]): 
        for right in allbinarytrees(s[i+1:]): 
         yield '({}{}{})'.format(left, s[i], right) 
      i += 1 

mẫu:

j=0 
for t in allbinarytrees('11+22*3/4456'): 
    j += 1 
    print j, (t[1:-1]) 

Output:

1 11+(22*(3/4456)) 
2 11+((22*3)/4456) 
3 (11+22)*(3/4456) 
4 (11+(22*3))/4456 
5 ((11+22)*3)/4456