#encoding=utf8
import sys
class Node():
'''结点'''
def __init__(self, number):
self.number = number
# 相连的其它结点
self.linked_nodes = []
def is_leaf(self):
'''判断是否是叶子结点'''
return len(self.linked_nodes) <= 1
class Tree():
'''树'''
def __init__(self, str_input):
'''创建新的树'''
# 结点数
self.n = 0
# 存储叶子结点,下标表示结点的数字
# 这样扫描一遍数组第一个非0元素就是
# 要删除的叶子结点
self.leaves = [0] * (50 + 1)
# 栈用于辅助解析字符串
stack = []
number = 0
for i in range(0, len(str_input)):
c = str_input[i]
if c == '(':
stack.append(c)
elif c == ' ':
continue
elif c == ')':
node1 = stack.pop()
# 弹出'('
stack.pop()
if len(stack) == 0:
if node1.is_leaf():
self.leaves[node1.number] = node1
break
# node2是node1的相连结点
node2 = stack[-1]
node1.linked_nodes.append(node2)
node2.linked_nodes.append(node1)
# 如果是叶子结点
if node1.is_leaf():
self.leaves[node1.number] = node1
# 数字
else:
if number == 0:
# 判断下一个字符是不是数字
if (str_input[i + 1].isdigit()):
number += 10 * int(c)
continue
else:
number = int(c)
new_node = Node(number)
stack.append(new_node)
number = 0
self.n += 1
else:
number += int(c)
new_node = Node(number)
stack.append(new_node)
number = 0
self.n += 1
def delete_min_leaf(self):
'''删除最小的叶子结点,并返回该节点的数字'''
for i in range(0, len(self.leaves)):
node = self.leaves[i]
if node != 0 and len(node.linked_nodes) == 1:
node.linked_nodes[0].linked_nodes.remove(node)
if (node.linked_nodes[0].is_leaf()):
self.leaves[node.linked_nodes[0].number] = node.linked_nodes[0]
number = node.linked_nodes[0].number
node.linked_nodes.pop()
return str(number)
if __name__ == '__main__':
for line in sys.stdin:
tree = Tree(line.strip('\n'))
for i in range(0, tree.n - 1):
sys.stdout.write(tree.delete_min_leaf())
if i != tree.n - 1 - 1:
sys.stdout.write(' ')
print ''
ZOJ Problem Set - 1097 Code the Tree Python 实现
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
推荐阅读更多精彩内容
- Day 12 神句文档 The team contends that these bear more than a...
- Given a binary treestruct TreeLinkNode {TreeLinkNode *lef...
- 动态规划题。思路就是暴力搜索,以每层为单位搜索,并且状态数目不多,把每一行的方格压缩为二进制编码。 Python代码:
- xxx is automatically signed for development, but a confli...
- AFHTTPSessionManager *manager =[AFHTTPSessionManager mana...