Avalua expressió general W28242

En aquest exercici considerarem arbres generals que representen expressions sobre els operadors +, *, i -, amb operands enters. Per exemple, el següent arbre

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

representa l’expressió $(1 \cdot 2 \cdot 3) + (- 5 + 1 + 6) + 2$. Els nodes d’aquest arbre poden ser enters o operadors. Quan són operadors, els fills del node són els operands. Quan són operands, no tenen fills.

L’operador ’-’ és la resta, i té dues interpretacions, en funció del nombre d’operands. Si té un sol operand, és un canvi de signe. Per exemple, l’arbre:

-
'-- 5

és l’expressió $-5$. Si té més d’un operand, es comporta com una resta de la forma $(n_1 - n_2 - \cdots - n_k)$, és a dir, que el primer operand es pren amb el seu valor, i els següents operands es resten del primer. Per exemple, l’arbre:

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

és l’expressió $(10 - 2 - 5 - 1)$ que s’avalua a 2.

Implementeu, doncs, la funció següent:

/**
 * @brief Avalua un arbre general no buit que representa una expressió.
 *
 * @pre L'arbre és no buit i l'expressió és correcta.
 *
 * @param t Arbre que representa l'expressió.
 * @return Resultat de l'avaluació de l'expressió.
 */
int eval_expression(Tree<string> t);

Observació

Els fitxers públics (icona del gatet) contenen:

El mòdul util defineix les funcions is_number i string_to_int, per simplificar la discriminació entre operands i valors i per fer la conversió dels operands de strings a enters.

Cal implementar eval_expression en un fitxer .cc nou, compilar, i finalment enviar només el fitxer amb la funció.

Entrada

(D’això s’encarrega el programa principal). L’entrada és una seqüència d’arbres generals en format visual.

Sortida

(D’això també s’encarrega el programa principal). La sortida són els strings resultants de cridar la funció eval_expression, un resultat per línia.