Verificació de evaluate S11834

Considera la següent funció:

/* @pre  t és un arbre no buit que representa una expressió 
 *       aritmètica correcta sobre els naturals i 
 *       els operadors +, -, *.
 * @post Retorna l'avaluació de l'expressió representada per t.
 */
int evaluate(BinTree<string> t) {
 int eval = 0;
 if (isNumber(t.value())) {
  eval = mystoi(t.value());
 } else {
  int auxl = evaluate(t.left());
  int auxr = evaluate(t.right());
  if (t.value() == "+") {
   eval = auxl + auxr;
  } else if (t.value() == "-") {
   eval = auxl - auxr;
  } else if (t.value() == "*") {
   eval = auxl * auxr;
  }
 }
 return eval;
}

Recorda que la funció isNumber retorna un booleà segons si el string d’entrada representa un enter o no. La funció mystoi converteix un string que representa un enter, en un enter.

Pregunta 1
Demostra que el cas bàsic és correcte. És a dir, demostra que si l’arbre d’entrada compleix la precondició i també la condició isNumber(t.value()) de l’if, aleshores el resultat que es retorna compleix la postcondició.

Pregunta 2
Escriu les hipòtesis d’inducció (HI) per al cas recursiu.

Pregunta 3
Demostra la correcció de l’algorisme en el cas en què l’arbre d’entrada t tingui a l’arrel el símbol +, - o *, utilitzant la HI.

Pregunta 4
Demostra que l’algorisme acaba. Dona una funció de cota i mostra les seves propietats.

Observació

El fitxer a enviar ha de ser un .tar dins del qual hi hagi un fitxer de text respuestas.txt amb les respostes a les preguntes. (El veredicte del Jutge sempre serà verd, perquè les respostes s’avaluaran manualment.)