Recursion De Base, Vérifier Les Parenthèses Équilibrées

tout d'abord, à votre question originale, soyez juste conscient que si vous travaillez avec des chaînes très longues, vous ne voulez pas faire des copies exactes moins une lettre chaque fois que vous faites un appel de fonction. Ainsi, vous devriez favoriser l'utilisation d'index ou vérifier que votre langue de choix ne fait pas des copies dans les coulisses.

Deuxièmement, j'ai un problème avec toutes les réponses ici qui utilisent une structure de données de pile. Je pense que le but de votre mission est de comprenez qu'avec la récursion votre fonction appelle créer une pile . Vous n'avez pas besoin d'utiliser une structure de données de pile pour maintenir vos parenthèses parce que chaque appel récursif est une nouvelle entrée sur une pile implicite.

je vais 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 maintiens dans la fonction est ma position dans la chaîne (passé comme un pointeur) parce que la récursion est ma pile.

/* 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 == '"151900920"' || *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 == '"151910920"' ? 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!

l'idée est de garder une liste des crochets ouverts, et si vous trouvez un brackt de fermeture, Vérifiez s'il ferme le dernier ouvert:

• si ces crochets correspondent, alors supprimer le dernier ouvert de la liste des paquets ouverts et continuer à vérifier récursivement sur le reste de la chaîne
• sinon vous avez trouvé un support qui ferme un nerver ouvert une fois, il n'est pas équilibré.

lorsque la chaîne est enfin vide, si la liste des brackes est vide (donc tous les brackes a été fermée) de retour true , d'autre 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;

cela n'a pas vraiment d'importance d'un point de vue logique -- si vous gardez une pile de tous les paris actuellement non équilibrés que vous passez à chaque étape de la récursion, vous n'aurez jamais besoin de regarder en arrière, donc cela n'a pas d'importance si vous coupez la chaîne sur chaque appel récursif, ou tout simplement incrémenter un index et ne regarder que le premier caractère actuel.

dans la plupart des langages de programmation, qui ont des chaînes Non-mutables, il est probablement plus coûteux (en termes de performances) de raccourcissez la chaîne de caractères pour passer une chaîne légèrement plus grande 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 tous les deux équivalents d'un point de vue conceptuel.

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

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 gérer en utilisant la récursion, la différence est dans l'approche de conception.

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
}

solution PHP pour vérifier les parenthèses équilibrées

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

dans le langage de programmation Scala, je le ferais comme ceci:

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

s'il vous plaît éditez pour le rendre parfait.

Je suggérais seulement une conversion à Scala.

il devrait être une utilisation simple de la pile ..

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;       

    }

@indiv réponse est agréable et suffisant pour résoudre les parenthèses de la grammaire des problèmes. Si vous voulez utiliser stack ou si vous ne voulez pas utiliser la méthode recursive, vous pouvez regarder le "script" 151930920 de python sur github. Il est simple et rapide.

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