A formula consisting of four fundamental arithmetic operations c an be expressed in a binary tree. Following diagram depicts a fo rmula “(9/(6-4))*3” in a binary tree. If an operator is in a pea k, the operator is applied using the result of the left subtree and result of right subtree.
Create a program outputting the calculation result of a formula
when a binary tree consisting of only the operators “+,-, *, /”
and positive integer is given. All operations are based on real
number operations. If the final result is not an integer, only t
he integer part is output. In the above, the calculation result
is 13.5, thus 13 is output.
[Constraints]
Total number of peaks N is 1≤N≤1000.
[Input]
In the first line of the input file, total number of peaks N(1≤N
≤1000) of the tree of each test case is given. The peak data are
given in the next n lines. If the peak is a number, the peak num
ber and the value are given. If the peak is an operator, the pea
k number, operator, peak number of left child and peak number of
right child are given in that order.
An integer between 1 ~ N is given as the peak number. There is n
o special rule for numbering the peak.However, the number of the
root peak is always 1.
The adjacent numbers or operators are all separated by the space.
In the above example, if the number 4 corresponds to the 7th pea
k, it is given “7 4”. If the operator ‘/’ corresponds to the 2nd
peak, it is given “2 / 4 5” since two child nodes are the 4th pe
ak with number 9 and 5th peak with operator ‘-‘.
Total of 10 test cases are given.
[Output]
Output the answer to each test case. Each line begins with ‘#x’,
and the answer is recorded after a line feed. Note that the answ
er is always recorded in an integer form.
