Las llaves en una cuerda se consideran equilibradas si cumplen las siguientes condiciones,
(), {}, [] . La llave izquierda abre el par y la derecha lo cierra. Por ejemplo, [{}] es una agrupación válida de llaves pero [}]{} no lo es.
Probé con el siguiente fragmento de código pero no obtuve el resultado esperado,
let firstBracketOpening = "(" let firstBracketClosing = ")" let secondBracketOpening = "{" let secondBracketClosing = "}" let thirdBracketOpening = "[" let thirdBracketClosing = "]" func check(for braces: String) -> Bool { var isMissing = false for char in brace { isMissing = contains(char: char, in: brace) if isMissing { break } } return isMissing ? false : true } func contains(char: Character, in string: String) -> Bool { var isMissing = false if firstBracketOpening.contains(char) { isMissing = string.contains(firstBracketClosing) ? false : true } if secondBracketOpening.contains(char) { isMissing = string.contains(secondBracketClosing) ? false : true } if thirdBracketOpening.contains(char) { isMissing = string.contains(thirdBracketClosing) ? false : true } return isMissing }Cualquier pista a la solución será apreciada. Gracias por adelantado.
Aquí está la solución que se me ocurrió:
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 }Casos de prueba:
print(checkParentheses(s: "((({[]})))")) // True (Balanced) print(checkParentheses(s: "((({[]}))")) // False (Not Balanced) print(checkParentheses(s: "(]")) // False (Not Balanced) Todo lo que estamos haciendo aquí es iterar sobre cada Character en la String . Si encontramos un paréntesis inicial, es decir. "(", luego empujamos el paréntesis final a la pila, es decir, ")". Hacemos esto siempre que el carácter actual sea un paréntesis inicial.
Una vez que encontramos un paréntesis final, debe ser el último carácter de la pila en función de cómo los agregamos. Si esto es cierto, entonces los paréntesis eran válidos y podemos proceder.
Si nada de lo anterior es cierto, tenemos un carácter no válido (no un paréntesis) o un caso en el que los paréntesis no están equilibrados. Dicho esto, podemos return false aquí.
Después de iterar sobre cada carácter en la Cadena, nuestra pila estará vacía si los paréntesis estaban balanceados. Si la pila no está vacía, significa que los paréntesis no estaban equilibrados.
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() } } }Para explicar:
filter("()[]{}".contains) elimina cualquier carácter excepto los delimitadores. Significa lo mismo que filter({ c in "()[]{}".contains(c) }) .
Cualquier cadena balanceada no vacía de longitud finita debe contener uno o más pares de delimitadores vacíos ( () , [] o {} ). Eliminar todos los pares vacíos no cambia el equilibrio de la cadena. Así que elimine cualquiera de esos pares vacíos usando replacingOccurrences(of:with:) .
Si, después de eliminar todos los pares vacíos, tiene una cadena vacía, entonces comenzó con una cadena balanceada, así que devuelva verdadero.
Si, después de eliminar todos los pares vacíos, en realidad no eliminó ningún par vacío (y no tiene una cadena vacía), entonces debe tener un delimitador desequilibrado, así que devuelva falso.
Si, después de eliminar todos los pares vacíos, eliminó al menos un par, es posible que ahora tenga nuevos pares vacíos. Por ejemplo, eliminar los pares vacíos de [({})][({})] da [()][()] , que tiene nuevos pares vacíos. Así que intente eliminar más llamando a isBalanced tail-recursivamente.
Para hacer esto bien, necesita una stack para mantener las llaves de apertura. Cuando obtenga una abrazadera de apertura, empújela hacia la pila. Cuando obtenga una llave de cierre, saque la llave de apertura superior de la pila y verifique que coincidan. Cuando haya terminado de analizar la cadena, la stack debe estar vacía.
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 }Pruebas:
checkBalance("{ [ ( ) ] }").balanced
checkBalance("{ [ ] { } }").balanced
checkBalance("[(").unbalanced("missing 2 closing braces")
checkBalance("{ [ ( ) }").unbalanced("mismatched braces: [, }")
checkBalance("}").unbalanced("unexpected close brace: }")
Nota:
checkBalance devuelve una enumeración de tipo Balance . Para verificar si el resultado es .balanced , lo haría así:
if case .balanced = checkBalance("() { [ ] }") { // handle balanced case } o puedes usar un switch :
switch checkBalance("() { [ ] }") { case .balanced: // do something if balanced case .unbalanced(let reason): print("Not balanced: \(reason)") }