Welcome to ZOJ
68 - ZOJ Monthly, July 2008 - 1007
Tree Format Converter

Time Limit: 2 Seconds      Memory Limit: 32768 KB

In computer science, a tree is a widely-used data structure, and there're a lot of problems dealing with trees in programming contests. However, tree is not a data structure like array which can be represented easily in the input text (just a sequence of elements with its size or a terminator). Instead, it is a graphic structure and can be represented by text in many different ways. Each problem with trees just choose one of them as input format, thus result in some problems: if you've solved a problem with a specific input format, and meet another problem which requires the same algorithm but uses a different input format, maybe you have to write a completely new program to work with the new format. That's obviously a waste of time. Your task here is just write a tree format converter that can convert a tree format into another. For simplicity, we just deal with rooted trees here, and use terminator (-1) instead of size for some formats since other formats do not require such information and thus there's no need to record the size of the tree. There're six formats that your program should handle here:

  • Children list (CL): There's a line for the root and each internal node, each begins with the node number and the size of its children, then a list of its children's numbers followed. All those lines are listed in preorder of the node they specify. A line of -1 terminates a tree.

  • Parent sequence (PS): There's a line for each node with two integers: the node number and its parent's number. All nodes are listed in preorder, the parent's number of the root is -1 since it has no parent. A line of -1 terminates a tree.

  • Preorder and postorder sequences (PP): Just two lines of node numbers terminated by -1. The node numbers in the first line are listed in preorder, and those in the second line are listed in postorder.

  • Preorder and depth sequence (PD): There's a line for each node with two integers: the node number and its depth. All nodes are listed in preorder. A line of -1 terminates a tree.

  • Parentheses language (PL): The grammar of this language is:

    T ::= "(" N S ")"
    S ::= " " T S
        | empty
    N ::= node number

    That is, trees have parentheses around them, and node numbers of the roots, followed by arbitrarily many (maybe none) subtrees separated by single space character. For example: (1 (2 (4) (5)) (3 (6)))

  • Parentheses and commas (PC): A tree is begin with the node number of its root, and all its subtrees (if any) are listed inside a pair of parentheses and separated by commas. There's a space before each left parenthesis and after each comma. For example: 1 (2 (4, 5), 3 (6))


Each test case begins with a line with the format "XX -> YY", where XX is the two-letter abbreviation of the source format, and YY is the abbreviation of the target name. Then followed a description of a non-empty tree in the source format. All node numbers are distinct non-negative integers less than 32768.

There's a blank line between every two test cases, processing to the end of file.


For each test case, you should print the tree in the target format. And print a blank line between every two test cases.

Sample Input

CL -> PS
1 2 2 3
2 2 4 5
3 1 6

PP -> PD
1 2 4 5 3 6 -1
4 5 2 6 3 1 -1

PL -> PC
(1 (2 (4) (5)) (3 (6)))

Sample Output

1 -1
2 1
4 2
5 2
3 1
6 3

1 0
2 1
4 2
5 2
3 1
6 2

1 (2 (4, 5), 3 (6))

The tree all the samples represent is:

Author: XIAO, Dong

Submit    Status