68 - ZOJ Monthly, July 2008 - 1007
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:
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.
CL -> PS 1 2 2 3 2 2 4 5 3 1 6 -1 PP -> PD 1 2 4 5 3 6 -1 4 5 2 6 3 1 -1 PL -> PC (1 (2 (4) (5)) (3 (6)))
1 -1 2 1 4 2 5 2 3 1 6 3 -1 1 0 2 1 4 2 5 2 3 1 6 2 -1 1 (2 (4, 5), 3 (6))
The tree all the samples represent is:
Author: XIAO, Dong