Klammerung bei Strings

[ocsme]

Guten Tag,

ich komme hier nicht wirklich weiter 🙁
Möchte mir eine Methode schreiben die Überprüft ob ein String richtig geklammert ist.
Also z. B. ist dieser String richtig geklammert: 3+(4-5[as])%()[[(bfg)]] falsch wäre sowas: ([dfdf)a] da die Runde klammer später zu gehen muss. Hier ist mal mein Anfang. Bis jetzt habe ich nur überprüft ob die summe der Klammern stimmen sprich wenn eine Runde, Eckige oder Geschweifte Klammer auf geht muss auch wieder eine zu gehen wenn mehr zu gehen ist es Falsch.
Doch wie mache ich das nun wenn sich eine Klammer vordrängeln würde. Hat da jemand einen Tipp?

        String s="[as(dd])f)adf()";
        char[] c=s.toCharArray();
        int rcounter=0;
        int ecounter=0;
        int gcounter=0;
        for(int i=0;i<c.length;i++) {
            if(c[i]=='(')
                rcounter++;
            else if(c[i]=='[')
                ecounter++;
            else if(c[i]=='{')
                gcounter++;
            else if(c[i]=='}') {
                gcounter--;
                if(gcounter<0)
                    System.out.println("Fehler");
            }
            else if(c[i]==']') {
                ecounter--;
                if(ecounter<0)
                    System.out.println("Fehler");
            }
            else if(c[i]==')') {
                rcounter--;
                if(rcounter<0)
                    System.out.println("Fehler");
            }
       
        }

Danke im voruas 🙂

lG

 

[Xyz1]

Das geht mit einem sg Rangierbahnhof, aber der String s iss nicht vollständig geklammert. 🙁

 

[Robat]

Hier mal als Pseudocode:

- Stack für die Character deklarieren
- für jedes Zeichen currentChar im String 
   - wenn currentChar gleich '(', '{' oder '[' ist
      - currentChar auf den Stack pushen
   - wenn currentChar gleich ')', '{' oder ']' ist
      - pop Zeichen von Stack und speicher es in a
      - wenn a nicht das öffnende Pendant zu currentChar ist
          - Fehler gefunden

 

[ocsme]

Ich weiß leider derzeit nicht zu 100% ob es richtig läuft. Hab es aber mit hilfe von Prioritäten gemacht! Denke das ist so etwas in der Art was du meintest Wissender!
Denn mit deiner Aussage an sich konnte ich nicht so viel Anfangen 🙁

        String s="{as(}dd])f)adf()";
        char[] c=s.toCharArray();
        int ranger=1;
        int rangee=2;
        int rangeg=3;
        int prio=0;
        int rcounter=0;
        int ecounter=0;
        int gcounter=0;
        for(int i=0;i<c.length;i++) {
            if(c[i]=='(') {
                rcounter++;
                prio=ranger;
            }
            else if(c[i]=='[') {
                ecounter++;
                prio=rangee;
            }
            else if(c[i]=='{') {
                gcounter++;
                prio=rangeg;
            }
            else if(c[i]=='}') {
                gcounter--;
                if(prio!=rangeg)
                    System.out.println("Falsche Reihenfolge");
                if(gcounter<0)
                    System.out.println("Fehler");
            }
            else if(c[i]==']') {
                ecounter--;
                if(prio!=rangee)
                    System.out.println("Falsche Reihenfolge");
                if(ecounter<0)
                    System.out.println("Fehler");
            }
            else if(c[i]==')') {
                rcounter--;
                if(prio!=ranger)
                    System.out.println("Falsche Reihenfolge");
                if(rcounter<0)
                    System.out.println("Fehler");
            }
       
        }

 

[ocsme]

Robat danke für die Antwort.
Wie mache ich das ganze ohne Stack 😀

 

[Xyz1]

Wie mache ich das ganze ohne Stack

Gar nicht 😳

 

[Robat]

Naja ein Stack ist ja auch nur ein Array mit "besonderen" Einfügeoperationen..

 

[Xyz1]

Und ein Array mit "besonderen" Einfügeoperationen wäre nur ein Stack. 🙂

 

[Robat]

Hier mal als Beispiel .. ich persönlich würde es trotzdem mit einem Stack und ggf. einer Map machen. Damit könnte man ein paar Abfragen noch verkürzen / sich ganz sparen

public class ParantheseChecker{
 
  public static boolean hasBalancedParantheses(String expression) {
    char[] stack = new char[expression.length()];
    int stackPointer = 0;
    boolean error = false;
  
    for(char currentChar : expression.toCharArray()) {
      if(isOpeningBrace(currentChar)) {
        stack[stackPointer++] = currentChar;
      } else if(isClosingBrace(currentChar) && stackPointer > 0) {
          char c = stack[--stackPointer];
          if(noMatchingBraces(currentChar, c)) {
             return false;
          }
       }
    }
    return true;
  }
 
  private static boolean isOpeningBrace(char c) {
    return c == '(' || c == '{' || c == '[';
  }
 
  private static boolean isClosingBrace(char c) {
    return c == ')' || c == '}' || c == ']';
  }
 
  private static boolean noMatchingBraces(char closingBrace, char openingBrace) {
    switch(closingBrace) {
      case ')': return openingBrace != '(';
      case ']': return openingBrace != '[';
      case '}': return openingBrace != '{';
      default: return false;
    }
  }


  public static void main(String[] args) {
    String expression = "([])3+(4-5[as])%()[[((bfg))]]";
    if(!hasBalancedParantheses(expression)) {
        System.out.println("Fehler");
    } else {
        System.out.println("Korrekt");
    } 
  }
}

 

[Meniskusschaden]

Wie mache ich das ganze ohne Stack 😀

Du könntest es auch mit einer rekursiven Lösung versuchen. Da brauchst du keine eigene Datenstruktur, weil man den impliziten Rekursionsstack zur Abbildung der offenen Klammerebenen nutzen kann.

 

[ocsme]

Ja stimmt ich werde es später mit einem array versuchen und so eine Art von Stack mal schauen ob ich es hin bekomme.
Mit der Prio sollte es ja auch klappen wie ich es oben gemacht habe.
Meniskusschaden danke für die Antwort Rekursive Funktionen sind nicht so mein Fall da ich sie nicht wirklich hin bekomme 🙁 muss noch viel üben 😛

Robat Danke für die super Antwort zur Not werde ich das nehmen bzw. es so ähnlich dann machen 🙂 denn einen Stack bzw. Datenstrukturen zu Implementieren wollte ich eh noch =)

LG