Hilfe beim Algorithmus

[julia123]

hi Leute,

ich hänge immer noch bei den Bäumen.
Ziel: Diesen Ausdruck ((2+6)/(3*4))) -> [2, 6, +, 3, 4, *, / ] so umwandeln
Also was ich hab sind OP-Methoden(Expressions) die als Knoten dienen. Und Cont der als Blatt dient.
Die Bedingung der Aufgabe ist das ganze in Stack-Form zu lösen (grob gesagt).

Also so wie ich es verstanden hab . Man durchläuft (traversiert) durch die Blätter und fasst diesen mit dem Knoten zusammen...Diese Form nennt man glaub ich Postfix. z.B (2+3) -> 2,3,+


Ich hab die relevante Methode über die ich spreche oben im Quellcode Kommentiert.
Problem-Nummer 1. = Wieso bekomme ich -8 und nicht einfach 8 ausgegeben? (wenn ich das Programm ausführe)
Problem-Nummer 2. = Zeile 204 ( zwei Zahlen zusammenführen) ich hab da sowas geschriebn :

result.push(new Mult(tempZ1, tempZ2));

müsste es aber nicht so heißen

result.push(new Const( new Mult(tempZ1, tempZ2)));

Problem-Nummer 3. = Findet ihr noch Fehler? Oder könnt ihr mir etwas weiter bringen. Ich will keine lösung. Vielleicht erklärt ihr mir einfach nur ein denk Fehler.

Vielen Dank, schon mal !

 

[deepthroat]

Problem-Nummer 1. = Wieso bekomme ich -8 und nicht einfach 8 ausgegeben? (wenn ich das Programm ausführe)

Weil '(' - '0' nunmal -8 ist.

Problem-Nummer 2. = Zeile 204 ( zwei Zahlen zusammenführen) ich hab da sowas geschriebn :

result.push(new Mult(tempZ1, tempZ2));

müsste es aber nicht so heißen

result.push(new Const( new Mult(tempZ1, tempZ2)));

Nein.

Problem-Nummer 3. = Findet ihr noch Fehler? Oder könnt ihr mir etwas weiter bringen. Ich will keine lösung. Vielleicht erklärt ihr mir einfach nur ein denk Fehler.

Da ist noch ziemlich viel durcheinander.

Erstmal solltest du dich darauf konzentrieren aus dem Infix-Ausdruck einen korrekten Baum zu erstellen. Die Ausgabe des Baumes in Postfix-Schreibweise ist dann trivial.

Der erste Schritte wäre das du Zahlen verarbeiten kannst - nicht nur Ziffern.

Dann solltest du ruhig erstmal die Klammerausdrücke beiseite lassen und nur die Grundrechenarten verarbeiten. Dabei müßtest du auf die Priorität achten - wobei ich nicht weiß wie deine Aufgabenstellung genau lautet...

Außerdem wäre es vermutlich einfacher wenn deine parse Methode einfach einen Teil-Baum zurückgibt anstatt die Stack-Variable direkt zu modifizieren.

 

[julia123]

Ich bedanke mich erstmal ganz herzlich!

2. Fragen hätte ich noch:

1. Kannst du mir ihrrgendwo Exceptions empfehlen. Also ist alles Korrekt.

2.Wie kann ich es machen, dass z.B.: ein '+' geprinted wird. Die Reiehenfogle der Zahlen bei der Ausgabe ist richtig. Aber die Operatoren fehlen. Wo ist das Problem ?
Soll ich für jede Methode eine extra toString- Methode implementieren. Wie beiehen die Methode diese, also wie kommt es zu einem Aufruf?

 

[deepthroat]

2. Fragen hätte ich noch:

1. Kannst du mir ihrrgendwo Exceptions empfehlen. Also ist alles Korrekt.

Also ich würde dir estmal empfehlen nochmal komplett neu anzufangen. Das wird so nichts.

Mache dir erstmal Gedanken wie du den Baum des Ausdrucks erzeugen kannst -- ohne irgendwas zu programmieren. Grundlegend kannst du auch auf dem Papier überprüfen ob ein Algorithmus einen Ausdruck korrekt parst.

2.Wie kann ich es machen, dass z.B.: ein '+' geprinted wird.

Naja, einfach ausgeben...

Die Reiehenfogle der Zahlen bei der Ausgabe ist richtig. Aber die Operatoren fehlen. Wo ist das Problem ?

Dein Code ist ziemlich wirr. Das Problem ist die Rekursion und das Attribut pos in der Klasse. Wenn du die Methode rekursiv aufrufst, veränderst du auch die Position, damit steht pos bei der Rückkehr des Aufrufs an einer völlig anderen Stelle... Das siehst du aber auch ganz einfach wenn du mal mit dem Debugger schrittweise dein Programm durchgehst!

Desweiteren wäre es für die Hilfestellung wichtig wenn du uns möglichst genau sagst wie überhaupt deine Aufgabe lautet.

 

[HonniCilest]

Grundsätzlich muss ich mich deepthroat anshcließen, dein Code ist mittlerweile ziemlich wirr, ggf. solltest du ihn Schritt für Schritt noch einmal aufbauen.

2.Wie kann ich es machen, dass z.B.: ein '+' geprinted wird. Die Reiehenfogle der Zahlen bei der Ausgabe ist richtig. Aber die Operatoren fehlen. Wo ist das Problem ?
Soll ich für jede Methode eine extra toString- Methode implementieren. Wie beiehen die Methode diese, also wie kommt es zu einem Aufruf?

Als hilfestellende Erklärung:
Das Beispiel (2+6)/(3*4) ist mit deinem Ansatz ein Baum der Tiefe 3. Der Wurzelknoten ist die ComplexExpression DIV mit den 2 Teilbäumen, welche als Knoten eine ComplexExpression SUM und eine ComplexExpression MULT darstellen. Diese wiederum haben jeweils zwei ConstantExpression als Ast-Enden.
Um den finalen Baum auszugeben musst du also die toString-Methode des Wuzelknotens ausgeben. Dieser wiederum ruft toString() der Sub-Knoten auf mit Anhängen des entsprechenden Operators. Das würde Schritt für Schritt für das Beispiel so aussehen:

ROOT: "LEFT1, RIGHT1, /"
..LEFT1: "LEFT2A, RIGHT2A, +"
....LEFT2A: "2"
....RIGHT2A: "6"
..RIGHT1: "LEFT2B, RIGHT2B, *"
....LEFT2B: "3"
....RIGHT2B: "4"

-->
ROOT: "LEFT1, RIGHT1, /"
..LEFT1: "2, 6, +"
..RIGHT1: "3, 4, *"

-->
ROOT: "2, 6, +, 3, 4, *, /"

Edit PS.: Hast du dir auch ausreichend Testfälle zurechtgelegt? Die würden dir beim Parsen selbst vermutlich helfen. Hier mal ein paar Anregungen:
- Fehlerfälle wie Division durch 0, Unvollständige Ausdrücke, unzulässige Symbole ("1/0", "+", "(", "abc")
- Wertlose Ausdrücke wie leerer Ausdruck, leere Klammer ("", " ", "()")
- Konstante Ausdrücke ("8", "123")
- Einfache Operationen ("1+1","1-1","1*1","1/1"), Frage: Wie willst du eine Division behandeln, welche kein ganzzahliges Ergebnis hat?
- Verkettete Ausdrücke ohne Klammer ("1+1+1+1") Hier sollte ein balancierter Baum angestrebt werden also 1, 1, + 1, 1, +, + anstatt 1, 1 +, 1, +, 1, + auf Grund möglicher Rekursionstiefen
- Knoten mit einem Komplexen und einem Konstanten Ausdruck ("1+1*1")
- Punktrechnung vor Strichrechnung ("1+1*1", "1/1-1")
- Verschachtelte Klammern ("1+(1*(1+1)*(1+1))")
- Negative Zahlenwerte ("1+-1", "1*-1", "-1")

 

[julia123]

ok,
ich hab das Problem mit z.B.: '+' gelöst. Ich hab einfach eine toString- Methode in die einzelnen Expressions implementiert z.B:
Addition

@Override
		public String toString() {
			return getx() + "" + gety() + "+";
		}

Die toString-Methode von meiner abstrakten Klasse ruft ja die der Unterklassen auf ...


Ich bekome jetzt sollch ein Ausdruck rauss (2+6)/(3*4)))-> 2, 3, +, 4, 5, -,
Alles schön und gut.

Das richtige wird auch ausgerechent, der Vorgegebene Test läuft :

@Test
	public void testShouldResultInCorrectEvaluation() {
		Expression expr = Expressions.parse("(3*((((2+3)*2)-5)/5))");
		assertEquals(3, expr.evaluate());
	}

Jedoch beim 2 Teil des Test kommt ein Fehler:

 @Test
	public void testShouldResultInEqualSyntaxTrees() {
		Expression expr1 = new Mult(
								new Div(
									new Sub(
										new Mult(
											new Add(new Const(2), new Const(3)),
											new Const(2)
										), new Const(5)
									), new Const(5)
								), new Const(3)
							);
		Expression expr2 = Expressions.parse("(3*((((2+3)*2)-5)/5))");

		assertTrue(expr1.equals(expr2));
	}

Ist meine Equals-Methode richtig? Ich vermute da denn Fehle weiss aber nicht wie ich das beheben kann. Hab mir schon die API 100 durchgelsen. Am Ende kommt bei mir trotzdem nur die Durschnitz Equals-Methode rauss.

Hier noch die Aufgabenstellung

Aufgabenstellung
Betrachten Sie die Erstellung eines Syntaxbaums von Aufgabenblatt 4. Ist es notwending, einen Umweg über die
dort verlangte Postfix-Darstellung zu gehen oder kann der Algorithmus zur Erzeugung der Postfix-Darstellung
so abgewandelt werden, dass er mit Hilfe des Stapels gleich den Baum aufbaut?
Implementieren Sie eine entsprechende Abwandlung von diesem Algorithmus aus Aufgabenblatt 4 und der Methode
parseToPostfix(String expr) als parse(String expr) in einer Klasse Expression. Diese Methode
soll einen vollständig geklammerten arithmetischen Ausdruck entgegen nehmen. Sie gibt dann den entsprechenden
Ausdrucks-Baum zurück.
Die Methode evaluate() eines Ausdrucks soll wieder den Ausdruck auswerten und das Resultat der Auswertung
übergeben.

Vielleicht hab ich aber auch einfach nur die Aufgabenstellung nicht verstanden.


Trotzdem hab ich dazu die Aufgabenstellung im Anhang beigefügt.

 

[HonniCilest]

Also war die Liste doch vorgegeben... Persönliche Meinung: Unvorteilhafte Studienaufgabe...
Mit Listen kannst du aber grundsätzlich ähnlich vorgehen, statt str1 + str2 verwendest du eben die Verkettung von 2 Listen.

Die Voraussetzung mit der vollständigen Klammerung ändert natürlich auch einiges wie z.B. die Beachtung von Punkt- vor Strichrechnung, die Erzeugung eines balancirten Baumes etc.
Daher sehe meine Testfälle (siehe oben) bitte nur als Anregung für die Zukunft ;-)

 

[julia123]

Langsam versteh ich bei mir an der uni nix mehr... echt!
Ich hab auch jetzt kaum zeit dass alles nach zu gehen deswegen Frag ich mal hier in die Runde:
Der Junit test von oben Funktioniert wie ich schon gesagt habe nicht !
Testfall testShouldResultInEqualSyntaxTrees läuft oben nicht!

Jetzt haben die einen neuen Hochgeladen(keine Ahnung ob der obige falsch ist oder ...),naja hab denn mal implementiert und siehe da alles Läuft.

import static org.junit.Assert.*;
import org.junit.Test;

import ad.hue3.Expressions.*;

public class ExpressionsTest {

	@Test
	  public void testShouldResultInEqualSyntaxTrees() {
	    Expression expr1 =
	           new Mult(
	                new Const(3),
	                new Div(
	                  new Sub(
	                    new Mult(
	                      new Add(new Const(2), new Const(3)),
	                      new Const(2)
	                    ), new Const(5)
	                ), new Const(5)
	              )
	           );
	    
	    Expression expr2 = Expressions.parse("(3*((((2+3)*2)-5)/5))");
	    
	    assertTrue(expr1.equals(expr2));
	  }
	  
	  @Test
	  public void testShouldResultInCorrectEvaluation() {
	    Expression expr = Expressions.parse("(3*((((2+3)*2)-5)/5))");
	    
	    assertEquals(3, expr.evaluate());
	  }
	  
	  @Test
	  public void testShouldCompareSimpleExpressions() {
		  Expression expr1 = new Add(new Const(2), new Const(3));
		  Expression expr2 = Expressions.parse("(2+3)");
		  
		  assertTrue(expr1.equals(expr2));
	  }
	  
	  @Test
	  public void testShouldCompareSimpleExpressionsAndFail() {
		  Expression expr1 = new Add(new Const(2), new Const(3));
		  Expression expr2 = Expressions.parse("(3+2)");
		  Expression expr3 = Expressions.parse("(2-3)");
		  
		  assertFalse(expr1.equals(expr2));
		  assertFalse(expr1.equals(expr3));
		  assertFalse(expr2.equals(expr3));
	  }
	  
	}

Hier läuft dieser TEST durch:
testShouldResultInEqualSyntaxTrees
Was ist aber anderes?

Bin grade leicht verunsichert ... naja. Jetzt weiss ich nicht soll ich weiter gucken wo ich Fehler hab oder soll ich sagen alles richtig.

 

[deepthroat]

Die Voraussetzung mit der vollständigen Klammerung ändert natürlich auch einiges

Genau soetwas hatte ich vermutet; deswegen meine Frage. Damit ist auch die Hälfte von dem was ich sagte unnötig geworden...

Der Junit test von oben Funktioniert wie ich schon gesagt habe nicht !
Testfall testShouldResultInEqualSyntaxTrees läuft oben nicht!

Jetzt haben die einen neuen Hochgeladen(keine Ahnung ob der obige falsch ist oder ...

Ja, der obige ist "falsch".

Das Problem (und der Unterschied zum zweiten Test) ist die Reihenfolge der Operanden beim äußeren Mult.

Wobei die Multiplikation natürlicher Zahlen eigentlich kommutativ ist... Das könntest du natürlich auch in deinen equals Methoden beachten...

 

[julia123]

hi, Leute

Naja angelblich sollte ich meine Equals -Methode mal überarbeiten. Ich kann ihn da aber nicht ganz folgen(siehe oben equals).
Ich hab jetzt einfach mal in der Main 2 Bäume vergleichen. Es läuft.

public static void main(String[] agrs) {
		
		
		//equals funktioniert Test
		
		Expression a =parse("((2+6)/(3*4)))");
		Expression b =parse("((2+6)/(3*4)))");
		System.out.println(a.equals(b));
		
		
	}

ich hab jetzt einfach immer mal was Anderes verändert. Mal ander Zahlen eingefügt, mal Operatoren ersetzt oder denn Ausdruck komplett verkleinert.

Meine einzige Angst ist die dass hier nicht das richtige equals verwendet wird. Also nicht das von ComplexExpression.

Naja, wenn dass so nicht richtig ist wie ich es teste bitte ich um Hilfe. Und dass meine Equals-Methode falsch ist oder dass ich da was Rekusiv machen sollte weiss ich auch, bitte etwas konkreter.

@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			ComplexExpression other = (ComplexExpression) obj;
			if (x == null) {
				if (other.x != null)
					return false;
			} else if (!x.equals(other.x))
				return false;
			
			if (y == null) {
				if (other.y != null)
					return false;
			} else if (!y.equals(other.y))
				return false;

			return true;
		}