设计一个函数2

[编程题]设计一个函数2

热度指数：906 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

设计一个函数，传入一个可序列化为树结构的字符串，将含有多个子节点的节点以数组的形式输出。

输入描述:

{ node: 'root', next: [ { node: 'second_root' }, { node: 'second_child', next: [{ node: 'second_child_1', next: { node: 'second_child_1_1' } }, { node: 'second_child_2' }] }, { node: 'third_root', next: { node: 'third_child' , next: [{ node: 'third_child_1', next: { node: 'third_child_1_1' } }, { node: 'third_child_2' }] } } ] }

输出描述:

数组
输出规范
1）数组应被左右中括号括起；
2）数组的元素间由','相隔；
3）各节点在数组中的顺序应和其在输入中出现的次序一致；
4）节点名保证为不超过30个字符的字符串，仅含大小写字母、数字及下划线，输出时应用双引号括起；
5）输出的字符串不应有多余的空格。

示例1

输入

{ node: 'root', next: [ { node: 'second_root' }, { node: 'second_child', next: [{ node: 'second_child_1', next: { node: 'second_child_1_1' } }, { node: 'second_child_2' }] }, { node: 'third_root', next: { node: 'third_child' , next: [{ node: 'third_child_1', next: { node: 'third_child_1_1' } }, { node: 'third_child_2' }] } } ] }

输出

["root","second_child","third_child"]

算法知识视频讲解

Python

Kai201906292219250

"""

不知道哪错了，一直是93.33%的通过率，找不到问题在哪，求各位大神指明道路！

"""

import re

def find(s, result):
if "[" not in s:
return

node = re.search(r"'[a-z_0-9]*'", s, re.I)
_, start = node.span()
judge = re.match(r",next:\[", s[start:], re.I)
if judge:
result.append('"' + node.group()[1:-1] + '"')
find(s[start:], result)

if __name__ == "__main__":
s = input().replace(" ", "")
result = []
find(s, result)
print('[{}]'.format(','.join(result)))

发表于 2019-09-07 21:35:56 回复(0)

Python

ElonB

""""
字符串匹配和递归
{node: 'root', next:
    [{node: 'second_root'},
     {node: 'second_child', next:
         [{node: 'second_child_1', next:
             {node: 'second_child_1_1'}
           },
          {node: 'second_child_2'}
          ]
      },
     {node: 'third_root', next:
         {node: 'third_child', next:
             [{node: 'third_child_1', next:
                 {node: 'third_child_1_1'}
               },
              {node: 'third_child_2'}
              ]
          }
      }
     ]
 }
"""
import sys


def find_node(s, ans, dic):
    node = s[s.index("'") + 1:s.index("'") + 1 + s[s.index("'") + 1:].index("'")].strip()
    ans.append(node)  # 添加node名到ans列表中
    dic[node] = 0  # node的子节点
    if '{' not in s:  # 没有子节点
        return
    x = s.index('{')  # 至少一个子节点，记录递归的起始位置 x+1
    stack = []  # 栈用于符号配对，此题标准格式不需要验证符号是否匹配，只记录是否为空
    y = x
    for y in range(x, len(s)):
        if s[y] == '{':
            if not stack:
                x = y  # 记录递归的起始位置
            stack.append(s[y])
        elif s[y] == '}':
            stack.pop()
            if not stack:  # 栈空则，dic[node]加一，且对字符串 s[x + 1:y] 递归
                dic[node] += 1
                find_node(s[x + 1:y], ans, dic)


if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    s = input().strip()
    ans = []  # 按输入顺序记录所有节点
    dic = {}  # 记录node有几个子节点
    find_node(s[1:-1], ans, dic)
    res = []  # 符合多个子节点要求的所有节点
    flag = False
    for c in ans:
        if dic[c] >= 2:
            res.append('"' + c + '"')
    print("[{0}]".format(','.join(res)))

编辑于 2019-07-14 20:25:01 回复(0)