algorithm - recursivo - sucesion recursiva en python

Recursión básica, verificar paréntesis equilibrado

Question

He escrito software en el pasado que usa una pila para verificar ecuaciones equilibradas, pero ahora me piden que escriba un algoritmo similar recursivamente para verificar paréntesis y paréntesis anidados correctamente.

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

Ejemplos malos: ((] ([)]

Supongamos que mi función se llama: isBalanced.

¿Debería cada pase evaluar una subcadena más pequeña (hasta llegar a un caso base de 2 izquierda)? O, ¿debería siempre evaluar la cadena completa y mover los índices hacia adentro?

Answer 1

Debería ser un uso simple de la pila ...

private string tokens = "{([<})]>";        
    Stack<char> stack = new Stack<char>();   

    public bool  IsExpressionVaild(string exp)
    {
        int mid = (tokens.Length / 2)  ;  

        for (int i = 0; i < exp.Length; i++)
        {
            int index = tokens.IndexOf(exp[i]);
            if (-1 == index) { continue; }

            if(index<mid ) stack .Push(exp[i]);
            else 
            {
                if (stack.Pop() != tokens[index - mid]) { return false; }       

            }          

        }
        return true;       

    }

Answer 2

En el lenguaje de programación de Scala, lo haría así:

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

Por favor edítalo para que sea perfecto.

Solo estaba sugiriendo una conversión en Scala.

Answer 3

En primer lugar, a su pregunta original, tenga en cuenta que si trabaja con cadenas muy largas, no desea hacer copias exactas menos una letra cada vez que realiza una llamada a función. Por lo tanto, debe favorecer el uso de índices o verificar que el idioma de su elección no esté haciendo copias entre bastidores.

En segundo lugar, tengo un problema con todas las respuestas aquí que usan una estructura de datos de pila. Creo que el objetivo de tu tarea es que comprendas que con la recursividad las llamadas a tus funciones crean una pila . No necesita usar una estructura de datos de pila para mantener sus paréntesis porque cada llamada recursiva es una entrada nueva en una pila implícita.

Lo demostraré con un programa C que coincida con ( y ) . Agregar los otros tipos como [ y ] es un ejercicio para el lector. Todo lo que mantengo en la función es mi posición en la cadena (pasada como un puntero) porque la recursión 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);
}

Probado 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!

Answer 4

En realidad, no importa desde un punto de vista lógico: si mantienes una pila de todos los parens no balanceados que pasas a cada paso de la recursión, nunca necesitarás mirar hacia atrás, por lo que no Importa si corta la cadena en cada llamada recursiva, o simplemente incrementa un índice y solo mira el primer carácter actual.

En la mayoría de los lenguajes de programación, que tienen cadenas no mutables, probablemente sea más caro (en cuanto al rendimiento) acortar la cadena que pasar una cadena ligeramente más grande en la pila. Por otro lado, en un lenguaje como C, puedes simplemente incrementar un puntero dentro de la matriz char. Creo que es bastante dependiente del lenguaje cuál de estos dos enfoques es más "eficiente". Ambos son equivalentes desde un punto de vista conceptual.

Answer 5

Hay muchas formas de hacerlo, pero el algoritmo más simple es simplemente procesar hacia adelante de izquierda a derecha, pasando la pila como 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 lo he cambiado ahora para que la pila empuje al frente en lugar de en la parte posterior de la cadena, para mayor comodidad. También lo he modificado para que salte símbolos sin paréntesis en lugar de informarlo 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);
}

Arnés 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

Answer 6

La idea es mantener una lista de los corchetes abiertos, y si encuentra un cierre de Brackt, verifique si cierra el último abierto:

• Si esos corchetes coinciden, elimine el último abierto de la lista de aperturas de Billetes y continúe comprobando recursivamente en el resto de la cadena
• De lo contrario, has encontrado unos corchetes que cierran un nerver abierto una vez, por lo que no está equilibrado.

Cuando la cadena está finalmente vacía, si la lista de llaves está vacía también (por lo que todos los bloqueos se han cerrado) devuelve true , de lo contrario es 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 he importado las siguientes clases:

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

Answer 7

La respuesta de @indiv es buena y suficiente para resolver los problemas de gramática entre paréntesis. Si desea utilizar la pila o no desea usar el método recursivo, puede ver la script de script python en github. Es simple y rápido.

BRACKET_ROUND_OPEN = ''(''
BRACKET_ROUND__CLOSE = '')''
BRACKET_CURLY_OPEN = ''{''
BRACKET_CURLY_CLOSE = ''}''
BRACKET_SQUARE_OPEN = ''[''
BRACKET_SQUARE_CLOSE = '']''

TUPLE_OPEN_CLOSE = [(BRACKET_ROUND_OPEN,BRACKET_ROUND__CLOSE),
                    (BRACKET_CURLY_OPEN,BRACKET_CURLY_CLOSE),
                    (BRACKET_SQUARE_OPEN,BRACKET_SQUARE_CLOSE)]
BRACKET_LIST = [BRACKET_ROUND_OPEN,BRACKET_ROUND__CLOSE,BRACKET_CURLY_OPEN,BRACKET_CURLY_CLOSE,BRACKET_SQUARE_OPEN,BRACKET_SQUARE_CLOSE]

def balanced_parentheses(expression):
    stack = list()
    left = expression[0]
    for exp in expression:
        if exp not in BRACKET_LIST:
            continue
        skip = False
        for bracket_couple in TUPLE_OPEN_CLOSE:
            if exp != bracket_couple[0] and exp != bracket_couple[1]:
                continue
            if left == bracket_couple[0] and exp == bracket_couple[1]:
                if len(stack) == 0:
                    return False
                stack.pop()
                skip = True
                left = ''''
                if len(stack) > 0:
                    left = stack[len(stack) - 1]
        if not skip:
            left = exp
            stack.append(exp)

    return len(stack) == 0
if __name__ == ''__main__'':
    print(balanced_parentheses(''(()())({})[]''))#True
    print(balanced_parentheses(''((balanced)(parentheses))({})[]''))#True
    print(balanced_parentheses(''(()())())''))#False

Answer 8

Solución PHP para verificar paréntesis equilibrados

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

Answer 9

Yo diría que esto depende de tu diseño. Puede usar dos contadores o apilar con dos símbolos diferentes o puede manejarlo usando la recursión, la diferencia está en el enfoque de diseño.

Answer 10

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

Answer 11

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
}