파이썬에서 알고리즘 구현

Question

특정 알고리즘을 구현해야합니다. 기본적으로 규칙은 다음과 같습니다.

1. 줄의 첫 번째 공백으로 구분 된 토큰은 정의되는 단어입니다.
2. 나중에 토큰이 정의됩니다. 정의가 "."인 경우, 그 단어는 프리미티브, 즉 정의가없는 단어이다.
3. 출력은 딕셔너리의 각 단어가 정확히 한 번만 포함 된 쉼표로 구분 된 한 줄의 텍스트입니다. 각 단어는 정의에있는 모든 단어 뒤에 인쇄됩니다. 특정 입력 세트의 경우 유효한 출력이 여러 개있을 수 있습니다.

예를 들어 입력 :

Civic  Honda Car 
Honda  Manufacturer 
VW   Manufacturer 
Manufacturer . 
Car   . 
Beetle  VW Car 

일부 가능한 출력 :

Car, Manufactor, Honda, VW, Beetle, Civic 
Manufacturer, VW, Car, Beetle, Honda, Civic 
Manufacturer, Honda, VW, Car, Beetle, Civic 

내 구현 :

def defIt(pre, cur): 
    # If previous and current strings are the same, no action take 
    if pre == cur: 
     return pre 

    # Split two strings to list 
    l_pre = pre.split() 
    l_cur = cur.split() 

    # If previous string length is shorter than the current string  length, then swap two lists 
    if len(l_pre) < len(l_cur): 
     l_pre, l_cur = l_cur, l_pre 

    found = False 


    for j, w_cur in enumerate(l_cur): 
     for i, w_pre in enumerate(l_pre): 
      if w_pre == w_cur: 
       found = True 
       return ' '.join(l_cur[j:] + l_cur[:j] + l_pre[:i] + l_pre[(i + 1):]) 


    if not found: 
     return ' '.join(l_cur[1:] + [l_cur[0]] + l_pre) 

이 바로 그것을 얻을 수 없습니다. 나는 무엇을 놓치고 있습니까? 고마워.

Answer 1

def read_graph(lines): 
    g = {} 
    for line in lines: 
     words = line.split() 
     if words[1] == '.': 
      words = words[:1] 
     g[words[0]] = words[1:] 
    return g 

def dump_graph(g): 
    out = [] 
    def dump(key): 
     for k in g[key]: 
      dump(k) 
     if key not in out: 
      out.append(key) 
    for k in g: 
     dump(k) 
    return out 

사용법 :

>>> data = """Civic  Honda Car 
... Honda  Manufacturer 
... VW   Manufacturer 
... Manufacturer . 
... Car   . 
... Beetle  VW Car 
... """ 
>>> g = read_graph(data.splitlines()) 
>>> g 
{'VW': ['Manufacturer'], 'Civic': ['Honda', 'Car'], 'Car': [], 
'Honda': ['Manufacturer'], 'Beetle': ['VW', 'Car'], 'Manufacturer': []} 
>>> dump_graph(g) 
['Manufacturer', 'VW', 'Honda', 'Car', 'Civic', 'Beetle'] 
>>> 

결과 목록에서 모든 단어는 모든 "정의"단어 뒤에 온다.