提示: 欢迎访问OurACM平台。
Problem 1512 Syntax Tree

Accept: 185    Submit: 568
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Oaiei is now studying Compiler Principles. He finds that compilers must convert each of the statement into a syntax tree for analysis.

A syntax tree is a binary tree. Its leaf node is a variable or is a numerical and each internal node is an operator.

Now your task is, given a syntax tree, convert it into a statement.

Each leaf node is only a letter (a-z or A-Z) or a number (0-9). Operators can only be one of =, +, -, x, / and %.

It’s simple, isn’t it?

Input

The input consists of several test cases. For each case, the first line has an integer n (1<=n<=101), indicating the number of nodes in the given syntax tree, nodes are numbered 1, 2, ..., n. Next n lines, each line consists of three integers A,B,C, indicating the node numbered A has a left child numbered B, a right child numbered C. 0 indicates the node doesn’t have a left or right child. Following C, there is a character D, indicating the value of the node. All nodes are given in layer order.

Output

The statement after coverting the syntax tree. No blanks allowed. (The conversion order is left subtree first and then right subtree)

Sample Input

7 1 2 3 = 2 0 0 a 3 4 5 + 4 0 0 b 5 6 7 + 6 0 0 c 7 0 0 d

Sample Output

a=b+c+d

Source

FOJ月赛-2007年6月

Submit  Back  Status  Discuss