Evalúa expresión general W28242

En este ejercicio consideraremos árboles generales que representan expresiones sobre los operadores +, *, y -, con operandos enteros. Por ejemplo, el siguiente árbol

+
|-- *
|   |-- 1
|   |-- 2
|   '-- 3
|-- +
|   |-- -
|   |   '-- 5
|   |-- 1
|   '-- 6
'-- 2

representa la expresión $(1 \cdot 2 \cdot 3) + (- 5 + 1 + 6) + 2$. Los nodos de este árbol pueden ser enteros u operadores. Cuando son operadores, los hijos del nodo son los operandos. Cuando son operandos, no tienen hijos.

El operador ’-’ es la resta, y tiene dos interpretaciones, en función del número de operandos. Si tiene un solo operando, es un cambio de signo. Por ejemplo, el árbol:

-
'-- 5

es la expresión $-5$. Si tiene más de un operando, se comporta como una resta de la forma $(n_1 - n_2 - \cdots - n_k)$, es decir, que el primer operando se toma con su valor, y los siguientes operandos se restan del primero. Por ejemplo, el árbol:

-
|-- 10
|-- 2
|-- 5
'-- 1

es la expresión $(10 - 2 - 5 - 1)$ que se evalúa a 2.

Implementad, pues, la función siguiente:

/**
 * @brief Evalúa un árbol general no vacío que representa una expresión.
 *
 * @pre El árbol es no vacío y la expresión es correcta.
 *
 * @param t Árbol que representa la expresión.
 * @return Resultado de la evaluación de la expresión.
 */
int eval_expression(Tree<string> t);

Observación

Los ficheros públicos (icono del gatito) contienen:

El módulo util define las funciones is_number y string_to_int, para simplificar la discriminación entre operandos y valores y para hacer la conversión de los operandos de strings a enteros.

Hay que implementar eval_expression en un fichero .cc nuevo, compilar, y finalmente enviar solo el fichero con la función.

Entrada

(De esto se encarga el programa principal). La entrada es una secuencia de árboles generales en formato visual.

Salida

(De esto también se encarga el programa principal). La salida son los strings resultantes de llamar la función eval_expression, un resultado por línea.