ZOJ Problem Set - 1097 Code the

#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 ''