So drucken Sie die verschiedenen Möglichkeiten der Zeichenfolge in Klammern

Question

Ich muss ein Programm schreiben, das alle verschiedenen Möglichkeiten zum Klammern einer Zeichenfolge zurückgibt. Zum Beispiel, wenn die gegebene Zeichenfolge „ABCD“ ist, dann haben wir genau diese fünf unterschiedlichen Ergebnisse:

((ab)c)d  (a(bc))d  (ab)(cd)  a((bc)d)  a(b(cd)) 

Die Anzahl der Klammern sind abhängig von der Länge der Saite natürlich, aber ich dachte, dass die Länge die Zeichenfolge-2 ist geeignet (wir haben keine Ahnung von der Anzahl der Klammern, die wir verwenden können ...). Es scheint einfach zu sein: Ich muss nur Klammern in jede mögliche Position einfügen. Ich denke, dass Rekursion hier geeignet ist.

Ich habe versucht, dies zu schreiben:

private static ArrayList<String> generateParens(String string, ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) { 
    if (leftRem < 0 || rightRem < leftRem) return null; 
    if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */ 
     String s = String.copyValueOf(str); 
     list.add(s); 
    } else { 
     if (leftRem > 0) { // try a left paren, if there are some available 
      str[count] = '('; 
      str[count+1] = string.charAt(count); 
      generateParens(string, list, leftRem - 1, rightRem, str, count+1); 
     } 
     if (rightRem > leftRem) { // try a right paren, if there’s a matching left 
      str[count] = string.charAt(count); 
      str[count+1] = ')'; 
      generateParens(string, list, leftRem, rightRem - 1, str, count + 1); 
     } 
    } 


    return list; 
} 

public static ArrayList<String> generateParens(String string) { 
    char[] str = new char[string.length()*2]; //because we have a PAIR of parenthese 
    ArrayList<String> list = new ArrayList<String>(); 
    String str2 = string + string; 
    return generateParens(str2, list, string.length()-2, string.length()-2, str, 0); 
} 

ich eine rekursive Funktion zu schreiben versucht, aber ich bin nicht sehr gut in Rekursion, so habe ich eine Menge Probleme, vor allem mit Indizes. Ich habe viele Dinge ausprobiert, aber ich habe immer noch Probleme. Ich bin mir nicht sicher, ob es nur an den Indizes liegt).

Können Sie mir bitte helfen, das zu beheben?

Answer 1

Sie denken dies als ein Problem der Zeicheneinfügung. Ich schlage eine andere Sichtweise vor.

Betrachten Sie dies als einen algebraischen Ausdruck, vielleicht a + b/c - d, aber ohne Regeln der Betreiber Vorrang. Sie müssen alle möglichen verschiedenen Möglichkeiten finden, um dies zu berechnen: welche Operationen kommen zuerst, zweite und dritte. Eine andere Möglichkeit, es anzuzeigen, besteht darin, dass Sie alle möglichen binären Bäume erstellen müssen, die vier Blattknoten haben. Dies gibt uns die Ausdrücke

((a+b)/c)-d (a+(b/c))-d (a+b)/(c-d) a+((b/c)-d) a+(b/(c-d)) 

Ich bleibe bei der Algebra-Idee für jetzt. Sie haben recht, dass Sie in jeder abgeschlossenen Lösung genau N-2 Klammerpaare benötigen. Sie haben N-1-Operationen, und alle außer dem letzten (äußerster Operator) benötigen ein Paar Klammern.

Ich schlage vor, dass Sie am unteren Rand des Baumes und arbeiten Sie Ihren Weg nach oben starten. Behalten Sie eine Liste der Zeichenfolgen bei, denen Sie beitreten müssen. Wählen Sie in jeder Iteration ein Paar Zeichenfolgen aus, die verknüpft werden sollen. Halte Klammern um sie und wiederhole sie mit der kürzeren Liste. Wenn die Liste nur aus zwei Elementen besteht, verketten Sie sie ohne den äußersten Klammersatz. Zum Beispiel in der zweiten Zeichenfolge bekommen, würde die Sequenz so etwas wie dies funktioniert, Klammern für die Liste (Array-Notation?):

private static genParen(leaves) // is the protocol. Now for the execution sequence ... 

call genParen(["a", "b", "c", "d"]) 
// Pick the second join ... 
// Concatenate the 2nd & 3rd items; add parentheses 
leaves[1] = "(" + leaves[1] + leaves[2] + ")" 
// Delete item 2 from leaves, and recur: 
    call genParen(["a", "(bc)", "d"]) 
    // This time, pick the first join ... 
    leaves[0] = "(" + leaves[0] + leaves[1] + ")" 
    // Delete item 1 from leaves, and recur: 
    call genParen(["(a(bc))", "d"]) 
    // There are now only 2 elements remaining, so ... 
    return leaves[0] + leaves[1] 

Nun, wie Sie wieder auf den Baum gehen, können Sie jede Lösung hinzufügen zu einer Liste von Lösungen, die Sie verwalten.

Die Verknüpfungslogik "erste Auswahl" oder "zweite Auswahl" ist nicht von Hand zu winkeln: Ihre Funktion muss nacheinander jede mögliche Auswahl durchlaufen: Für eine Liste von N Elementen haben Sie N-1 mögliche Auswahlmöglichkeiten. Sie müssen jedes, wiederholen Sie mit der kürzeren Liste, und speichern Sie die Ergebnisse.

Außerdem müssen Sie Ihre Liste der Ergebnisse sehen, wie es Möglichkeiten gibt, eine Ausgabezeichenfolge zu duplizieren. Zum Beispiel gibt es zwei Möglichkeiten, (ab) (cd) zu generieren, je nachdem, welches Blattpaar Sie zuerst auswählen.

Ist das genug, um Sie zu einer Lösung zu bewegen?