INPUT FILE: eval.in
OUTPUT FILE: eval.out
Often an expression in regular mathematical notation, such as 5 * (4 + 3), involves one or more pairs of parentheses which make evaluation difficult. However, when expressed as a binary tree no parentheses are needed and evaluation can be done straightforwardly. In our example we have
* / \ 5 + / \ 4 3
You cannot multiply the 5 without first evaluating 4 + 3.
Your task is to evaluate such an expression, given the entries in the binary tree.
INPUT
The input file contains 5 data sets.
The first line of each data set contains N, the number of levels in the binary
tree (1 <= N <= 10)
The next N lines of the data set contain the elements on each of the N levels
of the tree, in left-to-right order.
Each element will be either one of the operators *, + or - or one of the numbers
from 1 to 9 inclusive.
The tree is guaranteed to be valid; that is, each operator has two children
and each number has none. Furthermore, we guarantee that at no point in the
evaluation will a number obtained by evaluating a subtree be outside the range
-32000..32000.
OUTPUT
Evaluate the given binary tree and output its result.
Sample Input File
3 * 5 + 4 3 3 * * * 1 2 3 4
(and 3 more inputs)
Output for Sample Input
35 24