Besoin de vérifier que les accolades dans un tableau donné sont équilibrées ou non

Pour ce faire correctement, vous avez besoin d'une stack pour maintenir les accolades ouvrantes. Lorsque vous obtenez une accolade ouvrante, poussez-la sur la pile. Lorsque vous obtenez une accolade de fermeture, sortez l'accolade d'ouverture supérieure de la pile et vérifiez qu'elles correspondent. Lorsque vous avez terminé l'analyse de la chaîne, la stack doit être vide.

switch checkBalance("() { [ ] }") {
case .balanced:
    // do something if balanced
case .unbalanced(let reason):
    print("Not balanced: \(reason)")
}

Tests:

if case .balanced = checkBalance("() { [ ] }") {
    // handle balanced case
} 

.unbalanced("unexpected close brace: }")

checkBalance("}")

.unbalanced("mismatched braces: [, }")

checkBalance("{ [ ( ) }")

.unbalanced("missing 2 closing braces")

checkBalance("[(")

.balanced

checkBalance("{ [ ] { } }")

.balanced

Remarque:

checkBalance renvoie une énumération de type Balance . Pour vérifier si le résultat est .balanced , procédez comme .balanced :

checkBalance("{ [ ( ) ] }")

ou vous pouvez utiliser un switch :

enum Balance {
    case balanced
    case unbalanced(String)
}

func checkBalance(_ str: String) -> Balance {
    var stack = [Character]()

    for char in str {
        if ["{", "(", "["].contains(char) {
            stack.append(char)
        } else if ["}", ")", "]"].contains(char) {
            if let top = stack.popLast() {
                switch (top, char) {
                case ("{", "}"), ("(", ")"), ("[", "]"):
                    break
                default:
                    return .unbalanced("mismatched braces: \(top), \(char)")
                }
            } else {
                return .unbalanced("unexpected close brace: \(char)")
            }
        }
    }
    if !stack.isEmpty {
        return .unbalanced("missing \(stack.count) closing braces")
    }
    return .balanced
}

Voici la solution que j'ai trouvée:

print(checkParentheses(s: "((({[]})))")) // True (Balanced)
print(checkParentheses(s: "((({[]}))")) // False (Not Balanced)
print(checkParentheses(s: "(]")) // False (Not Balanced)

Cas de test:

func checkParentheses(s: String) -> Bool {
    let pairs: [Character: Character] = ["(": ")", "[": "]", "{": "}"]
    var stack: [Character] = []
    for char in s {
        if let match = pairs[char] {
            stack.append(match)
        } else if stack.last == char {
            stack.popLast()
        } else {
            return false
        }
    }
    return stack.isEmpty
}

Tout ce que nous faisons ici, c'est itérer sur chaque Character de la String . Si nous trouvons une parenthèse de départ ie. "(", puis nous poussons la parenthèse de fin dans la pile, c'est-à-dire ")". Nous faisons cela tant que le caractère actuel est une parenthèse de départ.

Une fois que nous avons trouvé une parenthèse de fin, ce doit être le dernier caractère de la pile en fonction de la façon dont nous les avons ajoutés. Si cela est vrai, alors les parenthèses étaient valides et nous pouvons continuer.

Si rien de ce qui précède n'est vrai, nous avons soit un caractère invalide (pas de parenthèses), soit un cas où les parenthèses ne sont pas équilibrées. Cela étant dit, nous pouvons return false ici.

Après avoir parcouru chaque caractère de la chaîne, notre pile sera vide si les parenthèses étaient équilibrées. Si la pile n'est pas vide, cela signifie que les parenthèses n'étaient pas équilibrées.

import Foundation

extension String {

    func isBalanced() -> Bool {
        switch self.filter("()[]{}".contains)
            .replacingOccurrences(of: "()", with: "")
            .replacingOccurrences(of: "[]", with: "")
            .replacingOccurrences(of: "{}", with: "") {
        case "": return true
        case self: return false
        case let next: return next.isBalanced()
        }
    }

}
To explain:
filter("()[]{}".contains) removes any characters except the delimiters. It means the same as filter({ c in "()[]{}".contains(c) }).
Any finite-length, non-empty balanced string must contain one or more empty delimiter pairs ((), [], or {}). Deleting all empty pairs doesn't change the balanced-ness of the string. So delete any such empty pairs using replacingOccurrences(of:with:).
If, after deleting all empty pairs, you have an empty string, then you started with a balanced string, so return true.
If, after deleting all empty pairs, you didn't actually remove any empty pairs (and you don't have an empty string), then you must have an unbalanced delimiter, so return false.
If, after deleting all empty pairs, you removed at least one pair, then you might now have new empty pairs. For example, deleting the empty pairs of [({})][({})] gives [()][()], which has new empty pairs. So try to do more deleting by calling isBalanced tail-recursively.

Juste pour le fun. Peut ne pas contenir de longues chaînes (~ 60 niveaux de caractères de gauche, mais idéal pour la plupart des cas d'édition).

C'est la même chose que la méthode de la pile. 2 entiers construisent une pile. 00 est vide, 11, 01, 10 de chaque chiffre le plus à droite représentant "(" "[" et "{". Dites-moi s'il y a une erreur. J'espère qu'il s'exécute plus vite que une pile conceptuelle.

Par exemple, "(({} []))" Au départ, c'est 0 0 comme les deux entiers de la pile.

    print (test("[((hello([]))my)]")) 

C'est équilibré.

    func test(_ s: String) -> Bool{
        var os1 : Int = 0;   var os2 : Int = 0
        for c in s{
            switch (c, os1 & 0x1, os2 & 0x1) {
            case ("(",_,_):  os1 <<= 0x1 ;  os1 |= 0x1 ; os2 <<= 0x1 ; os2 |= 0x1
            case ("[",_,_):  os1 <<= 0x1 ;  os1 |= 0x0 ; os2 <<= 0x1 ; os2 |= 0x1
            case ("{", _,_): os1 <<= 0x1 ;  os1 |= 0x1 ; os2 <<= 0x1 ; os2 |= 0x0
            case (")",0x1, 0x1), ("]",0x0, 0x1),("}",0x1, 0x0):  os1 >>= 0x1 ;  os2 >>= 0x1
            case (")",_ ,_),("]", _, _), ("}", _, _):  return false
            default: break
            }
        }
        return os1 == 0 && os2 == 0
    }


    print (test("[((([])))]"))
    print (test("[[[[]]]][[[[]]]]")) 

D'autres caractères seront transmis, donc cela peut être utilisé dans une situation de développement.

        0 0
 "(" -> 1 1.  (  0<<1 + 1 , 0<<1 + 1 ) //push
 "(" -> 3 3   (  1<<1 + 1 , 1<<1 + 1 ) //push
 "{" -> 7 6.  (  3<<1 + 1,  3<<1 + 0 ) //push
 "}" -> 3 3.  (  7>>1 ,  6 >>1) //pop
 "[" -> 6 7.  (  3<<1 + 0, 3<<1 + 1) //push
 "]" -> 3 3.  (  6>>1 , 7>>1 ) //pop
 ")" -> 1 1.  (  3>>1 , 3>>1 ) //pop
 ")" -> 0 0.  (  1>>1 , 1>>1 ) //pop

Aand, une solution entièrement FP, utilisant une pile pour garder une trace des parenthèses déséquilibrées:

extension StringProtocol {
    func correctlyClosedParentheses() -> Bool {
        return reduce([Character]()) { stack, char in
            switch (char, stack.last) {
            // opening parentheses, we don't care about the top of the stack
            case ("(", _), ("[", _), ("{", _): return stack + [char]
                
            // closing parentheses, we do care about the top of the stack
            case (")", "("), ("]", "["), ("}", "{"): return stack.dropLast()
                
            // closing parentheses that failed the top of the stack check
            // we just accumulate them to make sure the stack is invalid
            case (")", _), ("]", _), ("}", _): return stack + [char]
                
            // other characters, we don't care about them
            default: return stack
            }
        }.isEmpty
    }
}