檢查遞歸

Question

我曾嘗試使用下面的代碼創建Python中的樹對象樹子節點的存在：

#!/usr/bin/env python 
# -*- coding: utf-8 -*- 

import re,sys,codecs 

neg_markers_en=[u'not',u"napt",u'no',u'nobody',u'none',u'never'] 

class Node: 
    def __init__(self,name=None,parent=None,sentence_number=0): 
     self.name=name 
     self.next=list() 
     self.parent=parent 
     self.depth=0 
     self.n_of_neg=0 
     self.subordinate=None 
     self.foo=None 

def print_node(self): 
    print self.name,'contains',[(x.name,x.depth,x.foo) for x in self.next] 
    for x in self.next: 
     x.print_node() 

def get_negation(self): 


    for x in self.next: 
     if x.n_of_neg!=0: 
      print unicode(x.depth)+u' |||', 
      try: 
       x.look_for_parent_vp() 
      except: print 'not in a VP', 
      try: 
       x.look_for_parent_sent() 
      except: print '***' 
     x.get_negation() 


def look_for_parent_vp(self): 

    if self.parent.name=='VP': 
     self.parent.print_nont() 
    else: 
     self.parent.look_for_parent_vp() 

def look_for_parent_sent(self): 

    if self.parent.name=='S' or self.parent.name=='SBAR': 
     #This is to send out to a text file, along with what it covers 
     print '||| '+ self.parent.name, 
     try: 
      self.parent.check_subordinate() 
      self.parent.print_nont() 
      print '\n' 
     except: 
      print u'no sub |||', 
      self.parent.print_nont() 
      print '\n' 
    elif self.parent=='None': print 'root |||' 
    else: 
     self.parent.look_for_parent_sent() 


def print_nont(self): 

    for x in self.next: 
     if x.next==[]: 
      print unicode(x.name), 
     else: x.print_nont() 


def mark_subordinate(self): 

    for x in self.next: 
     if x.name=='SBAR': 
      x.subordinate='sub' 
     else: x.subordinate='main' 
     x.mark_subordinate() 

def check_subordinate(self): 

    if self.subordinate=='sub': 
     print u'sub |||', 
    else: 
     self.parent.check_subordinate() 


def create_tree(tree): 

    #replace "n't" with 'napt' so to avoid errors in splitting 
    tree=tree.replace("n't",'napt') 
    lista=filter(lambda x: x!=' ',re.findall(r"\w+|\W",tree)) 

    start_node=Node(name='*NULL*') 
    current_node=start_node 

    for i in range(len(lista)-1): 
     if lista[i]=='(': 
      next_node=Node() 
      next_node.parent=current_node 
      next_node.depth=current_node.depth+1 
      current_node.next.append(next_node) 
      current_node=next_node 
     elif lista[i]==')': 
      current_node=current_node.parent 
     else: 
      if lista[i-1]=='(' or lista[i-1]==')': 
       current_node.name=lista[i] 
      else: 
       next_node=Node() 
       next_node.name=lista[i] 
       next_node.parent=current_node 
       #marks the depth of the node 
       next_node.depth=current_node.depth+1 
       if lista[i] in neg_markers_en: 
        current_node.n_of_neg+=1 
       current_node.next.append(next_node) 


return start_node 

現在所有的節點都連接，從而父節點的子節點附加到列表中，並通過實例父項將這些子節點中的每一個都引回給它們的父節點。 我有以下問題： 對於名稱爲'S'或'SBAR'（我們稱之爲node_to_check）的每個節點，我必須查看它的任何子節點的名稱是'S'還是'SBAR';如果這是不是我想將node_to_check的.foo屬性轉換爲'atom'的情況。

我在想是這樣的：

def find_node_to_check(self): 
    for next in self.next: 
     if next.name == 'S' or next.name == 'SBAR': 
     is_present = check_children(next) 
     if is_present == 'no': 
      find_node_to_check(next) 
     else: 
      self.foo = 'atom' 

def check_children(self): 
    for next in self.next: 
     # is this way of returning correct? 
     if next.name == 'S' or next.name == 'SBAR': 
      return 'no' 
     else: 
      check_sents(next) 
      return 'yes' 

我包括我的問題也是我至今寫的代碼。在函數create_tree（tree）中創建樹結構;輸入樹是斯坦福分析器的括號內的符號。

Answer 1

當試圖設計一個新類時，知道你需要做什麼來告訴你如何構造它。例如：在這裏，Stubbing運作良好：

class Node: 
    """A vertex of an n-adic tree""" 

    def __init__(self, name): 
     """since you used sentence, I assumed n-adic 
      but that may be wrong and then you might want 
      left and right children instead of a list or dictionary 
      of children""" 
     pass 

    def append_children(self, children): 
     """adds a sequence of child Nodes to self""" 
     pass 

    def create_child(self, name): 
     """creates a new Named node and adds it as a child""" 
     pass 

    def delete_child(self, name): 
     """deletes a named child from self or throws exception""" 
     pass 

依此類推。孩子需要訂購嗎？你有沒有需要刪除節點（和後代）？您是否可以預先製作一份兒童名單，或者您是否一次只能做一份。你真的想存儲一個事實，即節點是終端（這是多餘的），或者你想is_terminal()返回children is None？