wake-up-neo.com

Grundrekursion, Ausgewogene Klammer prüfen

Ich habe in der Vergangenheit eine Software geschrieben, die einen Stapel verwendet, um nach ausgeglichenen Gleichungen zu suchen, aber jetzt werde ich aufgefordert, einen ähnlichen Algorithmus rekursiv zu schreiben, um nach geschachtelten Klammern und Klammern zu suchen.

Gute Beispiele: () [] () ([] () [])

Schlechte Beispiele: ((] ([)]

Angenommen, meine Funktion heißt: isBalanced. 

Sollte jeder Durchlauf einen kleineren Teilstring auswerten (bis ein Basisfall von 2 übrig bleibt)? Oder sollte ich immer die gesamte Zeichenfolge auswerten und Indizes nach innen verschieben?

40
pws5068

Es gibt viele Möglichkeiten, dies zu tun, aber der einfachste Algorithmus besteht darin, einfach von links nach rechts vorwärts zu arbeiten und den Stapel als Parameter zu übergeben

FUNCTION isBalanced(String input, String stack) : boolean
  IF isEmpty(input)
    RETURN isEmpty(stack)
  ELSE IF isOpen(firstChar(input))
    RETURN isBalanced(allButFirst(input), stack + firstChar(input))
  ELSE IF isClose(firstChar(input))
    RETURN NOT isEmpty(stack) AND isMatching(firstChar(input), lastChar(stack))
      AND isBalanced(allButFirst(input), allButLast(stack))
  ELSE
    ERROR "Invalid character"

Hier ist es in Java implementiert. Beachten Sie, dass ich es jetzt so gewechselt habe, dass der Stack front anstelle von back der Zeichenfolge drückt, um die Bequemlichkeit zu verbessern. Ich habe es auch so modifiziert, dass es nur Nicht-Klammer-Symbole überspringt, anstatt es als Fehler zu melden.

static String open  = "([<{";
static String close = ")]>}";

static boolean isOpen(char ch) {
    return open.indexOf(ch) != -1;
}
static boolean isClose(char ch) {
    return close.indexOf(ch) != -1;
}
static boolean isMatching(char chOpen, char chClose) {
    return open.indexOf(chOpen) == close.indexOf(chClose);
}

static boolean isBalanced(String input, String stack) {
    return
        input.isEmpty() ?
            stack.isEmpty()
        : isOpen(input.charAt(0)) ?
            isBalanced(input.substring(1), input.charAt(0) + stack)
        : isClose(input.charAt(0)) ?
            !stack.isEmpty() && isMatching(stack.charAt(0), input.charAt(0))
              && isBalanced(input.substring(1), stack.substring(1))
        : isBalanced(input.substring(1), stack);
}

Testgeschirr:

    String[] tests = {
        "()[]<>{}",
        "(<",
        "]}",
        "()<",
        "(][)",
        "{(X)[XY]}",
    };
    for (String s : tests) {
        System.out.println(s + " = " + isBalanced(s, ""));
    }

Ausgabe:

()[]<>{} = true
(< = false
]} = false
()< = false
(][) = false
{(X)[XY]} = true
44

Zu Ihrer ursprünglichen Frage sollten Sie zunächst wissen, dass Sie bei sehr langen Zeichenfolgen nicht bei jedem Funktionsaufruf exakte Kopien mit Ausnahme eines einzelnen Buchstabens erstellen möchten. Sie sollten also lieber Indizes verwenden oder sicherstellen, dass Ihre bevorzugte Sprache keine Kopien hinter den Kulissen macht.

Zweitens habe ich ein Problem mit allen Antworten, die eine Stack-Datenstruktur verwenden. Ich denke, der Sinn Ihrer Aufgabe besteht darin, dass Sie verstehen, dass Ihre Funktion mit Rekursion einen Stack aufruft. Sie brauchen keine Stack-Datenstruktur für die Klammern, da jeder rekursive Aufruf ein neuer Eintrag in einem impliziten Stack ist.

Ich werde mit einem C-Programm demonstrieren, das mit ( und ) übereinstimmt. Das Hinzufügen der anderen Typen wie [ und ] ist eine Übung für den Leser. Alles, was ich in der Funktion beibehalten habe, ist meine Position in der Zeichenfolge (als Zeiger übergeben), da die Rekursion mein Stapel ist. 

/* Search a string for matching parentheses.  If the parentheses match, returns a
 * pointer that addresses the nul terminator at the end of the string.  If they
 * don't match, the pointer addresses the first character that doesn't match.
 */
const char *match(const char *str)
{
        if( *str == '\0' || *str == ')' ) { return str; }
        if( *str == '(' )
        {
                const char *closer = match(++str);
                if( *closer == ')' )
                {
                        return match(++closer);
                }
                return str - 1;
        }

        return match(++str);
}

Getestet mit diesem Code:

    const char *test[] = {
            "()", "(", ")", "", "(()))", "(((())))", "()()(()())",
            "(() ( hi))) (())()(((( ))))", "abcd"
    };

    for( index = 0; index < sizeof(test) / sizeof(test[0]); ++index ) {
            const char *result = match(test[index]);

            printf("%s:\t", test[index]);
            *result == '\0' ? printf("Good!\n") :
                    printf("Bad @ char %d\n", result - test[index] + 1);
    }

Ausgabe:

(): Good!
(:  Bad @ char 1
):  Bad @ char 1
:   Good!
(())):      Bad @ char 5
(((()))):   Good!
()()(()()): Good!
(() ( hi))) (())()(((( )))):    Bad @ char 11
abcd:       Good!
51
indiv

Die Idee ist, eine Liste der geöffneten Klammern aufzubewahren, und wenn Sie eine schließende Klammer finden, überprüfen Sie, ob die zuletzt geöffnete Klammer geschlossen wird: 

  • Wenn diese Klammern übereinstimmen, entfernen Sie das zuletzt geöffnete Element aus der Liste der geöffnetenBrackets und prüfen Sie den Rest der Zeichenfolge rekursiv
  • Ansonsten haben Sie eine Klammer gefunden, die einen einmal geöffneten Server schließt, damit er nicht ausbalanciert ist.

Wenn die Zeichenfolge endgültig leer ist und auch die Liste der Klammern leer ist (also alle Klammern geschlossen wurden), geben Sie true zurück, andernfalls false.

ALGORITHMUS(in Java):

public static boolean isBalanced(final String str1, final LinkedList<Character> openedBrackets, final Map<Character, Character> closeToOpen) {
    if ((str1 == null) || str1.isEmpty()) {
        return openedBrackets.isEmpty();
    } else if (closeToOpen.containsValue(str1.charAt(0))) {
        openedBrackets.add(str1.charAt(0));
        return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
    } else if (closeToOpen.containsKey(str1.charAt(0))) {
        if (openedBrackets.getLast() == closeToOpen.get(str1.charAt(0))) {
            openedBrackets.removeLast();
            return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
        } else {
            return false;
        }
    } else {
        return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
    }
}

PR&UUML;FUNG:

public static void main(final String[] args) {
    final Map<Character, Character> closeToOpen = new HashMap<Character, Character>();
    closeToOpen.put('}', '{');
    closeToOpen.put(']', '[');
    closeToOpen.put(')', '(');
    closeToOpen.put('>', '<');

    final String[] testSet = new String[] { "abcdefksdhgs", "[{aaa<bb>dd}]<232>", "[ff{<gg}]<ttt>", "{<}>" };
    for (final String test : testSet) {
        System.out.println(test + "  ->  " + isBalanced(test, new LinkedList<Character>(), closeToOpen));
    }
}

AUSGABE:

abcdefksdhgs  ->  true
[{aaa<bb>dd}]<232>  ->  true
[ff{<gg}]<ttt>  ->  false
{<}>  ->  false

Beachten Sie, dass ich folgende Klassen importiert habe:

import Java.util.HashMap;
import Java.util.LinkedList;
import Java.util.Map;
3
 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;
    }
}
2
jot

Aus logischer Sicht ist es nicht wirklich wichtig - wenn Sie einen Stapel aller derzeit nicht ausbalancierten Parens behalten, die Sie an jeden Schritt der Rekursion übergeben, müssen Sie niemals zurückblicken, also nicht Egal, ob Sie die Zeichenfolge bei jedem rekursiven Aufruf ausschneiden oder einfach einen Index inkrementieren und nur das aktuelle erste Zeichen betrachten.

In den meisten Programmiersprachen, die über nicht veränderliche Zeichenfolgen verfügen, ist es wahrscheinlich (in Bezug auf die Leistung) teurer, die Zeichenfolge zu verkürzen, als eine etwas größere Zeichenfolge auf dem Stack zu übergeben. Andererseits könnten Sie in einer Sprache wie C einfach einen Zeiger innerhalb des Char-Arrays erhöhen. Ich denke, es ist ziemlich sprachabhängig, welcher dieser beiden Ansätze "effizienter" ist. Beide sind aus konzeptioneller Sicht gleichwertig.

1
Adrian Petrescu

Ich würde sagen, das hängt von Ihrem Design ab. Sie können entweder zwei Zähler oder einen Stapel mit zwei verschiedenen Symbolen verwenden oder mit Rekursion umgehen.

0
func evalExpression(inStringArray:[String])-> Bool{
    var status = false
    var inStringArray = inStringArray
    if inStringArray.count == 0 {
        return true
    }

    // determine the complimentary bracket.
    var complimentaryChar = ""
    if (inStringArray.first == "(" || inStringArray.first == "[" || inStringArray.first == "{"){
        switch inStringArray.first! {
        case "(":
            complimentaryChar = ")"
            break
        case "[":
            complimentaryChar = "]"
            break
        case "{":
            complimentaryChar = "}"
            break
        default:
            break
        }
    }else{
        return false
    }

    // find the complimentary character index in the input array.
    var index = 0
    var subArray = [String]()
    for i in 0..<inStringArray.count{
        if inStringArray[i] == complimentaryChar {
            index = i
        }
    }
    // if no complimetary bracket is found,so return false.
    if index == 0{
        return false
    }
    // create a new sub array for evaluating the brackets.
    for i in 0...index{
        subArray.append(inStringArray[i])
    }

    subArray.removeFirst()
    subArray.removeLast()

    if evalExpression(inStringArray: subArray){
        // if part of the expression evaluates to true continue with the rest.
        for _ in 0...index{
            inStringArray.removeFirst()
        }
        status = evalExpression(inStringArray: inStringArray)
    }

    return status
}
0
siva k

In der Programmiersprache Scala würde ich es so machen:

  def balance(chars: List[Char]): Boolean = {

    def process(chars: List[Char], myStack: Stack[Char]): Boolean =

      if (chars.isEmpty) myStack.isEmpty

      else {
        chars.head match {
          case '(' => process(chars.tail, myStack.Push(chars.head))
          case ')' => if (myStack.contains('(')) process(chars.tail, myStack.pop)
          else false
          case '[' => process(chars.tail, myStack.Push(chars.head))
          case ']' => {
            if (myStack.contains('[')) process(chars.tail, myStack.pop) else false
          }
          case _ => process(chars.tail, myStack)
        }
      }

    val balancingAuxStack = new Stack[Char]

    process(chars, balancingAuxStack)
  }

Bitte bearbeiten Sie es, um es perfekt zu machen. 

Ich habe nur eine Umstellung in Scala vorgeschlagen.

0
MrOnyancha

PHP-Lösung zur Überprüfung ausgewogener Klammern

<?php
/**
 * @param string $inputString
 */
function isBalanced($inputString)
{
    if (0 == strlen($inputString)) {
        echo 'String length should be greater than 0';
        exit;
    }

    $stack = array();
    for ($i = 0; $i < strlen($inputString); $i++) {
        $char = $inputString[$i];
        if ($char === '(' || $char === '{' || $char === '[') {
            array_Push($stack, $char);
        }
        if ($char === ')' || $char === '}' || $char === ']') {
            $matchablePairBraces = array_pop($stack);
            $isMatchingPair = isMatchingPair($char, $matchablePairBraces);
            if (!$isMatchingPair) {
                echo "$inputString is NOT Balanced." . PHP_EOL;
                exit;
            }
        }
    }
    echo "$inputString is Balanced." . PHP_EOL;
}

/**
 * @param string $char1
 * @param string $char2
 * @return bool
 */
function isMatchingPair($char1, $char2)
{
    if ($char1 === ')' && $char2 === '(') {
        return true;
    }
    if ($char1 === '}' && $char2 === '{') {
        return true;
    }
    if ($char1 === ']' && $char2 === '[') {
        return true;
    }
    return false;
}

$inputString = '{ Swatantra (() {} ()) Kumar }';
isBalanced($inputString);
?>
0
Swatantra Kumar