Binary Expression Tree
By Neilor Tonin, URI 
Brazil
Timelimit: 2
Brazil BrazilA binary expression tree or Arithmetic Expression Binary Tree is a specific application of a binary tree to evaluate expressions. It can be used to represent an algebraic and boolean expression, like the expression 4 * a - ( 6 + b ) + 8 / ( 9 - 7 ) presented in the figure below.
These trees can represent expressions that contain both unary and binary operators. Expression trees have been implemented as binary trees mainly because binary trees allow their user to quickly find what he is looking for.
The upper limit of steps necessary to find required information in binary trees equals to log2N, where N denotes the number of all nodes in a tree.
In order to make an different exercise, the professor ask you to list an expression stored in a binary tree, level by level, from level zero to level n.
The input contains several test cases. Each test case consists of an arithmetic expression containing from two operands and a simple operation up to 100 elements. This expression can contain uppercase letters, lowercase letters, digits, parentheses, and basic arithmetic operations (+, -, *, /) as shown below. Each operand can have only one digit ('0'-'9') or letter ('a', 'B', etc). The end of input is indicated by the end of file (EOF).
For each test case, your program must print several lines corresponding to the levels of the expression tree and containing all the elements present in each one of these levels from left to right. These lines must begin always with the message "Nivel n: ", formatted as presented in the example given below. Print a blank line between two test cases.
| Sample Input | Sample Output |
|
4 * a - ( 6 + b ) + 8 / ( 9 - 7 ) |
Nivel 0: + |