Récursion de base, vérifier la parenthèse équilibrée

Question

J'ai écrit des logiciels dans le passé, qui utilise une pile pour vérifier l'équilibre des équations, mais maintenant, je me demande d'écrire un algorithme similaire de manière récursive pour vérifier correctement imbriquées les crochets et les parenthèses.

De bons exemples: () [] () ([]()[])

Mauvais exemples: ( (] ([)]

Supposons que ma fonction est appelée: isBalanced.

Chacun doit-il passer d'évaluer un plus petit sous-chaîne (jusqu'à arriver à un cas de base de 2 à gauche)? Ou, devrais-je toujours évaluer la chaîne complète et déplacer les indices vers l'intérieur?

Answer 1

Tout d'abord, à votre question de départ, juste être conscient que si vous travaillez avec de très longues chaînes, vous ne voulez pas de faire des copies exactes, déduction faite d'une seule lettre à chaque fois que vous effectuez un appel de fonction. Vous devez donc vous en faveur de l'utilisation d'index ou de vérifier que la langue de votre choix n'est pas de faire des copies de derrière les coulisses.

Deuxièmement, j'ai un problème avec ici toutes les réponses qui sont à l'aide d'une pile de structure de données. Je pense que le point de votre mission est de vous faire comprendre qu'avec la récursivité vos appels de fonction créer une pile. Vous n'avez pas besoin d'utiliser une pile de structure de données pour tenir votre parenthèses parce que chaque appel récursif est une nouvelle entrée sur un implicite de la pile.

Je vais le démontrer avec un programme C qui correspond ( et ). Ajouter les autres types, comme [ et ] est un exercice pour le lecteur. Tout ce que je maintenir dans la fonction est de ma position dans la chaîne (passé en un pointeur) parce que la récursivité est mon stack.

/* 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);
}

Testé avec ce 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);
    }

Sortie:

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

Answer 2

Il y a beaucoup de façons de le faire, mais la plus simple de l'algorithme est de simplement avancer de gauche à droite, en passant de la pile en tant que paramètre

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"

---

Ici, il est mis en œuvre en Java. Notez que j'ai mis maintenant de sorte que la pile pousse en avant au lieu de à l' arrière de la chaîne, pour des raisons de commodité. J'ai aussi modifié pour qu'il n'ignore non parenthèse symboles plutôt que comme une erreur.

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);
}

Harnais de Test:

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

Sortie:

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

Answer 3

L'idée est de garder une liste de l'ouverture des crochets, et si vous trouvez un de clôture brackt, vérifier si elle ferme le dernier ouvert:

• Si ces crochets de match, puis de supprimer le dernier ouvert à partir de la liste des openedBrackets et continuer à vérifier de manière récursive sur le reste de la chaîne
• Sinon vous avez trouvé un des supports à proximité une je n'ai jamais ouvert une seule fois, donc il n'est pas équilibrée.

Lorsque la chaîne est enfin vide, si la liste des brackes est vide aussi (donc tous les brackes a été fermé) rendement true, le reste false

ALGORITHME (en 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);
    }
}

TEST:

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));
    }
}

SORTIE:

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

Notez que j'ai importé les classes suivantes:

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

Answer 4

Il n'a pas vraiment d'importance d'un point de vue logique, si vous gardez une pile de tous actuellement déséquilibré parens que vous passez à chaque étape de la récursion, vous n'aurez jamais besoin de regarder en arrière, de sorte qu'il n'a pas d'importance si vous coupez la ficelle à chaque appel récursif, ou tout simplement incrémenter un index et seulement regarder l'actuel premier caractère.

Dans la plupart des langages de programmation, qui ont non-mutable chaînes, il est probablement plus coûteux (en terme de performance) pour raccourcir la chaîne que c'est de passer un peu plus de chaîne sur la pile. D'autre part, dans un langage comme C, vous pouvez simplement incrémenter un pointeur dans le tableau de char. Je suppose que c'est assez dépendant de la langue, laquelle de ces deux approches est la plus "efficace". Ils sont à la fois l'équivalent d'un point de vue conceptuel.

Answer 5

Je dirais que cela dépend de votre conception. Vous pouvez soit utiliser deux compteurs ou empiler avec deux symboles différents ou vous pouvez le manipuler en utilisant la récursion, la différence est dans l'approche de conception.