Binärbaum mit Linksklammerdarstellung

[drpingoo]

Hi zusammen,

Versuch mich wieder mal am programmieren.

Also bei der Linksklammerdarstellung, ich weiss nich, ob euch das was sagt, ist quasi ein Baum impliziert. Also man durchläuft in jeweils von links nach rechts. Das heisst, immer, wenn eine neue Klammer geöffnet wird, bedeutet das, dass wir uns wieder eine Ebene tiefer befinden, wenn sie geschlossen wird wieder weiter oben, also einfach ungekehrt. Und durch Kommas abgetrennte Buchstaben bedeuten, dass sie sich auf der selben Ebene befinden.

Also z.B. so A(B(C,D))

Ich muss jetzt ein Programm schreiben, dass anzeigt, ob eine Eingabe in der Konsole korrekt war oder nicht und dementsprechend reagieren.

Ich möchte,dass tree[i] jeweils die Position im Baum markiert. Wie kann ich es aber anstellen, dass z.b. bei binärbaum(tree[i]) der tree[i] auch in der Titelmethode steckt, obwohl ich es schon deklariert habe zu Beginn. Und wie kann ich einen error bzw. ein ok ausprinten. Ist das Programm sonst ok?

lg

/**
 * Informatik II - FS2008 <br>
 * Uebungsserie 3, Aufgabe 4 <br>
 * Template for LKD.java <br>
 *
 * LKD verifies the syntactical correctness of a binary tree given
 * in left-parenthesis representation <br>
 *
 * @author Silvia Santini
 */
public class LKD {

    //the private class field tree contains the
    //left-parenthesis representation of a binary tree
    private char tree[];
    int i;
    /**
     * Constructor initializes the class field tree.
     *
     * @param tree binary tree in left-parenthesis representation
     */
    public LKD(char[] treeInLKDForm) {
        tree =  treeInLKDForm;
    }

    /**
     * Prints an array of chars and marks the last element with "^"
     * (You can use this method to indicate the element actually causing a syntax error)
     *
     * @param testIndex the index of the last correct element in the tree
     */
    public void invalidPosition( int testIndex ) {
        System.out.println( tree );
        for(int j=0; j < testIndex; j++ ) {
            System.out.print(" ");
        }
        System.out.println("^");
    }

    /**
     * Verifies the syntactical correctness of the left-parenthesis
     * representation of a binary tree
     */
    public void syntaxChecker(tree[i]) {
        int testIndex = 0;
        tree[i] =binärbaumOderLeer(tree[i])
        if(tree[i]!=' '){
        	return; // error
        }
        else{
        	return; //ok
        }
        
      

       

        if( testIndex == tree.length ) {
            //correct left-parenthesis representation
            System.out.println("Valid left-parenthesis representation :-) ");
        }
        else {
            System.out.println( "ERROR: "+
            "Error type 007 detected: ");
            invalidPosition( testIndex );
        }
    }

    int knoten(int pos){
    	if (tree[i] >= 'A' && tree[i] <= 'Z'){
    		return tree[i+1];}
    		else{
    			return ;//error
    	}
    }
    
    int binärbaum(tree[i]){ //ich möchte, dass der Paramter jeweils auch da drin steht,
    	tree[i] = knoten(tree[i]);//wie stelle ich das an?
    	if(tree[i]=='('){
    		tree[i] =tree[i+1] ;
    		tree[i] = binärbaum(tree[i]);
    		if(tree[i]==','){
    			tree[i] =tree[i+1];
    			tree[i] = binärbaum(tree[i]);
    	
    		}
    		if(tree[i]!=')')
    			tree[i] =tree[i+1];
    	}
    	return tree[i];
    	
    }
    
    int binärbaumOderLeer(tree[i]){
    	if (tree[i]==' ')return tree[i];
    	else return binärbaum(tree[i]);
    	
    	
    	
    }
    
    public static void main(String[] args) {

        //Parse the input
        if( args.length != 1 ) {
            System.out.println( "Invalid input!");
            System.out.println( "Example of a correct call to LKD.java: " +
            "java LKD \"A(B(C,B(A)))\"" );
            System.exit( 1 );
        }

        //Convert input string to an array of chars (char[]):
        char[] inputLKD = args[0].toCharArray();

        //New instance of the LKD class initialized with the
        //left-parenthesis representation given as input
        LKD check = new LKD(inputLKD);

        //Syntax-checker:
        check.syntaxChecker();
    }
}

 

[zeja]

Übergib doch tree und i getrennt als zwei Parameter an deine Methoden.

 

[drpingoo]

ok, meinst du sowas:

int binärbaumOderLeer(char tree[], int i)?

lg

 

[zeja]

Ja genau. Dann kannst du da doch so drauf zugreifen. Hab da jetzt nicht im Detail rübergeschaut, nur damit du mal weiterkommst.

 

[drpingoo]

Hmm.. Dann hab ich aber an einem andren Ort das Problem. Beispielsweise wenn ich sowas schreibe:

tree[i] = knoten(tree[i])

lg

 

[zeja]

Sorry schau mir das mal in Ruhe an morgen...

 

[drpingoo]

ok,ist gut

lg

 

[zeja]

Irgendwie steckt da noch ziemlich der Wurm drin.

int knoten(int pos){
        if (tree[i] >= 'A' && tree[i] <= 'Z'){
            return tree[i+1];}
            else{
                return ;//error
        }
    }

Warum nicht:

boolean isNode(int pos){
        if (tree[pos] >= 'A' && tree[pos] <= 'Z'){
            return true;
        }
        else{
            return false;
        }
    }

Ich weiß an den meisten Stellen gar nicht was du damit bezwecken willst ein int zurückzugeben?

Überleg dir nochmal genau wie das ganze funktionieren soll, mal etwas abseits von Java. Also erstmal den Algorithmus in Textform hinschreiben und dann schaun wie man das wiederum in Java umsetzen kann.

 

[drpingoo]

Hmm.. ok, also als syntaydiagramm hab ich mir das so gedacht, iwie rekursiv (im Anhang). Und uns wurde gesagt, dass jedes Diagramm einer Methode entsprechen würde, also 3.

lg

 

[drpingoo]

Also, ich hab mal dran rumgebastelt. Es hat jetzt zwar keine Fehler mehr drin, funktioniert aber trotzdem noch nicht... Das mit dem binärbaumOderLeer ist auch noch eingeslasht, sonst würds Fehlermeldungen geben, also stimmts momentan ja sowieso nicht.

lg

/**
 * Informatik II - FS2008 <br>
 * Uebungsserie 3, Aufgabe 4 <br>
 * Template for LKD.java <br>
 *
 * LKD verifies the syntactical correctness of a binary tree given
 * in left-parenthesis representation <br>
 *
 * @author Silvia Santini
 */
public class LKD {

    //the private class field tree contains the
    //left-parenthesis representation of a binary tree
    private char tree[];
    int i;
    /**
     * Constructor initializes the class field tree.
     *
     * @param tree binary tree in left-parenthesis representation
     */
    public LKD(char[] treeInLKDForm) {
        tree =  treeInLKDForm;
    }

    /**
     * Prints an array of chars and marks the last element with "^"
     * (You can use this method to indicate the element actually causing a syntax error)
     *
     * @param testIndex the index of the last correct element in the tree
     */
    public void invalidPosition( int testIndex ) {
        System.out.println( tree );
        for(int j=0; j < testIndex; j++ ) {
            System.out.print(" ");
        }
        System.out.println("^");
    }

    /**
     * Verifies the syntactical correctness of the left-parenthesis
     * representation of a binary tree
     */

    /*public int syntaxChecker() {
        int testIndex = 0;
        //tree[i] =binärbaumOderLeer(tree[i], i);
        if(tree[i]!=' '){
        	return -1; // error
        }
        else{
        	return 0; //ok
        }
      
*/
    public void syntaxChecker() {
        int testIndex = 0;
        if(tree[testIndex]!=' '){
        	System.out.println("fehler"); // error
        }
        //ADD YOUR CODE HERE
        //MODIFY THE TEMPLATE IF NECESSARY OR APPROPRIATE!
        //DEFINE AND IMPLEMENT ADEQUATE METHODS TO PERFORM THE SYNTAX CHECK!

        //testIndex = ....
  

        if( testIndex == tree.length ) {
            //correct left-parenthesis representation
            System.out.println("Valid left-parenthesis representation :-) ");
        }
        else {
            System.out.println( "ERROR: "+
            "Error type 007 detected: ");
            invalidPosition( testIndex );
        }
    }

    boolean isknoten(int testIndex ){
    	if (tree[testIndex] >= 'A' && tree[testIndex] <= 'Z'){
    		return true;}
    		else{
    			return false ;//error
    	}
    }
    
    
 
    int binärbaum(int testIndex){ //ich möchte, dass der Paramter jeweils auch da drin steht,
    
    	if (tree[testIndex] == '(' && tree[testIndex+1] != ' '){
    		
    	  
    		tree[testIndex] = tree[testIndex+1];
    	}
    	
    	if(tree[testIndex]==',' && tree[testIndex+1] != ' '){
    		tree[testIndex] = tree[testIndex+1];
    	}
    	
    	if( tree[testIndex] != ')')
    		tree[testIndex] = tree[testIndex+1];
    	
    	return tree[testIndex];
    }
    	/*tree[i] = knoten(tree[i]);//wie stelle ich das an?
    	if(tree[i]=='('){
    		tree[i] =tree[i+1] ;
    		tree[i] = binärbaum(tree[i]);
    		if(tree[i]==','){
    			tree[i] =tree[i+1];
    			tree[i] = binärbaum(tree[i]);
    	
    		}
    		if(tree[i]!=')')
    			tree[i] =tree[i+1];
    	}
    	return tree[i];
    	
    }
    */
   /* int binärbaumOderLeer(char tree[]){
    	if (tree[i]==' ')return tree[i];
    	else return binärbaum(tree[i]);
    	
    	
    	
    }*/
    
    public static void main(String[] args) {

        //Parse the input
        if( args.length != 1 ) {
            System.out.println( "Invalid input!");
            System.out.println( "Example of a correct call to LKD.java: " +
            "java LKD \"A(B(C,B(A)))\"" );
            System.exit( 1 );
        }

        //Convert input string to an array of chars (char[]):
        char[] inputLKD = args[0].toCharArray();

        //New instance of the LKD class initialized with the
        //left-parenthesis representation given as input
        LKD check = new LKD(inputLKD);

        //Syntax-checker:
        check.syntaxChecker();
    }
}