新鲜狗家阳谷昂赛

最后一题用递归，每当遇到括号时

第一轮参考这里：https://www.geeksforgeeks.org/kt ... -binary-tree-set-2/

请问楼主有后续消息么 已加米～

第六题应当是用stack， 从左到右扫一遍，在从右到左扫一遍，顺便把括号除掉。每逢括号就把当前的字母串压入stack。

补充内容 (2019-5-15 12:39):
第一步要先把字符串tokenize.

第六题用递归的方式写了一下

1. def process(str, start, end, parenthesisMatch):
   
2.     # Separate the string by commas on the same level
   
3.     i, j = start, start
   
4.     list = []
   
5.     while j <= end:
   
6.         if str[j] == ',':
   
7.             list.append((i, j))
   
8.             i = j + 1
   
9.         elif str[j] == '{':
   
10.             j = parenthesisMatch[j]
    
11.         j += 1
    
12.     if i<j:
    
13.         list.append((i, j))
    
14.    
    
15.     # Parse each separated string (recursive)
    
16.     res = []
    
17.     for i, j in list:
    
18.         if str[i:j].isalpha():
    
19.             res.append(str[i:j])
    
20.         else:
    
21.             ii, jj = i, i
    
22.             super = [""]
    
23.             while jj<j:
    
24.                 if str[jj] == '{':
    
25.                     res_before = process(str, ii, jj-1, parenthesisMatch)
    
26.                     res_in_paren = process(str, jj+1, parenthesisMatch[jj]-1, parenthesisMatch)
    
27.                     if res_before:
    
28.                         for k in range(len(res_in_paren)):
    
29.                             res_in_paren[k] = res_before[0] + res_in_paren[k]
    
30.                     super_new = []
    
31.                     for s in super:
    
32.                         for t in res_in_paren:
    
33.                             super_new.append(s+t)
    
34.                     super = super_new
    
35.                     jj = parenthesisMatch[jj]
    
36.                     ii = jj + 1
    
37.                 jj += 1
    
38.             if ii<jj:
    
39.                 for k in range(len(super)):
    
40.                     super[k] += str[ii:jj]
    
41.             res.extend(super)
    
42.     return res
    
43. 
    
44. def interpret(str):
    
45.     parenthesisMatch = {} # Key: index of left parenthesis, value: index of right parenthesis
    
46.     stack = []
    
47.     for i, c in enumerate(str):
    
48.         if c == '{':
    
49.             stack.append(i)
    
50.         elif c == '}':
    
51.             parenthesisMatch[stack.pop()] = i
    
52.     return process(str, 0, len(str) - 1, parenthesisMatch)
    
53.    
    
54. print(interpret('{a,b}x{c,d}y{e,f{g,h}{i,j}k}'))

复制代码