Wieso funktioniert der Code zur Prüfung richtiger Klammersetzung nicht?
Hallo,
ich weiß, ich bin nicht so gut. Allerdings verstehe ich nicht, wie das richtig gehen würde. Was mache ich falsch?
Bitte ohne alles zu ändern, sprich Stack und Co.
public class Solution {
public bool IsValid(string s) {
if (s.Length % 2 != 0) {
return false;
}
char[] marks = new char[] { '(', ')', '[', ']', '{', '}' };
for (int i = 0; i < s.Length / 2; i++) {
for (int j = 0; j < marks.Length; j++) {
if (s[i] == marks[j] && s[s.Length - 1 - i] != marks[j + 1]) {
return false;
}
}
}
return true;
}
}
Es geht um einen Algorithmus, der schaut, ob Klammern richtig gesetzt worden sind:
()[) -> false,
()[]([]) -> true
3 Antworten
Ich möchte jetzt nicht speziell auf Deinen Code eingehen, sondern sondern generelle Fallstricke aufzeigen, welche so ziemlich alle "scheinbar" funktionierende Lösungen zu Fall bringen können.
Das Netz ist voll von recht guten Ansätzen, welche im Idealfall recht gut funktionieren::
- https://www.google.com/search?q=java+balanced+brackets+in+string
- https://www.baeldung.com/java-balanced-brackets-algorithm
Aber da gibts Murphys Gesetz und da ist nichts Ideal. es kommt auch auf den zu untersuchenden Text/Code an. Je nach Sprache des zu untersuchenden Codes muss man Kommentare , Stringdeklarationen ausschließen
Hier einfach mal ein ganz fieses Beispiel eine zu untersuchenden Powershellcodes: (der dir jeden simplen "Zähler" um die Ohren fliegen lässt)
$ESC = [char]0x1b
for ($red=0; $red -le 1000; $red+=10 ){
#ANSI-Escapesequenzen sind schon besonders :)
"$ESC[48;2;$(($red+3)%255);2;0;38;2;128;255;0mIch bin mit RGB-Sequenzen gefaerbt :) Rotanteil:""$(($red+3)%255)""$ESC[0m"
}
Die Klammern sind tatsächlich ausgeglichen. Algoritmus müsste allerdings #Kommentartext , 'Literal' und "Stringdeklaration" ausschließen. Aber jetzt kommt es noch dicker... innerhalb der Stringdeklaration habe ich auch Laufzeitfunktionen deklariert $(Functionexecution), welche im Extremfall auch ihrerseits ineinander verschachtelte Klammen enthalten könnten. die müsste dann wieder berücksichtigt werden 🤮 Ich hab nur mal Powershellcode als Text gewählt um die Sache auf die Spitze zu treiben.
Auch zu untersuchende Texte in andern Programmiersprachen enthalten Kommentare und andere Konstrukte, welche einen primitiven (Zähl)Algorithmus aus den Tritt bringen würden:.
Java
/* lass uns über schließende Klammerzeichen:
)]}>
reden*/
System.out.println("Hallo Textsmilie :)"); // Kommentar :)
Javascript (RegEx-Pattern werden nicht als "String" deklariert! ---ganz böse Falle---)
let text = "Ein Smilie :)";
let result = text.match(/:\)/i);
...spätestens an diesem Punkt würde ein simpler Zähler/Stack aus dem tritt kommen
Ich weiß nicht was Du letztlich vorhast und wie universell ensetzbar Dein Algorithmus sein soll?ich wollte Dir lediglich aufzeigen, dass es nicht einfach genügt die Klammern Hoch und Runter zu zählen. Je nach Sprache musst Du auch noch unterscheiden was funktionale Klammen sind und welche Klammern uninteressant sind.
Ich würde es so umsetzen das quasi die Tiefe innerhalb wie vieler Klammern man sich befindet geschaut wird (ich weiß ist nicht so gut erklärt).
Mal als etwas Detaillierter:
Ich würde alle Zeichen in einer foreach-Schleife (klar geht auch for) durchgehen und einen int der die Tiefe angibt (außerhalb der Schleife deklariert) definieren. Wenn eine Öffnende Klammer gefunden wird der int inkrementiert wird und bei einer Schließender Klammer dekrementiert und am ende wird geschaut ob der int der die Tiefe angibt gleich 0 ist. Wenn es sich um verschiedene Klammerarten handelt musst du allerdings für jede Art ein eigenen int machen.
lg Suiram1
Hab was übersehen.
Das hier würde abgedeckt werden: ()[)
Allerdings sowas: (][) würde obwohl es falsch ist als true ausgewertet werden, da von jeder Art gleich viele Öffnende und schließende klammer vorhanden sind.
Um eine Art stack kommst du also nicht herum. Musst du wohl eher die Antwort von @iQax ausprobieren. Wieso willst du eigentlich keinen stack nutzen?
Das funktioniert nicht, weil du davon ausgehst, das die schließende Klammer an der gleichen Position steht wie die öffnende, nur "von Hinten". Das geht aber schon bei ()[] schief.
Du musst dir jeweils die öffnende Klammer merken.
char stack[50]; // maximale Klammerebenen
int sp=0; // Stackpointer
char[] marks = new char[]{'(',')','[',']','{','}'};
for (int i = 0; i < s.Length; i++){
for(int j = 0; j < marks.Length; j++){
if (s[i] == marks[j]) {
if (j%2==0) { //öffnende Klammer
stack[sp++]=marks[j+1]; // passende schließende auf den Stack
} else { // schließende Klammer
if (sp==0) return false; // keine öffnende da
if (stack[--sp]!=marks[j]) return false; // falsche Klammer
}
} //if
} //for
} //for
if (sp>0) return false; // mehr öffnend als schließend
return true;
PS: Ohne Garantie, da sind bestimmt Syntaxfehler drin. Ohne Stack oder dir irgendwie die Reihenfolge der Klammern zu merken geht es nicht.
Das funktioniert aber nicht wenn in Strings/Kommentaren (warum auch immer) solitäre Klammern stehen. ...und nahezu jede Sprache hat ihre ganz speziellen Regeln ...
Und dann kommt ein Kommentar mit einem Smiley :-) und interpretiert es als schließende Klammer
Danke werde es ausprobieren :)