处理建立一个递归函数的字符串

Question

我有一个递归函数，打印一个字符串。 我想让函数返回它当前打印的字符串。

该代码基本上打印出不同层次的递归所需的字符串。

我正在考虑使用全局变量，但并不认为这听起来很pythonic。

我将多次调用此函数作为更大程序的一部分。

如果你想看看在当前的代码：

def check_if_multiple_sections(the_string): 
    level = 0 
    counter = 0 
    for char in the_string: 
     if char == '(': 
      level = level + 1 
      if level == 0: 
       counter = counter + 1 
     if char == ')': 
      level = level - 1 
      if level == 0: 
       counter = counter + 1 
    return counter 

def break_it_up(the_string): 
    level = 0 
    counter = 0 
    break_points = [] 
    for char in the_string: 
     if char == '(': 
      level = level + 1 
     if char == ')': 
      level = level - 1 
      if level == 0: 
       break_points.append(counter + 1) 
     counter = counter + 1 
    return break_points 


def recur_markov_change(the_string, key): 
    #print("the_string: " + str(the_string) + " : key: " +str(key)) 
    if key is not None: 
     #print(the_string) 
     #print("YEA") 
     print(str(the_string).split(' ')[0] +'^'+str(key) + ' ', end='') 
    else: 
     print('(TOP ', end ='') 
    key = ((the_string.split(' '))[0])[1:] 

    if len(the_string) < 2: 
     return 
    remaining_string = the_string.split(' ', 1)[1][:-1] 
    results = [] 
    results.append(((remaining_string.split(' '))[0])[1:]) 
    level = 0 
    counter = 0 
    if the_string.count('(') == 1: 
     items = the_string[1:-1] 
     both = items.split(' ') 
     print(str(the_string).split(' ',1)[1], end="") #This prints leaves 
     return 

    for char in remaining_string: 
     if char == '(': 
      level = level + 1 
     if char == ')': 
      level = level - 1 
     if level == 0 and char == ' ': 
      results.append(((remaining_string[counter+1:].split(' '))[0])[1:]) 
     counter = counter + 1 
    answer = (key, results, remaining_string) 
    #print(answer) 

    if check_if_multiple_sections(remaining_string) > 1: 
     break_points = break_it_up(remaining_string) 
     sublines = [] 
     prev_spot = 0 
     for breaks in break_points: 
      sublines.append(remaining_string[prev_spot:breaks].strip()) 
      prev_spot = breaks 
     sublines.append(remaining_string[breaks:].strip()) 
     for line in sublines: 
      if len(line) > 2: 
       print(' ', end='') 
       recur_markov_change(line, key) 
    print(')', end='') 


given_string = '(TOP (SBARQ (WHNP_WDT Which) (SQ_VP (VBZ is) (ADJP_JJ last))) (PUNC ?))' 
string_that_I_want_function_to_return = '(TOP (SBARQ^TOP (WHNP_WDT^SBARQ Which) (SQ_VP^SBARQ (VBZ^SQ_VP is) (ADJP_JJ^SQ_VP last))) (PUNC^TOP ?))' 

recur_markov_change(given_string, None) 
print("\ndesired string:") 
print(string_that_I_want_function_to_return) 

Answer 1

首先，我增加了一个基本字符串该函数递归地增加。我给这个initial打电话，然后我用inititial+=替换了所有打印件，最后返回initial。

def check_if_multiple_sections(the_string): 
    level = 0 
    counter = 0 
    for char in the_string: 
     if char == '(': 
      level = level + 1 
      if level == 0: 
       counter = counter + 1 
     if char == ')': 
      level = level - 1 
      if level == 0: 
       counter = counter + 1 
    return counter 

def break_it_up(the_string): 
    level = 0 
    counter = 0 
    break_points = [] 
    for char in the_string: 
     if char == '(': 
      level = level + 1 
     if char == ')': 
      level = level - 1 
      if level == 0: 
       break_points.append(counter + 1) 
     counter = counter + 1 
    return break_points 


def recur_markov_change(the_string, key, initial): 
    #initial+=("the_string: " + str(the_string) + " : key: " +str(key)) 
    if key is not None: 
     #initial+=(the_string) 
     #initial+=("YEA") 
     initial+=(str(the_string).split(' ')[0] +'^'+str(key) + ' ') 
    else: 
     initial+=('(TOP ') 
    key = ((the_string.split(' '))[0])[1:] 

    if len(the_string) < 2: 
     return 
    remaining_string = the_string.split(' ', 1)[1][:-1] 
    results = [] 
    results.append(((remaining_string.split(' '))[0])[1:]) 
    level = 0 
    counter = 0 
    if the_string.count('(') == 1: 
     items = the_string[1:-1] 
     both = items.split(' ') 
     initial+=(str(the_string).split(' ',1)[1]) #This initial+=s leaves 
     return initial 

    for char in remaining_string: 
     if char == '(': 
      level = level + 1 
     if char == ')': 
      level = level - 1 
     if level == 0 and char == ' ': 
      results.append(((remaining_string[counter+1:].split(' '))[0])[1:]) 
     counter = counter + 1 
    answer = (key, results, remaining_string) 
    #initial+=(answer) 

    if check_if_multiple_sections(remaining_string) > 1: 
     break_points = break_it_up(remaining_string) 
     sublines = [] 
     prev_spot = 0 
     for breaks in break_points: 
      sublines.append(remaining_string[prev_spot:breaks].strip()) 
      prev_spot = breaks 
     sublines.append(remaining_string[breaks:].strip()) 
     for line in sublines: 
      if len(line) > 2: 
       initial+=(' ') 
       initial = recur_markov_change(line, key, initial) 
    initial+=(')') 
    return initial 


given_string = '(TOP (SBARQ (WHNP_WDT Which) (SQ_VP (VBZ is) (ADJP_JJ last))) (PUNC ?))' 
string_that_I_want_function_to_return = '(TOP (SBARQ^TOP (WHNP_WDT^SBARQ Which) (SQ_VP^SBARQ (VBZ^SQ_VP is) (ADJP_JJ^SQ_VP last))) (PUNC^TOP ?))' 

print(recur_markov_change(given_string, None, "")) 
print("\ndesired string:") 
print(string_that_I_want_function_to_return) 

测试和工作就像一个魅力对我来说

Answer 2

...This would be impossible without recursion.., - 这是可能没有递归。

import collectons, operator 
s = '(TOP (SBARQ (WHNP_WDT Which) (SQ_VP (VBZ is) (ADJP_JJ last))) (PUNC ?))' 
result = '(TOP (SBARQ^TOP (WHNP_WDT^SBARQ Which) (SQ_VP^SBARQ (VBZ^SQ_VP is) (ADJP_JJ^SQ_VP last))) (PUNC^TOP ?))' 

我将使用一个类，Node，用自定义___str___方法。节点的有效负载将是其他节点或最内层的节点的字符串。

class Node: 
    def __init__(self, name, index): 
     self.name = name 
     self.index = index 
     self.parent = None 
     self._payload = [] 
    @property 
    def payload(self): 
     return self._payload 
    @payload.setter 
    def payload(self, thing): 
     self._payload.append(thing) 
    def __str__(self): 
     if self.parent is not None: 
      name = '{}^{}'.format(self.name, self.parent.name) 
     else: 
      name = self.name 
     #account for the extra space in a non-Node paylode 
     if not isinstance(self.payload[0], Node): 
      payload = ' ' + self.payload[0] 
     else: 
      payload = ' '.join(str(thing) for thing in self.payload) 
     return '({!s:} {!s:})'.format(name, payload) 

该函数首先查找所有左右侧包的索引。如果左paren后跟左paren，则未完成节点已创建。 当找到左/右paren对时，节点已完全解析（完成）。它返回最外层的节点。

def parse(s): 
    # Where are the parenthesis? 
    unfinished_nodes = collections.deque() 
    left, right = collections.deque(), collections.deque() 
    for i, c in enumerate(s): 
     if c == '(': 
      left.append(i) 
     if c == ')': 
      right.append(i) 

    if len(left) != len(right): 
     raise ValueError('Unbalanced parenthesis in s') 

    # helpers 
    paren = operator.itemgetter(0) 
    next_paren = operator.itemgetter(1) 

    while left and right: 
     while paren(left) > paren(right): 
      # back-up to previous Node 
      left.rotate() 
     #print('left:{}, right:{}'.format(paren(left), paren(right))) 
     # are we at the bottom? No more Nodes? 
     try: 
      if next_paren(left) < paren(left): 
       finished = True 
      else: 
       finished = paren(left) < paren(right) < next_paren(left) 
     except IndexError: 
      # only one more left paren - outermost Node 
      finished = True 
     if finished: 
      token = s[paren(left)+1:paren(right)] 
      #print('\ttoken:{}'.format(token)) 
      if '(' not in token: 
       # this is an inner Node 
       name, payload = token.split() 
       node = Node(name, paren(left)) 
       node.payload = payload 
       try: 
        node.parent = unfinished_nodes[-1] 
        node.parent.payload = node 
       except IndexError: 
        # this inner Node is the first Node in the sequence 
        pass 
       unfinished_nodes.append(node) 
      # finished is the outermost completely parsed node 
      finished = unfinished_nodes.pop() 
      #print('\tfinished:{!s:}'.format(finished.name)) 
      right.popleft() 
      left.popleft() 
      #print('\t\tL:{}\t\tR:{}'.format(left, right)) 
     else: 
      name = s[paren(left)+1:next_paren(left)] 
      name = name.strip() 
      node = Node(name, paren(left)) 
      try: 
       node.parent = unfinished_nodes[-1] 
       node.parent.payload = node 
      except IndexError: 
       # this is the outermost Node 
       pass 
      #print('\tnew Unfinished:{}'.format(node.name)) 
      unfinished_nodes.append(node) 
      # proceed to the next Node 
      left.rotate(-1) 
    return finished 
    #or if you prefer 
    #return str(finished) 

print(parse(s)) 
print(result) 

---

这被简化，没有任何有心计，非递归，一个传过来的输入字符串 - 快速，清洁，高效：

import collections 
def parse2(s): 
    parents = collections.deque() 
    final = collections.deque() 
    t = '' 
    new_parent = False 
    new = '' 
    for c in s: 
     if c == '(': 
      new_parent = True 
      t += c 
     elif c == ')': 
      t += c 
      final.append(t) 
      t = '' 
      parents.pop() 
     else: 
      if c == ' ' and new_parent: 
       if parents: 
        t = t + '^' + parents[-1] 
       parents.append(new) 
       new_parent = False 
       new = '' 
      elif new_parent: 
       new += c 
      t += c 
    return ''.join(final) 

不知道是什么促使我来第一个解决方案使用Node类，并将其视为树/图/任何类型。