Rekursiv überprüfen, ob ein String symmetrisch ist

Möchte ich überprüfen, ob ein String hat passende Klammern, Klammern.

For example:
{}
()
[]

Ich kann es mit einem stack. Ich möchte es mit Rekursion. Ich war das Lesen der Antworten für eine ähnliche Frage und die Antworten wurden Rekursion gemischt und in einen Stapel. Ein Benutzer reagiert auf die Antworten, die sagen, dass die Rekursion ist auch ein Stapel, damit Ihre rekursive Methode sollte nicht auf einen Stapel in der Parameter-das macht Sinn für mich.

Ich habe ein großes problem, obwohl, ich bin auf der Suche, die durch den String rückwärts und immer das entfernen der letzten Stelle, die ich überprüfen, bis der String leer, so dass ich true zurück. Ich kann nicht Bild wie überprüfe ich für die einzelnen Teile, Klammern, Klammern oder Klammern, ohne dass ich einen zusätzlichen parameter in meine Methode zu halten, was ich Suche. Aber ich denke immer es muss einen einfacheren Weg, dies zu tun.

public boolean isBalanced(String in)
{
    if(in.isEmpty())
        return true;

    if(in.charAt(in.length()) == '}')
    {
        return recIsBalanced(in.substring(0, in.length()));
    }

    else if(in.charAt(in.length()) == ']')
    {

    }


    return recIsBalanced(in.substring(0, in.length()));
}
  • Nur aus Neugier. Was für einen Vorteil Sie versuchen, zu gewinnen tun Sie dies rekursiv statt iterativ?
InformationsquelleAutor | 2013-02-18
  1. 3

    Einfachste Weg, um zu lösen dieses problem mithilfe von Rekursion ist zum verkleinern der string aus beiden Richtungen. Sie Durchlaufen von Links und von rechts, bis Sie sehen . Wenn diese nicht übereinstimmen, String ist nicht ausgeglichen, ansonsten gelten die gleichen Algorithmus für die eingeschlossene Zeichenfolge, die zwischen diesen geschweiften Klammern. Geht nur von der einen Seite wird viel schwieriger, und Sie haben zu speichern Zustand.

    EDIT: Dank DanielFischer. Tatsächlich Durchlaufen von einer Seite, z.B. Links, bis Sie finden eine Stütze(wenn diese Klammer nicht öffnen Sie eine Rückkehr false). Als Iteration von der anderen Seite(in diesem Fall rechten), bis Sie eine passende Klammer. Nun die Zeichenfolge ist ausgeglichen, wenn und nur wenn die Teilzeichenfolge eingeschlossen innerhalb dieser Klammern ist symmetrisch und die Zeichenfolge rechts neben der schließenden Klammer sind sowohl mit symmetrischen als auch mit Rekursion.

    • In meinem Verständnis "()[]{}" ausgewogen ist. Dein test würde sagen, das ist es nicht.
    • Richtig. Ich werde das beheben. Danke.
    • EDIT: Sehr interessant. Ich habe gerade gelesen Ihre "BEARBEITEN". Aber ich denke, die Lösung wäre, dass die Rückkehr von ([ )] als richtig.
    • Nein, ich glaube, Sie missverstanden mich. Sie Durchlaufen von Links und finden Sie einen ( und als Iteration von rechts(in der gleichen Ebene der Rekursion keine rekursiven Aufruf noch) und finden ). Dann machen Sie eine rekursive Aufrufe für die Teilzeichenfolge zwischen ( und ) und der Abschnitt auf der rechten ).
    • Strandjev "( und als Iteration von rechts(in der gleichen Ebene der Rekursion keine rekursiven Aufruf noch) und finden". Also innerhalb einer Schleife der rekursive Aufruf der Suche nach einer schließenden Klammer?
    • ja das ist meine Idee und ich glaube, das ist die einzige Möglichkeit, um das problem zu lösen, ohne die irgendeine Art von Zustand zwischen den verschiedenen Ebenen der Rekursion
    • Diese Methode schlägt fehl, auf "()()" durch Rücksendung "unausgewogen" und "([)]" durch Rücksendung "ausgewogen".

    InformationsquelleAutor Ivaylo Strandjev
  2. 1
     public static boolean isBalanced(String str) {

    if (str.length() == 0) {
        return true;
    }
    if (str.contains("()")) {
        return isBalanced(str.replaceFirst("\\(\\)", ""));
    }

    if (str.contains("[]")) {
        return isBalanced(str.replaceFirst("\\[\\]", ""));
    }

    if (str.contains("{}")) {
        return isBalanced(str.replaceFirst("\\{\\}", ""));
    } else {
        return false;
    }
}
    InformationsquelleAutor jot
  3. 1

    Hier ist die Lösung, nicht das ersetzen von allem, gerade Rekursion:

    /**
 * @param args
 */
public  boolean balance(String s, int start, int end)
{
   System.out.println("start:"+start + " end" + end);
   if (start == s.length()) return end == 0;
   if (end<0) return false;
   //if (end == s.length()-1) return start == 0;
   if (s.charAt(start) == '(')
     return balance(s, start+1, end+1);
   if (s.charAt(start) == ')')
     return balance(s, start+1, end-1);
   return balance(s, start+1, end );

}
    InformationsquelleAutor matthieu lieber
  4. 0

    Es getan werden kann, durch analysieren der eingegebenen Zeichenfolge. Grammatik für diesen Fall ist:

    P -> (P)
P -> [P]
P -> {P}
P -> e  (Null)

    Ist es einfacher, um die position zu verfolgen, was analysiert wird, in einen string, und dass der Rekursion-stack hält, was Klammer geschlossen werden. Hier ist ein einfaches python-Implementierung.

    ps = { '{': '}', '(': ')', '[': ']'}
all_ps = set(['{', '}', '(', ')', '[', ']'])
read_position = 0

def _is_balanced( s, closing_par=None ):
  global read_position
  while read_position < len(s):
    if s[read_position] == closing_par:
      read_position += 1         # Read closing parenthesis
      return True
    elif s[read_position] in ps:
      read_position += 1         # Read opening parenthesis
      if not _is_balanced( s, ps[s[read_position-1]] ):
        return False
    else:
      if s[read_position] not in all_ps:
        read_position += 1       # Read non-parenthesis char
      else:
        return False            # It is closing parenthesis, witouh opening before
  return closing_par is None    # Are we looking for a closing parenthesis?

def is_balanced( s ):
  global read_position
  read_position = 0  # Reset parsing position
  return _is_balanced( s )
    InformationsquelleAutor Ante
  5. 0
    boolean isBalanced(String str)
{
    if (str.isEmpty()) {
        return true;
    }
    else if (str.charAt(0) == '(') {
        return str.charAt(str.length() - 1) == ')'
            && isBalanced(str.substring(1, str.length()));
    }
    else if (str.charAt(0) == '[') {
        return str.charAt(str.length() -  1) == ']'
            && isBalanced(str.substring(1, str.length()));
    }
    else if (str.charAt(0) == '{') {
        return str.charAt(str.length() - 1) == '}'
            && isBalanced(str.substring(1, str.length()));
    }
    else {
        return true;
    }

}
    InformationsquelleAutor Chris
Schreibe einen Kommentar