String in binären Baum umwandeln

[jhjp]

Hallo Leute,
ich bin grad am Verzweifeln! Sitz jetzt glaub ich schon über 10 Stunden an diesem blöden Baum....

Folgende Aufgabe: Ein String der z.b. so aussieht: String s = "((3+4)x(1/2))" soll nun in einen Baum umgewandelt werden, der so aussieht:
x
+ /
3 4 1 2


Mein Problem: er setzt mir die Operanden immer an die falsche Stelle. Und die rechte Seite des Baumes sieht nur bei einfachen Strings korrekt aus zb.(3+2).

Ich bitte um Hilfe... weiß einfach nicht mehr weiter...

und mein Prof meint auch noch, das sei alles gar nicht so schwer *könntihnwürgen*

gruß
beni

Hier mein Code:

	public BinTree makeBinTree(String s){
		if(s.substring(0,1).matches("[0123456789]")){ //Bei Zahl			
			int i = 0; while(!s.substring(i,i+1).matches("[+-/x]") && !s.substring(i,i+1).equals(")")) i++;
			return bin( s.substring(0,i) );
		}
		if(s.indexOf("(") == 0){
			s = s.substring(1);
			return bin( makeBinTree(s.substring(0)), operant(s) , makeBinTree(rechteSeite(s)) );
		}
		return bin("");
	}
	public String operant(String s){
		int i = 0;
		if(s.indexOf("+") != -1 && s.indexOf("+") < s.indexOf(")")) i = s.indexOf("+");
		if(s.indexOf("-") != -1 && s.indexOf("-") < s.indexOf(")")) i = s.indexOf("-");
		if(s.indexOf("x") != -1 && s.indexOf("x") < s.indexOf(")")) i = s.indexOf("x");
		if(s.indexOf("/") != -1 && s.indexOf("/") < s.indexOf(")")) i = s.indexOf("/");
		return s.substring( i , i+1 );
	}
	public String rechteSeite(String s){
		int i = 0;
		if(s.indexOf("+") != -1 && s.indexOf("+") < s.indexOf(")")) i = s.indexOf("+");
		if(s.indexOf("-") != -1 && s.indexOf("-") < s.indexOf(")")) i = s.indexOf("-");
		if(s.indexOf("x") != -1 && s.indexOf("x") < s.indexOf(")")) i = s.indexOf("x");
		if(s.indexOf("/") != -1 && s.indexOf("/") < s.indexOf(")")) i = s.indexOf("/");
		return s.substring(i+1);
	}

Vollständigkeitshalber: Meine Baumklasse:
makeBinTree und operant, rechteSeite stehen in der class BinTree!

public class BinTree {
	public Node root;
	
	public BinTree(){
		root = new Node(null);
	}
	public BinTree bin(BinTree a, String t, BinTree b){
		BinTree neu = new BinTree();
		neu.root.left = a.root;
		neu.root.right = b.root;
		neu.root.value = t;
		return neu;
	}
	public BinTree bin(String t){
		BinTree neu = new BinTree();
		neu.root.value = t;
		return neu;
	}
	public static BinTree left(BinTree a){
		BinTree neu = new BinTree();
		neu.root = a.root.left;
		return neu;
	}
	public BinTree right(BinTree a){
		BinTree neu = new BinTree();
		neu.root = a.root.right;
		return neu;
	}
	public String value(BinTree a){
		return a.root.value;
	}
	public boolean isEmpty(BinTree a){
		if(a.root.value.equals("")) return true;
		else return false;
	}
}

Die Node klasse:

public class Node {
	String value;
	Node left;
	Node right;
	
	public Node(String wert){
		value = wert;
		left = null;
		right = null;
	}
}

So soll dann das Hauptprogramm aussehen:

class test extends BinTree {
	public static void main(String[] args){
		String s = "((3+4)x(1/2))";
		BinTree a = new BinTree();
		a = a.makeBinTree(s);
	}	
}

 

[ronny]

Hallo!

das ganze klingt ja ziemlich nach ner compiler vorlesung......

ich bin mir da aber nich so ganz sicher, ob du mit diesem string auschneid-aktionen auf dem richtigen weg bist....

FALLS das für compiler ist, dann bin ich mir aber sicher das ihr bestimmt erst ne sprachanalyse machen müsst um z. b. die rechenregeln abdecken zu können (punkt vor strich, klammern, etc).

Erst wenn du die sprache richtig analysiert und die grammatik dazu aufgestellt hast könntest du theoretisch nen recursive decent parser bauen der deinen string durchgeht.... da passiert nämlich nix anderes, als das ein "abstrakter" baum erstellt wird... ich denk mal ihr sollt halt dann in den "zwischenstationen" einfach das aktuelle zeichen in nen stringbuffer schreiben....

bin ich da auf dem richtigen weg???? weil dann könnt ich dir sprachkonstrukte geben für die grammatik für nen taschenrechner

 

[jhjp]

Danke für die Antwort!
Also rechenregeln muss der Programm nicht können! Die klammern werden immer richtig gesetzt!
So ein String: 5+4*3 ist zb. als eingabe nicht erlaubt!
Einfach die Klammern aufdröseln in : Operator = Wurzel, Zahl links vom Operator = linkes Kind, Zahl rechts vom Operator = rechtes Kind. mehr net!

Hab mir auch schon überlegt, das ganze mithilfe eines Stacks zu machen. Habs auch schon programmiert, hat aber natürlich net funktioniert, bin halt n anfänger...

Aber vom Prinzip her, kann ich doch das Problem gar nicht anders lösen, als jedes Zeichen aus dem String rauszuschnippeln und ihm dann sagen, was er machen soll in Abhängigkeit von der Art des Zeichens ( ob Klammer, Zahl oder Operand)... oder?

Gruß
beni

 

[ronny]

hmmmmmm, ok... scheint doch ne etwas andere geschichte zu sein, wie ich dachte.....

ich kann dir nicht wirklich im moment da weiterhelfen, da müsst ich mich erstmal reindenken und selbst ausprobieren....

doch selbst ohne rechenregeln bin ich mir ziemlich sicher, dass da ne rekursion dahinter steckt, die den baum aufbaut.... denn wenn ich mir den string anschaue, dann müsstest du ja eigentlich "die Mitte" finden (der Operator mit der höchsten prio) und von da ab links rechts abwärts den baum aufbauen...... und da wären wir schon wieder bei der geschichte: "wo geht die klammer auf, wo geht sie zu..." siehe: (((3+4)x(3+4))x(3+4))

hier wäre ja nach deiner angabe quasi das 2. x das oberste im baum....

ich hasse solche aufgaben.....

vielleicht hat ja doch noch jemand ne idee???
die lösung würde mich auch interessieren!!!

 

[nagash56]

Vorschlag:

Der funktioniert aber nur wenn du in deinen Baumknoten zusätzlich einen Zeiger für den Vaterknoten definierst.

Du scannst den String in einer Schleife Zeichen für Zeichen und startest mit einem leeren Baum (root = null) und führst einen pointer auf den aktuellen Knoten.

Bei "(" erzeugst du einen Knoten und hängst in links and den pointer-Knoten wenn links = null sonst rechts. pointer zeigt dann auf den neuen Knoten. Wichtig diese Knoten haben noch keinen value.

Bei Zahlen erzeugst du einen Knoten und hängst in links an den Baum wenn links = null, sonst rechts. pointer zeigt
nicht auf den neuen Knoten sondern bleibt auf dem aktuellen.

Bei Operatoren setzt du den Value des Knotens auf den pointer zeigt entsprechend dem Operator. Sonst nichts.

Bei ")" setzt du pointer auf den Vaterknoten von pointer, also pointer = pointer.getFather();

Und das machst du so lange bis der String zu Ende ist.

Also bei diesem Beispiel würde das wie folgt aussehen.
(((3+4)x(3+4))x(3+4))

Zuerst werden drei leere Knoten erzeugt jeweils links aneinander gehängt. pointer zeigt auf den niedrigsten
3 wird links von pointer gehängt, + wird in den leeren pointer Knoten eingetragen und 4 wird rechts von pointer gehängt, weil ja links schon belegt ist.
Dann kommt ")" und es wird pointer = pointer.getFather() ausgeführt und der zeiger wandert eine Ebene nach oben. Der Operator "x" wird in diesen Knoten eingetragen. Die nächste "(" erzeugt wieder einen leeren Knoten, der allerdings rechts angehängt wird weil ja links schon belegt ist, usw...

 

[Wildcard]

Warum denn so kompliziert?

        if (s.substring(1).contains("("))
        {
            s=s.substring(1);
            Pattern pat = Pattern.compile("[\\(\\)]");
            Matcher mat = pat.matcher(s);
            Stack stack = new Stack();
            do
            {
                mat.find();
                if (mat.group(0).equals("("))
                    stack.push(mat.group(0));
                else
                    stack.pop();        
            }while(!stack.isEmpty());
            int position = mat.end();
            makeBinTree(s.substring(0,position));
            makeBinTree(s.substring(position+1,s.length()-1));
        }
        else
        {
            //rekursionsende => klammerloser Term der Form 3+4 || 6x7 || ...
        }

Die Ergebnisse in den Baum einfügen und fertig :wink:

 

[Guest]

ES GEHT!!!!!!
Vielen Dank! für Eure Hilfe:
@wildcard, tut mir leid, aber den code hab ich net verstanden, was ist denn ein pattern?
@nagash56: VIELEN DANK, hat mir am meisten geholfen!!!!!

Hier nun der Code - so ne Schleife versteh ich einfach besser als diese rekursion...:

	public BinTree makeBinTree(String s){
		BinTree a = new BinTree();
		Node zeiger, szeiger;
		zeiger = a.root;
		szeiger = null;
		
		for(;;){
			if(s.substring(0,1).equals("(")){
				if(zeiger.left == null){
					zeiger.left = new Node("");
					szeiger = zeiger;
					zeiger = zeiger.left;
				}
				else{
					zeiger.right = new Node("");
					szeiger = zeiger;
					zeiger = zeiger.right;
				}
			}
			if(s.substring(0,1).matches("[0123456789]")){
				int i = 0; while(!s.substring(i,i+1).matches("[+-/x]") && !s.substring(i,i+1).equals(")")) i++;
				if(zeiger.left == null) zeiger.left = new Node(s.substring(0,i));
				else zeiger.right = new Node(s.substring(0,i));
			}
			if(s.substring(0,1).equals("+") || s.substring(0,1).equals("-") || s.substring(0,1).equals("x") || s.substring(0,1).equals("/")){
				zeiger.value = s.substring(0,1);
			}
			if(s.substring(0,1).equals(")")){
				zeiger = szeiger;
			}
			if(s.equals(")")) break;
			
			s = s.substring(1);
		}
		return a;
	}

Nur noch ein Problem: die Wurzel des Baums ist immer null und der Termbaum hängt am linken Kind.
Aber das Problem lös ich, wenn ich Einfügen und Löschen implementiert hab....

gruß
beni

 

[Wildcard]

@wildcard, tut mir leid, aber den code hab ich net verstanden, was ist denn ein pattern?

Du benutzt doch selbst Patterns, nur noch etwas kompliziert :lol: :

s.substring(0,1).matches("[0123456789]") == s.substring(0,1).matches("(\\d)")

usw...

zum Umgang mit Patterns (ist wichtig):
http://java.sun.com/j2se/1.5.0/docs/api/java/util/regex/Pattern.html

so ne Schleife versteh ich einfach besser als diese rekursion...

daran würd ich unbedingt arbeiten. Für viele Probleme eignet sich Rekursion ideal