40 votos

Básicos De La Recursividad, Verificación Equilibrada Entre Paréntesis

He de software escrito en el pasado, que utiliza una pila para comprobar para equilibrar ecuaciones, pero ahora me piden que escriba un algoritmo similar de forma recursiva para comprobar correctamente anidados entre corchetes y paréntesis.

Buenos ejemplos: () [] () ([]()[])

Malos ejemplos: ( (] ([)]

Supongamos que mi función es llamada: isBalanced.

Debe evaluar cada paso un pequeño substring (hasta llegar a una base de caso de la 2 a la izquierda)? O, debería evaluar siempre la cadena completa y mover los índices hacia adentro?

54voto

indiv Puntos 7403

En primer lugar, a tu pregunta original, acaba de ser conscientes de que si usted está trabajando con muy largas cadenas, usted no quiere hacer copias exactas menos una sola letra cada vez que usted haga una llamada a una función. Así que usted debe favorecer el uso de índices o asegúrese de que el idioma de su elección no es la realización de copias de detrás de las escenas.

Segundo, tengo un problema con todas las respuestas aquí que utiliza una pila de estructura de datos. Creo que el punto de su asignación es para que entiendan que con recursividad su función de llamadas de crear una pila. Usted no necesita el uso de una pila de estructura de datos para mantener su paréntesis porque cada llamada recursiva es una nueva entrada, en una implícita de la pila.

Voy a demostrar con un programa en C que coincide con ( y ). La adición de los otros tipos, como [ y ] es un ejercicio para el lector. Todos los que me mantienen en la función está mi posición en la cadena (se pasa como un puntero), ya que la recursividad es mi pila.

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

Prueba con este código:

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

Salida:

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

47voto

polygenelubricants Puntos 136838

Hay muchas maneras de hacer esto, pero la más simple algoritmo es simplemente el proceso de la izquierda a la derecha, pasando la pila como un parámetro

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"

Aquí está implementado en Java. Tenga en cuenta que me ha cambiado ahora para que la pila empuja en la parte delantera en lugar de en la parte posterior de la cadena, para una mayor comodidad. También he modificado para que sólo salta no paréntesis de símbolos en lugar de la presentación de informes como un error.

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

Instrumento de prueba:

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

Salida:

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

3voto

La idea es mantener una lista de los corchetes, y en caso de encontrar un cierre brackt, comprobar si se cierra la abrió por última vez:

  • Si los soportes del partido, luego de quitar el último abierto de la lista de openedBrackets y verificar de forma recursiva en el resto de la cadena
  • Otra cosa que usted ha encontrado un paréntesis que cierra un nerver abierto de una vez, por lo que no es equilibrada.

Cuando la cadena es finalmente vacía, si la lista de brackes es vacía (para todos los brackes ha sido cerrado) regresar true, de otra false

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

PRUEBA:

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

SALIDA:

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

Tenga en cuenta que me han importado las siguientes clases:

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

1voto

Adrian Petrescu Puntos 4618

Realmente no importa desde un punto de vista lógico -- si usted mantiene una pila de toda la actualidad de la onu-equilibrado paréntesis que le de paso a cada paso de la recursividad, usted nunca tendrá que volver a mirar hacia atrás, de manera que no importa si se corta la cadena en cada llamada recursiva, o simplemente incremento de un índice y que sólo mire el actual primer carácter.

En la mayoría de los lenguajes de programación, que no mutables cadenas, es probable que sea más caro (en cuanto al rendimiento) para acortar la cadena que es para pasar un poco más grande de la cadena en la pila. Por otro lado, en un lenguaje como C, se podría incrementar un puntero dentro de la matriz de char. Supongo que es bastante dependiente del lenguaje que de estos dos enfoques es más 'eficiente'. Ambos son equivalentes desde un punto de vista conceptual.

0voto

Gabriel Ščerbák Puntos 7982

Yo diría que esto depende de su diseño. Usted podría utilizar dos contadores o pila con dos símbolos diferentes o usted puede manejar el uso de la recursividad, la diferencia está en el enfoque de diseño.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X