需要检查给定数组中的大括号是否平衡

Question

如果字符串中的大括号满足以下条件，则认为它们是平衡的，

所有大括号都必须闭合。大括号以 (), {}, [] 的形式出现。左大括号打开一对，右大括号关闭它。
在任何一组嵌套大括号中，任何一对之间的大括号都必须闭合。

例如，[{}] 是有效的大括号分组，但 [}]{} 不是。

我尝试了下面的代码片段，但没有得到预期的结果，

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
}

任何导致解决方案的线索都将不胜感激。提前致谢。

Answer 1

要做到这一点，您需要 stack 来维护左大括号。当你得到一个左括号时，将它推到堆栈上。当你得到一个右括号时，从堆栈中弹出顶部的左括号并检查它们是否匹配。完成字符串解析后，stack 应该为空。

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
}

测试：

checkBalance("{ [ ( ) ] }")

.balanced

checkBalance("{ [ ] { } }")

.balanced

checkBalance("[(")

.unbalanced("missing 2 closing braces")

checkBalance("{ [ ( ) }")

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

checkBalance("}")

.unbalanced("unexpected close brace: }")

注：

checkBalance returns Balance 类型的枚举。要检查结果是否为 .balanced，您可以这样做：

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

或者您可以使用 switch:

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

Answer 2

这是我想出的解决方案：

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
}

测试用例：

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

我们在这里所做的就是迭代 String 中的每个 Character。如果我们找到一个起始括号，即。 “(”，然后我们将结束括号压入堆栈，即。“)”。只要当前字符是起始括号，我们就会这样做。

一旦我们找到结束括号，根据我们添加它们的方式，它一定是堆栈中的最后一个字符。如果这是真的，那么括号是有效的，我们可以继续。

如果上述 none 为真，我们要么有无效字符（不是圆括号），要么圆括号不平衡。话虽如此，我们可以 return false 这里。

遍历字符串中的每个字符后，如果括号是平衡的，我们的堆栈将为空。如果堆栈不为空，则表示括号不平衡。

Answer 3

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

}

说明：

filter("()[]{}".contains) 删除分隔符以外的所有字符。意思和filter({ c in "()[]{}".contains(c) }).
任何有限长度的非空平衡字符串必须包含一对或多对空分隔符（()、[] 或 {}）。删除所有空对不会改变字符串的平衡性。因此，使用 replacingOccurrences(of:with:).
如果在删除所有空对后，你有一个空字符串，那么你从一个平衡的字符串开始，所以 return 正确。
如果在删除所有空对后，您实际上并没有删除任何空对（并且您没有空字符串），那么您一定有一个不平衡的定界符，所以 return假。
如果在删除所有空对之后，您至少删除了一对，那么您现在可能会有新的空对。例如，删除 [({})][({})] 的空对会得到 [()][()]，它有新的空对。因此，尝试通过尾递归调用 isBalanced 来执行更多删除操作。

Answer 4

纯属娱乐。可能无法容纳长字符串（~ 60 级左侧字符，但理想情况下适用于大多数编辑情况）。

同栈方式。 2个整数构成一个栈。 00 是空的，11、01、10 每个最右边的数字代表“(” “[” 和 “{”。如果有错误告诉我。希望它比概念堆栈运行得更快。

例如，“(({}[]))” 最初，它是 0 0 作为两个堆栈整数。

        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

这是平衡的。

    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("[[[[]]]][[[[]]]]"))

其他字符会被传递，所以这个可以在开发的情况下使用。

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

Answer 5

并且，完全 FP 解决方案，使用堆栈来跟踪不平衡的括号：

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

Answer 6

我的解决方案只需要字符串方法：

import Foundation

func validBraces(_ string:String) -> Bool {
    
    var checkString = string
    
        for _ in 0..<Int(checkString.count / 2) {
            checkString = checkString.replacingOccurrences(of: "()", with: "")
                .replacingOccurrences(of: "[]", with: "")
                .replacingOccurrences(of: "{}", with: "")
        }
    return checkString.isEmpty
}

需要检查给定数组中的大括号是否平衡

Need to check that braces in given array are balanced or not

string

braces

swift