[JAVA] valutare una espressione aritmetica usando alberi binari

[rubikk]

Salve a tutti, per un corso di Java ho dovuto sviluppare implementazioni di alberi binari e cammini euleriani per attraversarli.
Dal momento che la classe che implementa il cammino euleriano è una classe astratta ne ho anche dovute creare alcune che ne "sovrascrivano" (non riesco a trovare una traduzione migliore di override ) i metodi astratti. Lo scopo di tali classi è di prendere un albero binario che contiene una espressione aritmetica (gli operatori nei nodi interni e gli operandi nelle foglie), calcolarne il risultato e stamparla.

Questa è la classe EulerTour:

import eccezioni.BoundaryViolationException;
import eccezioni.EmptyTreeException;
import eccezioni.InvalidPositionException;
import interfacce.BinaryTree;
import interfacce.Position;

/**
 * 

Title: EulerTour.java</p>
 *
 * 

Description: implementazione di Euler Tour mediante il template method pattern. Questo consiste nel definire
 * 					un meccanismo di computazione generico che puo' essere specializzato da una particolare applicazione
 * 					ridefinendone alcuni passaggi. L'attraversamento ricorsivo è eseguito dal metodo eulerTour, mentre 
 * 					i metodi ausiliari che eulerTour chiama sono dei "place holders" vuoti. La classe EulerTour è astratta
 * 					e non puo' essere istanziata. Contiene metodi astratti che devono essere specificati nelle sottoclassi
 * 					concrete di EulerTour.</p>
 * 					

EulerTour rappresenta una sorta di unificazione dei diversi metodi di attraversamento di un albero
 * 					visti finora. Mentre questi prevedevano che i nodi venissero visitati al più una volta, l'"
 * 					Euler tour traversal prevede che questo requisito venga rilassato. Il vantaggio è che questo permette
 * 					a algoritmi più generali di essere espressi con facilità. L'attraversamento mediante cammino euleriano 
 * 					di un albero T si puo' vedere informalmente come una "passeggiata" attorno a T, partendo dalla radice verso
 * 					il suo figlio sinistro, e considerando i bordi di T come "muri" da tenere sempre alla propria sinistra.
 * 					Ogni nodo v di T viene incontrato tre volte:
 * 					[/list]
 * 					[*]"Da sinistra" (prima dell'Euler tour del sottoalbero sinistro di v)
 * 					[*]"Dal basso" (tra l'Euler tour dei due sottoalberi di v)
 * 					[*]"Da destra" (dopo l'Euler tour del sottoalbero destro di v)
 * 					[/list]
 * 					Se v è un nodo esterno, le visite avvengono tutte allo stesso momento.</p>
 * 					

Euler tour estende i cocetti di attraversamento inorder, preorder e postorder. L'attraversamento 
 * 					preorder di un albero binario si puo' vedere come un Euler tour traversal tale che ogni nodo ha una azione associata alla 
 * 					visita che viene eseguita solo queno il nodo è incontrato sulla sinistra. Allo stesso modo gli attraversamenti
 * 					inorder e postorder di un albero binario sono equivalenti a Euler tour tali che ogni odo ha una azione associata
 * 					alla visita che viene eseguita solo quando il nodo viene incontrato dal basso o da destra rispettivamente.</p>
 * 
 *
 *
 */

public abstract class EulerTour<E,R> {
	
	protected BinaryTree<E> tree;
	
	/**esegue l'attraversamento; questo metodo astratto deve essere specificato in una sottoclasse concreta
	 * @throws EmptyTreeException */
	public abstract R execute(BinaryTree<E> T) throws EmptyTreeException;
	
	/**inizializza l'attraversamento*/
	protected void init(BinaryTree<E> T) {
		tree = T;
	}
	
	/**Template Method*/
	protected R eulerTour(Position<E> v) {
		TourResult<R> r = new TourResult<R>();
		try {
			visitLeft(v, r); 						//visita da sinistra.
			if (tree.hasLeft(v)) 					//scende al figlio sinistro di v.
				r.left = eulerTour(tree.left(v));	//attraversamento ricorsivo dei figli sinistri di v; salva nel campo left di r i risultati.
			visitBelow(v, r); 						//visita dal basso.
			if (tree.hasRight(v)) 					//scende al figlio destro di v.
				r.right = eulerTour(tree.right(v)); //attraversamento ricorsivo dei figli destri di v; salva nel campo right di r i risultati.
			visitRight(v, r);						//visita da destra.
		
		} catch (InvalidPositionException e) {
			e.printStackTrace();
		} catch (BoundaryViolationException e) {
			e.printStackTrace();
		} 							
		return r.out;	
	}
	
	//METODI AUSILIARI; possono essere ridefiniti in sottoclassi in maniera da eseguire operazioni specifiche
	/**metodo invocato per la visita a sinistra*/
	protected void visitLeft(Position<E> v, TourResult<R> r) { }
	
	/**metodo invocato per la visita dal basso*/
	protected void visitBelow(Position<E> v, TourResult<R> r) { }
	
	/**metodo invocato per la visita a destra*/
	protected void visitRight(Position<E> v, TourResult<R> r) { }
}

I valori delle chiamate ricorsive vengono salvati nei campi di un oggetto TourResult definito come segue:

/**
 * 

Title: TourResult.java</p>
 *
 * 

Description: implementazione di un oggetto che tiene traccia dei 
 * 					risultati delle chiamate ricorsive a EulerTour.</p>
 * 					

I campi left e right tengono traccia delle chiamate 
 * 					di EulerTour sui figli destro e sinistro del nodo v 
 * 					rispettivamente, mentre out tiene traccia del valore
 * 					computato dalla chiamata di EulerTour su v.</p>
 *
 *
 */

public class TourResult<R> {
	
	public R left;
	public R right;
	public R out;
	
	/**costruttore; inizializza un oggetto TourResult vuoto*/
	public TourResult() {
		left = null;
		right = null;
		out = null;
	}

}

E di seguito ci sono le classi EvaluateExpressionTour e PrintExpressionTour che dovrebbero svolgere i calcoli:

import eccezioni.EmptyTreeException;
import eccezioni.InvalidPositionException;
import interfacce.BinaryTree;
import interfacce.Position;

/**
 * 

Title: EvaluateExpressionTour.java</p>
 *
 * 

Description: è una specializzazione di EulerTour, mediante la quale è possibile
 * 					calcolare l'espressione aritmetica salvata in un albero binario.</p>
 * 					</p>La classe "sovrascrive" il metodo ausiliario visitRight, facendogli
 * 					eseguire i seguenti calcoli:
 * 					<ul>
 * 					[*]Se v è un nodo esterno, setta <code>r.out</code> al valore della 
 * 						variabile memorizzata in v.
 * 					[*]Se v è un nodo interno, combina <code>r.left</code> e <code>r.right</code>
 * 						con l'operatore contenuto in v e setta <code>r.out</code> al risultato 
 * 						dell'operazione.
 * 					[/list]</p>
 *
 *
 */

public class EvaluateExpressionTour extends EulerTour<ExpressionTerm, Integer> {

	/**esegue l'attraversamento*/
	public Integer execute(BinaryTree<ExpressionTerm> T) {
		Integer toReturn = 0;
		
		init(T); //chiama il metodo della superclasse
		try {
			toReturn = eulerTour(tree.root()); //restituisce il valore dell'espressione
		} catch (EmptyTreeException e) {
			e.printStackTrace();
		}
		return toReturn;
	}
	
	/**esegue il calcolo dell'espressione durante la visita a destra dei nodi*/
	protected void visitRight(Position<ExpressionTerm> v, TourResult<Integer> r) {
		ExpressionTerm term = null;
		ExpressionOperator op = null;
		
		try {
			term = v.element();		
			if (tree.isInternal(v)) {
				op = (ExpressionOperator) term;
				op.setOperands(r.left, r.right);
			}
			r.out = term.getValue();
		} catch (InvalidPositionException e) {
			e.printStackTrace();
		}
	}
}

import eccezioni.EmptyTreeException;
import eccezioni.InvalidPositionException;
import interfacce.BinaryTree;
import interfacce.Position;

/**
 * 

Title: PrintExpressionTour.java</p>
 *
 * 

Description: è una specializzazione di EulerTour, mediante la quale è possibile
 * 					stampare l'espressione aritmetica salvata in un albero binario.</p>
 * 					</p>La classe "sovrascrive" i metodi ausiliari visitLeft, visitBelow 
 * 					e visitRight, facendogli eseguire le seguenti operazioni:
 * 					<ul>
 * 					[*]Durante la visita a sinistra, se v è un nodo interno stampa "(".
 * 					[*]Durante la visita dal basso stampa il valore di v.
 * 					[*]Durante la visita a destra, se v è un nodo interno stampa ")".
 * 					[/list]</p>
 *
 *
 */

public class PrintExpressionTour extends EulerTour<ExpressionTerm, String> {

	/**esegue l'attraversamento*/
	public String execute(BinaryTree<ExpressionTerm> T){
		init(T);
		System.out.print("Espressione: ");
		try {
			eulerTour(T.root());
		} catch (EmptyTreeException e) {
			e.printStackTrace();
		}
		System.out.println();
		return null; 
	}
		
	/**esegue l'attraversamento a sinistra*/
	protected void visitLeft(Position<ExpressionTerm> v, TourResult<String> r){
		try {
			if (tree.isInternal(v)) 
				System.out.print("(");
		} catch (InvalidPositionException e) {
			e.printStackTrace();
		} 	
	}
	
	/**esegue l'attraversamento a destra*/
	protected void visitBelow(Position<ExpressionTerm> v, TourResult<String> r){ 
		try {
			System.out.print(v.element());
		} catch (InvalidPositionException e) {
			e.printStackTrace();
		} 
	}
	
	/**esegue l'attraversamento dal basso*/
	protected void visitRight(Position<ExpressionTerm> v, TourResult<String> r){
		try {
			if (tree.isInternal(v)) 
				System.out.print(")");
		} catch (InvalidPositionException e) {
				e.printStackTrace();
		} 
	} 		
}

Esistono poi diverse classi ausiliarie che hanno lo scopo di fornire una rappresentazione di operatori e variabili (se necessario posso postare anche quelle).

Il problema è che durante il test la parentesizzazione dell'espressione risulta corretta, mentre operatori e variabili non vengono utilizzati come dovrebbero... vi faccio un esempio.
Data questa classe di test:

import eccezioni.InvalidPositionException;
import eccezioni.NonEmptyTreeException;
import interfacce.Position;
import tree.LinkedBinaryTree;

public class EvaluateExpressionTourTest {

	public static void main(String[] args) throws NonEmptyTreeException, InvalidPositionException {
	
		PrintExpressionTour exp = new PrintExpressionTour();
		EvaluateExpressionTour cal = new EvaluateExpressionTour();
		
		LinkedBinaryTree<ExpressionTerm> myTree = new LinkedBinaryTree<ExpressionTerm>();
		ExpressionTerm a = new AdditionOperator();
		ExpressionTerm m = new MultiplyOperator();
		ExpressionTerm f1 = new ExpressionVariable(5);
		ExpressionTerm f2 = new ExpressionVariable(10);
		ExpressionTerm f3 = new ExpressionVariable(10);
		ExpressionTerm f4 = new ExpressionVariable(2);
		
		Position<ExpressionTerm> root = myTree.addRoot(a);
		Position<ExpressionTerm> b = myTree.insertLeft(root, a);
		Position<ExpressionTerm> c = myTree.insertRight(root, m);
		myTree.insertLeft(b, f1);
		myTree.insertRight(b, f2);
		myTree.insertLeft(c, f3);
		myTree.insertRight(c, f4);
		
		exp.execute(myTree);
		System.out.println(" = " + cal.execute(myTree));
	}

il risultato che ottengo non è ((5+10)*(10+2)) ma ((5+5)+(5+5)).

Nonostante abbia passato ore sul debug non riesco a capire dov'è che le cose non funzionano e spero che qualcuno abbia la pazienza di darmi una mano. Ad ogni modo se dovessero servirvi altre informazioni ditemelo che aggiungo le altre parti del codice

[LeaderGL]

se ho capito bene l'operatore è in un nodo e nei suoi figli destro e sinistro gli operandi...giusto?

di conseguenza (5+10)*(10+2) diventerebbe:

           *
(5+10)          (10+2)

che a sua volta sarebbe:

                *
     +                     +
5        10         10         2

giusto? se non sto sbagliando niente il relativo codice non dovrebbe essere:

		Position<ExpressionTerm> root = myTree.addRoot(m);
		Position<ExpressionTerm> b = myTree.insertLeft(root, a);
		Position<ExpressionTerm> c = myTree.insertRight(root, a);
		myTree.insertLeft(b, f1);
		myTree.insertRight(b, f2);
		myTree.insertLeft(c, f3);
		myTree.insertRight(c, f4);

??

[rubikk]

Si, bravo, nei nodi gli operatori, nelle foglie gli operandi.

Per il resto hai ragione, ho sbagliato io a scrivere, il risultato dovrebbe essere ((5+10)+(10*2)), almeno questo è quello che il test vorrebbe che succedesse, mentre invece stampa ((5+5)+(5+5)), come se non riuscisse a visitare tutti i nodi o non so che, eppure apparentemente facendo il debug l'albero sembra essere stato creato correttamente.

Ecco, questo è il problema, spero sia chiaro e spero che qualcuno riesca a darmi una mano

[LeaderGL]

ciao,
quello che posso notare è che:

1) la classe EulerTour è dichiarata abstract ma non possiede metodi astratti:

public abstract class EulerTour<E,R> {
	...

	protected void visitLeft(Position<E> v, TourResult<R> r) { }
	
	/**metodo invocato per la visita dal basso*/
	protected void visitBelow(Position<E> v, TourResult<R> r) { }
	
	/**metodo invocato per la visita a destra*/
	protected void visitRight(Position<E> v, TourResult<R> r) { }
}

2) la classe che esegue le espressioni matematiche EvaluateExpressionTour non possiede l'implementazione dei metodi "visitLeft" e "visitBelow" (il compilatore non ti da errori xkè i metodi non sono abstract e quindi non è obbligatorio ri-definirli nella classe che estende EulerTour):

public class EvaluateExpressionTour extends EulerTour<ExpressionTerm, Integer> {

	/**esegue l'attraversamento*/
	public Integer execute(BinaryTree<ExpressionTerm> T) {
		Integer toReturn = 0;
		
		init(T); //chiama il metodo della superclasse
		try {
			toReturn = eulerTour(tree.root()); //restituisce il valore dell'espressione
		} catch (EmptyTreeException e) {
			e.printStackTrace();
		}
		return toReturn;
	}
	
	/**esegue il calcolo dell'espressione durante la visita a destra dei nodi*/
	protected void visitRight(Position<ExpressionTerm> v, TourResult<Integer> r) {
		ExpressionTerm term = null;
		ExpressionOperator op = null;
		
		try {
			term = v.element();		
			if (tree.isInternal(v)) {
				op = (ExpressionOperator) term;
				op.setOperands(r.left, r.right);
			}
			r.out = term.getValue();
		} catch (InvalidPositionException e) {
			e.printStackTrace();
		}
	}


	QUI MANCANO GLI ALTRI DUE METODI
	QUI MANCANO GLI ALTRI DUE METODI
	QUI MANCANO GLI ALTRI DUE METODI
}

spero di aver interpretato bene il tuo codice...

[rubikk]

Ciao LeaderGL, innanzitutto grazie per esserti interessato al problema

Allora, il metodo execute della classe EulerTour è definito come astratto, ed infatti viene poi implementato concretamente dalla classe EvaluateExpressionTour che chiama il metodo eulerTour il quale a sua volta chiama i metodi visitLeft, visitBelow o visitRight.

Di questi tre posso dirti che non è necessario che vengano invocati tutti. Cerco di spiegarmi meglio: il concetto alla base di un cammino euleriano è che, dato un albero, tutti i nodi vengano toccati da questo cammino per tre volte, la prima da sinistra (scendendo lungo l'albero), la seconda dal basso e la terza da destra (risalendo). Quindi se ognuno dei tre metodi attraversa tutti i nodi dell'albero, è sufficiente che ne venga implementato soltanto uno.

Tra l'altro il codice riportato dal libro di testo è sostanzialmente identico al mio e questo mi manda in tilt perchè a questo punto non so proprio quale possa essere il problema

[LeaderGL]

quello a cui mi riferivo è che secondo me non vengono richiamati i metodi giusti di volta in volta...hai controllato che effettivamente si entri, ad esempio, nel "visitRight()" di "EvaluateExpressionTour" e non da qualche altra parte?

[rubikk]

Ho capito qual era il problema e chiedo scusa a tutti coloro a cui ho fatto perdere del tempo, LeaderGL in primis.

I metodi di EulerTour e affini sono corretti, ne ero convinto e quindi, pensando che potesse essere un problema non tanto di costruzione dell'albero (che in effetti veniva generato correttamente dalla classe di test) quanto di sua gestione, sono andato a rivedere i metodi delle classi che implementano l'albero binario che viene usato per memorizzare gli elementi.
Gira e rigira, uno dei metodi che serviva a prendere il contenuto di un nodo lavorava non sul nodo corretto ma sul fratello, dunque avevo due metodi, chiamiamoli getLeft e getRight, implementati entrambi come getLeft.

Ovviamente questo portava anche i metodi di EulerTour a non lavorare sui due nodi figlio, bensì sempre sullo stesso nodo!

Questo è quanto, almeno ora ho imparato che quando si scrivono in successione due metodi assai simili tra loro conviene controllarli almeno 10 volte