Árboles de expresiones aritméticas

La forma habitual de escribir operaciones aritméticas es situar el operador entre sus dos operandos con la citada notación infija. Esta forma de notación obliga en muchas ocasiones a utilizar paréntesis para indicar el orden de la evaluación

A*B/(A+C)      A*B/A+C
(A-B)^C+D     A-B^C+D

La notación en la que el operador se coloca delante de los operadores, notación prefija, se conoce como notación polaca (En honor del matemático polaco que la estudió).

A*B/(A+C) (infija)       A*B/+AC      *AB/+AC       /*AB+AC (polaca)
A*B /A+C (infija)        *AB/A+C       /*ABA+C      +/*ABAC (polaca)
(A-B)^C+D (infija)      -AB^C+D       ^-ABC+D      +^-ABCD (polaca)

Podemos observar que no es necesaria la utilización de paréntesis al escribir la expresión en notación polaca. La propiedad fundamental de la notación polaca es que el orden en que se van a realizar las operaciones está determinado por las posiciones de los operadores y los operandos en la expresión.

Otra forma de escribir las operaciones es mediante la notación postfija o polaca inversa que coloca el operador a continuación de sus operandos

A*B/(A+C) (infija)       A*B/AC+       AB*/AC+       AB*AC+/ (polaca inversa)
A*B /A+C (infija)        AB*/A+C       AB*A/+C       AB*A/C+ (polaca inversa)
(A-B)^C+D (infija)      AB-^C+D       AB-C^+D       AB-C^D+ (polaca inversa)

Su tarea es escribir un programa que a partir de la notación infija, polaca y polaca inversa dibuje el árbol binario correspondiente a la expresión utilizando btreepic (8pts).

Ejemplo:

Dada la expresión:

       Sus notaciones son:

Infija = (3*x^2+2*x*y^2+8*y^3)/(8*x^3+3*x^2*y^2)

Polaca = /++*3^x2**2x^y2*8^y3+*8^x3**3^x2^y2

Polaca inversa = 3x2^*2x*y2^*+8y3^*+8x3^*3y2^*y2^*+/

El árbol binario correspondiente es:

Al dibujar el árbol se debe mostrar por consola la altura del árbol, la longitud del camino interno y la cardinalidad (4pts).

Una vez que se halla construido el árbol binario a partir de el genere un archivo de texto con la notación de Deway para el árbol m-ario correspondiente a la expresión aritmética (8pts).

Ejemplo: para el árbol anterior, el correspondiente m-ario es:

Obs: para llevar de el binario al m-ario, basta con ignorar hijos que sean operadores y que tengan el mismo valor que el padre, en cuanto al descenso de nivel.

Formato de la entrada

La entrada consiste en un único caso de prueba, que contiene tres líneas, cada una con la notación infija, polaca y polaca inversa de la expresión aritmética, la expresión consta de operadores de suma, resta, multiplicación, división y potencia, los operándoos son números entre 0 y 9 y letras minúsculas o mayúsculas.

Ejemplo:

(3*x^2+2*x*y^2+8*y^3)/(8*y^3+3*y^2*y^2) /++*3^x2**2x^y2*8^y3+*8^x3**3^x2^y2 3x2^*2x*y2^*+8y3^*+8x3^*3y2^*y2^*+/

Formato de la salida:

Aparte del dibujo utilizando btreepic y las salidas por consola, se debe generar un archivo de salida que contenga la notación de Deway del árbol m-ario correspondiente:

Ejemplo

1:/ 1.1:+ 1.1.1:* 1.1.1.1:3 1.1.1.2:^ 1.1.1.2.1:x 1.1.1.2.2:2 1.1.2:* 1.1.2.1:2 1.1.2.2:x 1.1.2.3:^ 1.1.2.3.1:y 1.1.2.3.2:2 1.1.3:* 1.1.3.1:8 1.1.3.2:^ 1.1.3.2.1:y 1.1.3.2.2:3 1.2:+ 1.2.1:* 1.2.1.1:8 1.2.1.2:^ 1.2.1.2.1:x 1.2.1.2.2:3 1.2.2:* 1.2.2.1:3 1.2.2.2:^ 1.2.2.2.1:x 1.2.2.2.2:2 1.2.2.3:^ 1.2.2.3.1:y 1.2.2.3.2:2

Reto:

Cuando se representa una expresion aritmética utilizando un árbol binario, muchas veces se desperdicia espacio en memoria en el momento de la implementación, puesto que si hay subexpresiones comunes, se utiliza espacio para representar cada una de sus ocurrencias. En ese caso, se podría pensar en compartir la memoria que las representa, con el fin de ahorrar espacio. Por ejemplo si se tiene la expresión: (x+y+z*a)^2 +(x+y+z*a)^3+(x+y+z*a)^4+(x+y+z*a)^5, su árbol de expresión podria ser:

pero si comparten las subexpresiones comunes, se tendría algo como:

Desarrolle una función que modifique la estructura de la representación de un árbol de expresiones, utilizando la idea anunciada anteriormente.