ARBRE X64750

En aquest exercici considerarem arbres que tenen en els seus nodes els operands +,-,*, i valors numèrics. Per exemple, l’arbre -(+(+(5,2),-(3,4)),-(5,1)). També considerarem un valor independent que haurà de ser buscat a l’arbre.

EXERCICI:

Implementeu una funció que, donat un arbre binari de valors i els operands +,-,*, retorna el nivell en que es troba el numero buscat per primera vegada,comptant que l’arrel és el nivell 0, si aquest valor no està a l’arbre, ha de retornar -1 . Aquesta és la capçalera:

// 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.
// Post: Retorna el nombre de subarbres de t que s'avaluen a x.

int numberSubtreesEvaluateToParam(const BinaryTree<string> &t, int x){

Aquí tenim un exemple de paràmetre d’entrada de la funció i la corresponent sortida: int numberSubtreesEvaluateToParam(-(+(+(5,2),-(3,4)),-(5,1)), 6) = -1

Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: Makefile, program.cpp, BinaryTree.hpp,numberSubtreesEvaluateToParam.hpp, utils.hpp, utils.cpp. Us falta crear el fitxer numberSubtreesEvaluateToParam.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 numberSubtreesEvaluateToParam.cpp

Entrada

L’entrada té un nombre arbitrari de casos. Cada cas consisteix en una línia amb un string descrivint un arbre binari d’strings i també un valor independent que haurà de ser buscat a l’arbre. 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 Aqui teniu un exemple:

-(*(-(10,5),8),+(+(13,5),+(7,3)))
8

Sortida

Per a cada cas, la sortida conté el corresponent numero de nodes que es visita per trobar per primera vegada el valor que cal cercar dins de l’arbre. Fixeu-vos en que el programa que us oferim ja s’encarrega d’escriure aquest valor. Només cal que implementeu la funció abans esmentada. Aqui teniu la sortida esperada del programa anterior:

2