Stack mit bestimmter Aufgabe

[Heinrich500]

Hallo,
ich will mittels eines Stacks eine Klasse implementieren, die die Korrektheit eines Klammerausdrucks überprüft. Das Programm bekomt dabei als Programmargument den Pfad einer Textdatei übergeben. Das erste Problem ist jetzt schon, wie ich auf diese Textdatei dann zugreifen könnte. Hier mein Versuch:

public class Klammern {

    public static boolean rightBrackets(String s) {
        Stack<Character> stack  = new Stack<Character>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '[' || c == '(' || c == '{' ) {     
                stack.push(c);
            } else if(c == ']') {
                if(stack.empty() || stack.pop() != '[') {
                    return false;
                }
            } else if(c == ')') {
                if(stack.empty() || stack.pop() != '(') {
                    return false;
                }           
            } else if(c == '}') {
                if(stack.empty() || stack.pop() != '{') {
                    return false;
                }
            }

        }
        return stack.empty();
    }

    
    
    
    
    public static void main(String[] args) {
        String path = args[0];
        File CP_file = new File(path);
        
        //Wie übergebe ich meiner Methode jetzt die Textdatei?
      
      
    }

 

[stg]

siehe z.B. java.io.FileReader und java.io.BufferedReader

 

[Heinrich500]

Also dann so:

           String path = args[0];
        File CP_file = new File(path);
        FileReader fr = new FileReader(CP_file);

Das funktioniert leider nicht und ich wüsste auch nicht, wie ich das in einen String umwandeln könnte?

 

[mihe7]

List<String> lines = java.nio.file.Files.readAllLines(CP_file.toPath());

 

[Heinrich500]

Ich verstehe leider nicht alle Anweisungen mihe. Würde es vllt auch so gehen:

 String path = args[0];
       File CP_file = new File(path);
       BufferedReader in = new BufferedReader (new FileReader (CP_file) );
       String ausgabe=in.readLine()    ;

 

[mihe7]

Ja, damit liest Du eine Zeile ein, wobei Du in dem Fall try-with-resources verwenden solltest, damit der Reader auch wieder geschlossen wird:

try(BufferedReader in = new BufferedReader(new FileReader (CP_file))) {
    String line = in.readLine();
    verarbeite(line);
}

Um alle Zeilen der Datei zu behandeln, packt man das in eine Schleife:

try(BufferedReader in = new BufferedReader(new FileReader (CP_file))) {
    String line;
    while ((line = in.readLine()) != null) {
        verarbeite(line);
    }
}

Natürlich kann man erst alle Zeilen einlesen, z. B. in eine Liste und dann über die Liste iterieren:

List<String> lines = new ArrayList<>();
try(BufferedReader in = new BufferedReader(new FileReader (CP_file))) {
    String line;
    while ((line = in.readLine()) != null) {
        lines.add(zeile);
    }
}

for (String line : lines) {
    verarbeite(line);
}

Und den ersten Teil kann man mit Hilfe von java.nio.file.Files kurz schreiben:

List<String> lines = java.nio.file.Files.readAllLines(CP_file.toPath());

for (String line : lines) {
    verarbeite(line);
}

Alles klar?

 

[Heinrich500]

List<String> lines = new ArrayList<>(); try(BufferedReader in = new BufferedReader(new FileReader (CP_file))) { String line; while ((line = in.readLine()) != null) { lines.add(zeile); } } for (String line : lines) { verarbeite(line); }

Alles klar. Das zeile müsste dann doch line sein oder?

Wie könnte ich mit meinem Stack die Positionen des zusammengehörigen Klammerpaares ausgeben?

 

[mihe7]

Das zeile müsste dann doch line sein oder?

Oops, ja. Übersehen. Ich hatte das zuerst mit zeile geschrieben und dann auf line umbenannt, damit es besser zum Code von vorhin passt 🙂

Wie könnte ich mit meinem Stack die Positionen des zusammengehörigen Klammerpaares ausgeben?

Indem Du Dir eine Klasse schreibst, deren Objekte je ein Zeichen inkl. dessen Position im String darstellen.

 

[Heinrich500]

Ich habe eine Methode vorgegeben, die folgendes macht:
Die Methode erhält als Parameter die Zeile und Spalte der öffnenden undschließenden Klammern sowie die Klammern selbst als Zeichen. Dies führt zu eine runseren Testfällen genügenden Ausgabe wie z. B.:Matching brackets: ’[’ at line 1, column 10 and ’]’ at line 1, column 11

Dann muss ich mir ja auch noch merken, in welcher Zeile die Klammer steht.
Wie merke ich mir die Zeile und Spalte.
Kannst du mir da noch einen Tipp geben?

 

[mihe7]

Das funktioniert genauso. Dürfen die Klammern über mehrere Zeilen verteilt sein?

 

[Heinrich500]

Ja dürfen sie:
Z.b gibt es folgende Ausgabe:
Matching·brackets:·'{'·at·line·1,·column·16·and·'}'·at·line·3,·column·1
Also kann ich mein obiges Programm nicht verwenden?
Könntest du vllt den Anfang von deiner Idee zeigen bitte?
Vllt würde ich es dann besser verstehen.

 

[mihe7]

Du willst Dir die Zeile und die Spalte eines Zeichens sowie das Zeichen selbst merken:

class CharacterPosition {
    public final int row;
    public final int col;
    public final char character;

    public CharacterPosition(int row, int col, char character) {
        this.row = row;
        this.col = col;
        this.character = character;
    }
}

Statt einfach nur ein '{' auf den Stack zu legen, verwendest Du also ein Objekt vom Typ CharacterPosition. Die Zeilen und Spalten kannst Du in den Schleifen mitzählen.

 

[Heinrich500]

Aso vielen Dank🙂
Was mir gerade noch leider erst jetzt auffällt, muss ich alles in einer Klasse machen.
Geht es theoretisch die class CharacterPosition mit in die Klasse Klammer einzubetten?

 

[mihe7]

Ja:

class Klammer {
    static class CharacterPosition {
    ...
    }
}

 

[Heinrich500]

Aha gut🙂

List<String> lines = new ArrayList<>(); try(BufferedReader in = new BufferedReader(new FileReader (CP_file))) { String line; while ((line = in.readLine()) != null) { lines.add(line); } } for (String line : lines) { verarbeite(line); }

Wie zähle ich jetzt die Zeilen genau. Ich lese ja damit alles auf einmal ein.

 

[mihe7]

Naja, Du hast die Zeilen ja jetzt in einer Liste und die ist "nummeriert":

for (int row = 0, n = lines.size(); row < n; row++) {
    String line = lines.get(row);
}

row ist der Zeilenindex, die Zeilennummer (für die Ausgabe) wäre dann row+1.

 

[Heinrich500]

Aber woher weis ich dann, wann die Klammer in der nächsten Zeile steht?

 

[mihe7]

Wie meinst Du das? Du gehst ja Zeile für Zeile und jede Zeile Zeichen für Zeichen durch. Wenn Du auf eine öffnende Klammer stößt, kennst Du also Zeile (row), Spalte (col) und das Zeichen (ch) mit der öffnenden Klammer. Dann legst Du ein new CharacterPosition(row, col, ch) auf den Stack.

Stößt Du auf eine schließende Klammer, kennst Du wieder die Zeile (row), Spalte (col) und das Zeichen (ch) mit der schließenden Klammer. Auf dem Stack liegt ggf. die CharacterPosition der öffnenden Klammer.

 

[Heinrich500]

Ok ja jetzt habe ich es. Man geht ja hier die Zeilen entlang:

for (String line : lines) {
            verarbeite(line);
        }

Das Problem ist, dass ich die Methoden mit Objekten nicht ausführen kann, z.b ist push so implementiert:

public void push(T t) {
        
        StackNode<T> tmp=new StackNode<T>(t);
        tmp.next=topElement;
        topElement=tmp;
        counter++;
    }

Wie kann man das dann machen?

 

[mihe7]

Ich weiß nicht, was Du hier betreibst:

import java.util.*;

public class Klammern {
    static class CharacterPosition {
        public final int row;
        public final int col;
        public final char character;

        public CharacterPosition(int row, int col, char character) {
            this.row = row;
            this.col = col;
            this.character = character;
        }
    }

    public static void process(List<String> lines) {
        Stack<CharacterPosition> positions = new Stack<>();
        for (int row = 0, n = lines.size(); row < n; row++) {
            String line = lines.get(row);
            for (int col = 0, m = line.length(); col < m; col++) {
                char ch = line.charAt(col);
                if (ch == '(') {
                    positions.push(new CharacterPosition(row, col, ch));
                }
            }
        }

        while (!positions.isEmpty()) {
            CharacterPosition pos = positions.pop();
            System.out.printf("%c gefunden in Zeile %d, Spalte %d\n", pos.character, pos.row+1, pos.col+1);
        }
    }

    public static void main(String[] args) {
        List<String> lines = Arrays.asList(
            "Dies ist ein Beispiel (wirklich), das zeigt, ",
            "dass Positionen (Zeilen und Spalten) von Klammern ",
            "ausgegeben werden");
        Klammern.process(lines);
    }
}

 

[Heinrich500]

Ich bin selber etwas verwirrt. Vielen Dank für dein Programm. Jetzt muss ich noch einbauen, dass Klammerpaare erkannt werden. Solte man dazu die while-Schleife entfernen und nach dem

 if(ch=='('))

folgendes einbauen:

else if(c == ')') {
                if(!stack.empty() && stack.pop() == '(') {
                printMatch(row, col, ch)
                }

 

[Heinrich500]

 public static void process(List<String> lines) {
        Stack<CharacterPosition> positions = new Stack<>();
        for (int row = 0;row <  lines.size(); row++) {
            String line = lines.get(row);
            for (int col = 0, m = line.length(); col < m; col++) {
                char ch = line.charAt(col);
                if (ch == '(' || ch == '[' || ch == '{' ) {
                    positions.push(new CharacterPosition(row, col, ch));
                }
                else if(ch == ']') {
                    if(!positions.empty() || positions.pop() != '[') {
                       Printall(row,col,ch);
                    }
                }
                else if(ch == ')') {
                    if(!positions.empty() || positions.pop() != '(') {
                        Printall(row,col,ch);
                    }           
                }
                else if(ch == '}') {
                    if(!positions.empty() || positions.pop() != '{') {
                        Printall(row,col,ch);
                    }
                }
            }   
        }     
        

      
    }

Das Problem ist, dass

positions.pop() != '[')

nicht funktioniert. Folgender Fehler:
Incompatible operand types Klammer.CharacterPosition and char
Wie kann ich das lösen?

 

[mihe7]

positions.pop() liefert ein Objekt vom Typ CharacterPosition. Daher musst Du mit den Methoden/Attributen dieses Typs arbeiten:

CharacterPosition p = positions.pop();
if (p.character == '}') {
...
}

 

[Heinrich500]

Ist nicht so schön wsl, aber wäre das dann insgesamt korrekt:

  if (ch == '(' || ch == '[' || ch == '{' ) {
                    positions.push(new CharacterPosition(row, col, ch));
                }
              
                else if(ch == ']') {
                    CharacterPosition p = positions.pop();
                    if(!positions.empty() && p.character == ']') {
                       Printall(row,col,ch);
                    }
                }
                else if(ch == ')') {
                    haracterPosition p = positions.pop();
                    if(!positions.empty() && p.character == ')') {
                        Printall(row,col,ch);
                    }           
                }
                else if(ch == '}') {
                    CharacterPosition p = positions.pop();
                    if(!positions.empty()&& p.character == '}') {
                        Printall(row,col,ch);
                    }

 

[Heinrich500]

Ist das ok?

 

[mihe7]

Nein, Du kannst nicht erst vom Stack was rausnehmen und dann nachschauen, ob er vielleicht leer war 🙂

 

[Heinrich500]

Oh man. Tut mir leid. Also dann wäre es doch beispielhaft so:

 else if(ch == ']') {
                    
                    if(!positions.empty()) {
                        CharacterPosition p = positions.pop();
                        if(p.character == ']') {
                            Printall(row,col,ch);
                        }   
                    }
                }

 

[mihe7]

Oh man. Tut mir leid.

Mir macht das nichts, es ist ja Dein Code 🙂 Das Beispiel sieht besser aus.

 

[Heinrich500]

Danke🙂 In meiner main-Methode läuft das einlesen dann so:

String path = args[0];
        File CP_file = new File(path);
        BufferedReader in = new BufferedReader(new FileReader (CP_file));
             List<String> lines = new ArrayList<String>();
             String line;
             while ((line = in.readLine()) != null) {
                    lines.add(line);
             }
             CheckBracketExpressions.process(lines);

Wäre das ok. Ich bin mir nicht ganz sicher

 

[mihe7]

Das sieht nicht unvernünftig aus.

 

[Heinrich500]

Vielen Dank.
Ich habe ja immer die printall-Methode verwendet. Jedoch brauche ich nicht nur 3 sondern 6 Parameter. Ich habe dann diese wie folgt implementiert:

 public static void printMatch(int rowL, int columnL, char leftBracket, int rowR, int columnR, char rightBracket) {
        System.out.println( "Matching brackets: '" + leftBracket+ "' at line " + rowL + ", column " + columnL
                + " and '" + rightBracket + "' at line " + rowR + ", column " + columnR );
    }

Wie füge ich die am besten nun in das Programm ein?

 

[mihe7]

Jetzt schau Dir mal Deinen Code an:

                else if(ch == ']') {
                        CharacterPosition p = positions.pop();
                        if(p.character == ']') {
                            Printall(row,col,ch);
                        }

Wie Du siehst, hast Du: row, col, ch und... p. Dabei sind row, col, ch die Zeile, Spalte und das Zeichen der schließenden Klammer. In p findest Du die Angaben für die linke Klammer: p.col, p.row, p.character.

Da fällt mir auf, dass mir vorhin ein Fehler unterlaufen ist: die if-Bedingung muss natürlich die öffnende Klammer prüfen:

                else if(ch == ']') {
                        CharacterPosition p = positions.pop();
                        if(p.character == '[') {
                            Printall(row,col,ch);
                        }

 

[Heinrich500]

Vielen Dank. Es hat geklappt🙂
Jetzt stimmen nur nicht die Indizes der Zeilen und Spalten.

lse if(ch == ']') {
                    
                    if(!positions.empty()) {
                        CharacterPosition p = positions.pop();
                        if(p.character == '[') {
                            printMatch(p.row,p.col,p.character, row, col,ch);
                        }   
                    }
                }

Müsste ich nicht row, col jeweils um 1 erhöhen?

 

[mihe7]

Ja, row und col sind Indizes (beginnend bei 0). Für die Ausgabe der Spalten- und Zeilennummern musst du jeweils um 1 erhöhen: printMatch(p.row+1, p.col+1, p.character, row+1, col+1, ch);

 

[Heinrich500]

Edit: Fehler gefunden. Tut mir leid.

 

[mihe7]

Kannst Du mal Deinen Code im Zusammenhang posten?

Nachtrag: brauchst Du dann nicht mehr.

 

[Heinrich500]

Es geht. Ich habe
if(p.character == ']') nicht verändert. Jetzt funktioniert es.
Es soll noch eine Fehlerbehandlung durchgeführt werden:
printUnmatchedClosingBracket: Erhält als Parameter die Zeile und Spalte der gefundenen, schließenden Klammer, welche eingelesen wurde, obwohl der Stack leer ist.
Das habe ich dann wie folgt, umgesetzt:

else if(ch == ']') {
                   
                    if(!positions.empty()) {
                        CharacterPosition p = positions.pop();
                        if(p.character == '[') {
                            printMatch(p.row+1,p.col+1,p.character, row+1, col+1,ch);
                        }  
                    }
                    else {
                        printUnmatchedClosingBracket(row+1, col+1,ch);
                    }
                }

Jedoch scheint das nicht richtig zu sein, Wenn ich in den else Zweig komme, dann ist doch der Stack leer?

 

[mihe7]

Es gibt zwei Fälle:
1. der Stack enthält z. B. ein '(', wenn Du auf ein ']' triffst: unmatched 🙂
2. der Stack ist leer, wenn Du auf eine schließende Klammer triffst.

 

[mihe7]

Und: es gibt noch einen weiteren Fall. Wenn alle Zeilen verarbeitet wurden und der Stack nicht leer ist, dann hast Du öffnende Klammern, die nicht geschlossen wurden.

 

[Heinrich500]

Ganz kurz: Deinen 2. Fall habe ich ja schon mit

else { printUnmatchedClosingBracket(row+1, col+1,ch); }

abgearbeitet.

 

[mihe7]

Ja.

 

[Heinrich500]

1. der Stack enthält z. B. ein '(', wenn Du auf ein ']' triffst: unmatched

Ich muss das ja am Anfang z.b von

if else ch==']

prüfen.

else if(ch == ']') {
                    CharacterPosition x = positions.top();
                    if(x.character!='[') printUnmatchedClosingBracket(row+1, col+1,ch);
                    if(!positions.empty()) {
                        CharacterPosition p = positions.pop();
                        if(p.character == '[') {
                            printMatch(p.row+1,p.col+1,p.character, row+1, col+1,ch);
                        }   
                    }
                    else {
                        printUnmatchedClosingBracket(row+1, col+1,ch);
                    }
                }

Etwas redudant, was sagst du?

 

[mihe7]

Du hast ein inneres if... auch das darf ein else haben 🙂

 

[Heinrich500]

Dann so:

lse if(ch == ']') {
                    
                    if(!positions.empty()) {
                        CharacterPosition p = positions.pop();
                        if(p.character == '[') {
                            printMatch(p.row+1,p.col+1,p.character, row+1, col+1,ch);
                        }
                        else {
                            printUnmatchedClosingBracket(row+1, col+1,ch);
                        }
                    }
                    else {
                        printUnmatchedClosingBracket(row+1, col+1,ch);
                    }
                }

Den letzen Fall weis ich nicht genau, wo ich den unterbringen soll,

 

[mihe7]

Nach der Schleife:

while (!positions.empty()) {
    CharacterPosition p = positions.pop();
    printUnmatchedOpeningBracket(p.row+1, p.col+1, p.character);
}

 

[Heinrich500]

Funktioniert leider nicht ganz: Siehst du den Fehler?

public static void process(List<String> lines) {
        Stack<CharacterPosition> positions = new Stack<>();
        for (int row = 0;row <  lines.size(); row++) {
            String line = lines.get(row);
            
            for (int col = 0; col < line.length(); col++) {
                    char ch = line.charAt(col);
                
                
                if (ch == '(' || ch == '[' || ch == '{' ) {
                    positions.push(new CharacterPosition(row, col, ch));
                }
              
                else if(ch == ']') {
                    
                    if(!positions.empty()) {
                        CharacterPosition p = positions.pop();
                        if(p.character == '[') {
                            Main.printMatch(p.row+1,p.col+1,p.character, row+1, col+1,ch);
                        }
                        else {
                            Main.printUnmatchedClosingBracket(row+1, col+1,ch);
                        }
                    }
                    else {
                        Main.printUnmatchedClosingBracket(row+1, col+1,ch);
                    }
                }
                else if(ch == ')') {
                     if(!positions.empty()) {
                         CharacterPosition p = positions.pop();
                         if(p.character == '(') {
                             Main.printMatch(p.row+1,p.col+1,p.character, row+1, col+1,ch);
                         }
                         else {
                            Main.printUnmatchedClosingBracket(row+1, col+1,ch);
                        }
                     }
                     else {
                         Main.printUnmatchedClosingBracket(row+1, col+1,ch);
                     }
                }
                else if(ch == '}') {
                     if(!positions.empty()) {
                         CharacterPosition p = positions.pop();
                         if(p.character == '{') {
                             Main.printMatch(p.row+1,p.col+1,p.character, row+1, col+1,ch);
                         }
                         else {
                            Main.printUnmatchedClosingBracket(row+1, col+1,ch);
                        }
                     }
                     else {
                         Main.printUnmatchedClosingBracket(row+1, col+1,ch);
                     }
                }   
            } 
        }
        while (!positions.empty()) {
        CharacterPosition p = positions.pop();
        Main.printUnmatchedOpeningBracket(p.row+1, p.col+1, p.character);
        }
    }

 

[mihe7]

Funktioniert leider nicht ganz

Was funktioniert nicht?

 

[mihe7]

Ah:

while (!positions.isEmpty()) {

muss es heißen.

 

[Blender3D]

Vielen Dank.
Ich habe ja immer die printall-Methode verwendet. Jedoch brauche ich nicht nur 3 sondern 6 Parameter. Ich habe dann diese wie folgt implementiert:

Eigentlich genügen 2 Parameter.

public static void printMatch(CharacterPosition pOpen, CharacterPosition pClose) {
        System.out.println( "Matching brackets: '" + pOpen.character + "' at line " + pOpen.row + ", column " + pOpen.col
                + " and '" + pClose.character + "' at line " + pClose.row + ", column " + pClose.col );
    }

 

[mihe7]

Eigentlich genügen 2 Parameter.

Normal ja. Soweit ich ihn verstanden hatte, ist die Methode vorgegeben ist (zwecks Testcase). Allerdings: eine Wrapper-Methode hätte nicht geschadet 🙂