Stacks wohlgeformte Klammerausdrücke

dan1996

Aktives Mitglied
Hallo zusammen,

ich arbeite grade an einer Aufgabe in der das Programm überprüft, ob eine Folge von Klammern wohlgeformt ist
z.B.:
wohlgeformt: ([()])
nicht wohlgeformt: {(})

bis jetzt habe ich alle offenen Klammer in mein Stack gepusht und wenn ich eine geschlossene Klammer gefunden habe und die die letze offene Klammer im Stack dazu passt, entferne ich die offene Klammer wieder vom Stack.

Doch irgendwie klappt das nicht ganz, heißt er entfernt nicht alle Klammern vom Stack, obwohl es wohlgeformt ist..

finde meinen Fehler nicht, hat jemand einen Ratschlag?

Code:
public class Aufgabe6 {

    public static void main(String[] args) {
        Keller t = new Keller();
        t.klammerCheck("()[]{}");
        System.out.println(t);
    }

}

class Keller {
    private Object item = "";
    private Keller next;

    public Keller() {
        next = null;
    }

    public boolean isEmpty() {
        return next == null;
    }

    public void push(Object x) {
        Keller l = new Keller();
        l.item = x;
        l.next = next;
        next = l;
    }

    public void pop() {
        next = next.next;
    }

    public Object top() {
        return next.item;
    }

    public String toString() {
        if (isEmpty())
            return "";
        if (!next.isEmpty())
            return "" + next.item + " -> " + next.toString();
        return "" + next.item;
    }

    public void klammerCheck(String klammer) {

        for (int i = 0; i <= klammer.length() - 1; i++) {
            if (klammer.charAt(i) == '(' || klammer.charAt(i) == '[' || klammer.charAt(i) == '{') {
                push(klammer.charAt(i));
            }
        }
        
        for (int i = 0; i <= klammer.length() - 1; i++) {
        
            switch(klammer.charAt(i)) {
            case ')':
                if (next.item.equals((char) '(')){
                pop();
                break;
                
                }
            case '}':
                if(next.item.equals((char) '{')){
                pop();
                break;
                
                }
            case ']':
                if(next.item.equals((char) '[')){
                pop();
                break;
                
                }
            default: continue;
            
            }
            
        }
        
        if (isEmpty()) {
            System.out.println("die Klammer ist Wohlgeformt");
        } else {
            System.out.println("Klammer ist nicht wohlgeformt");
        }

    }
}
 

mihe7

Top Contributor
finde meinen Fehler nicht, hat jemand einen Ratschlag?
Zwei Dinge:
1. Du darfst nicht im Vorfeld alle öffnenden Klammern auf den Stack legen, das musst Du - wie die schließenden Klammern - während des Durchlaufs machen.
2. Du musst aufpassen, dass ein nicht-wohlgeformter Ausdruck nicht doch zu einem leeren Stack führt...
 

dan1996

Aktives Mitglied
okay danke funktioniert endlich
Code:
public void klammerCheck(String klammer) {
        
        if(klammer.length() <= 0) {
            throw new IllegalArgumentException("Keine Klammern gegeben");
        }

        
        for (int i = 0; i <= klammer.length() - 1; i++) {
            
            if (klammer.charAt(i) == '(' || klammer.charAt(i) == '[' || klammer.charAt(i) == '{') {
                push(klammer.charAt(i));
            }
            
            switch(klammer.charAt(i)) {
            case ')':
                if (next.item.equals((char) '(')){
                pop();
                break;
                
                }
            case '}':
                if(next.item.equals((char) '{')){
                pop();
                break;
                
                }
            case ']':
                if(next.item.equals((char) '[')){
                pop();
                break;
                
                }
            default: continue;
            
            }
            
        }
        
        if (isEmpty()) {
            System.out.println("die Klammer ist Wohlgeformt");
        } else {
            System.out.println("Klammer ist nicht wohlgeformt");
        }

    }

doch kurze frage, warum hat meine erste Variante nicht geklappt, also warum kann ich nicht erst alle offenen Klammern pushen und dann nach und nach wieder entfernen ?
 

mihe7

Top Contributor
also warum kann ich nicht erst alle offenen Klammern pushen und dann nach und nach wieder entfernen ?
Nehmen wir mal an, Du hast einen String mit drei öffnenden Klammern. Jetzt nimmst Du drei Zettel und gehst jedes Zeichen des Strings durch. Wenn Du auf eine öffnende Klammer triffst, schreibst Du diese auf einen Zettel und legst den Zettel auf einen Stapel.

Beispiel: "()[]{}" führt dazu, dass auf dem untersten Zettel "(" steht und auf dem obersten "{".

Um nun zu überprüfen, ob der Ausdruck wohlgeformt ist, fängst Du jetzt wieder am Anfang an und triffst auf die schließende Klammer ")". Oben auf dem Stapel liegt aber ein "{". Also wird nichts vom Stapel genommen. Das gleiche gilt, wenn Du auf "]" triffst. Erst am Ende bekommst Du ein "}" und entfernst den obersten Zettel vom Stapel. Darunter liegen aber noch die zwei anderen.

okay danke funktioniert endlich
Wenn ich es richtig sehe, dürfte Punkt 2 noch offen sein. Dein Algorithmus dürfte "()[))))))]" als wohlgeformt erkennen.
 

httpdigest

Top Contributor
Streng genommen benötigst du gar keine dedizierte Stack Datenstruktur. Wenn du einen String als "Stack" missbrauchen willst, könntest du es auch so machen:
Java:
public class Klammerausdruck {
  private static final String open = "([{", close = ")]}";
  private static boolean isDyckSentence(String str) {
    return str.chars().boxed().reduce("", (p, c) -> {
      int index;
      return ((index = open.indexOf(c)) >= 0)
          ? p + (char) index
          : ((index = close.indexOf(c)) >= 0)
              ? (p.charAt(p.length() - 1) == index)
                  ? p.substring(0, p.length() - 1)
                  : "!" // <- Fehler!
              : p;
    }, String::concat).equals("");
  }
  public static void main(String[] args) {
    System.out.println(isDyckSentence("()[]{([])}")); // <- false
    System.out.println(isDyckSentence("()[]{([)])}")); // <- true
  }
}
 

mihe7

Top Contributor
Geschweige denn schreiben...
Wobei... :p
Java:
public class Klammern {
    private static final String OPENING = "([{";
    private static final String CLOSING = ")]}";

    public boolean checkKlammern(String s) {
        return checkKlammern(s, 0, -1, 0) != -1;
    }

    private int checkKlammern(String s, int pos, int klammer, int level) {
        if (pos >= s.length()) {
            return level == 0 ? pos : -1;
        }
        char ch = s.charAt(pos);
        if (ch == klammer) {
            return pos+1;
        }
        if (CLOSING.indexOf(ch) != -1) {
            return -1;
        }    

        int index = OPENING.indexOf(ch);
        if (index == -1) {
            return checkKlammern(s, pos+1, klammer, level);
        }

        char closing = CLOSING.charAt(index);
        index = checkKlammern(s, pos+1, closing, level+1);
        if (index == -1) {
            return -1;
        }
        return checkKlammern(s, index, klammer, level);
    }

    public static void main(String[] args) {
        System.out.println(new Klammern().checkKlammern(args[0]));
    }
}
 

Ähnliche Java Themen

Neue Themen


Oben