Avaluar expressions amb divisió X43096

INTRODUCCIÓ:

En aquest exercici considerarem arbres que representen expressions sobre els operadors +,-,*,/, i sobre operands naturals. Per exemple, l’arbre -(+(3,/(4,2)),5) representa l’expressió 3+4/2-5.

Alhora d’avaluar una divisió, interpretem la divisió entera que ens ofereix C++. Noteu que, en particular, (−5)/2=−2, contradient la definició que trobem habitualment en llibres de matemàtiques.

Noteu també que la divisió per 0 no està definida, i això ho haurem de tenir en compte en resoldre l’exercici.

EXERCICI:

Implementeu una funció que, donat un arbre binari d’strings que representa una expressió correcta sobre naturals i operadors +,-,*,/, retorna la seva avaluació i un indicador de si s’ha produït un error de divisió per 0, tot mitjançant paràmetres per referència. Aquesta és la capcelera:

// Pre:  t és un arbre no buit que representa una expressió correcta
//       sobre els naturals i els operadors +,-,*,/.
//       Les operacions no produeixen errors d'overflow,
//       però poden produïr error de divisió per 0.
// Post: Si l'avaluació de l'expressió representada per t no produeix errors de divisió per 0, 
//       llavors 'result' val l'avaluació d'aquesta expressió i 'error' val 'false'.
//       En cas contrari, 'error' val 'true', i el valor de 'result' és irrellevant.
void evaluate(const BinaryTree<string> &t, int &result, bool &error);

Aquí tenim un exemple de paràmetre d’entrada de la funció i la corresponent sortida:

evaluate(/(+(1,2),-(5,2)), result, error) produces result=1, error=false

Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: Makefile, program.cpp, BinaryTree.hpp, evaluate.hpp, utils.hpp, utils.cpp. Us falta crear el fitxer evaluate.cpp amb els corresponents includes i implementar-hi la funció anterior. Valdrà la pena que utilitzeu algunes de les funcions oferides a utils.hpp. Quan pugeu la vostra solució al jutge, només cal que pugeu un tar construït així:

tar cf solution.tar evaluate.cpp

Entrada

L’entrada té un nombre arbitrari de casos. Cada cas consisteix en una línia amb un string describint un arbre binari d’strings. Fixeu-vos en que el programa que us oferim ja s’encarrega de llegir aquestes entrades. Només cal que implementeu la funció abans esmentada.

Sortida

Per a cada cas, la sortida conté la corresponent avaluació de l’arbre o bé una indicació de que s’ha produït un error de divisió per 0 durant el procès d’avaluar l’arbre. Fixeu-vos en que el programa que us oferim ja s’encarrega d’escriure aquesta avaluació. Només cal que implementeu la funció abans esmentada.