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

ssgvzors  于 2023-06-21  发布在  Swift
关注(0)|答案(7)|浏览(121)

如果字符串中的大括号满足以下条件,则认为它们是平衡的,
1.所有大括号必须闭合。大括号以一对(), {}, []的形式出现。左括号打开该对,右括号关闭该对。
1.在任何一组嵌套大括号中,任何对之间的大括号都必须闭合。
例如,[{}]是有效的大括号分组,但[}]{}不是。
我尝试了下面的代码片段,但没有得到预期的结果,

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
}

任何解决方案的线索都将受到赞赏。先谢谢你了。

kq4fsx7k

kq4fsx7k1#

以下是我提出的解决方案:

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。如果我们找到一个起始括号。“(“,然后我们将结束括号推到堆栈ie。“)"。只要当前字符是起始括号,我们就这样做。
一旦我们找到一个结束括号,它必须是堆栈中的最后一个字符,这取决于我们如何添加它们。如果这是真的,那么括号是有效的,我们可以继续。
如果以上都不正确,我们要么有一个无效的字符(不是括号),要么有一个括号不平衡的情况。因此,我们可以在这里使用return false
在遍历String中的每个字符后,如果括号是平衡的,那么堆栈将为空。如果堆栈不是空的,这意味着括号没有平衡。

gr8qqesn

gr8qqesn2#

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

}

解释:

  1. filter("()[]{}".contains)删除除分隔符以外的所有字符。它的意思与filter({ c in "()[]{}".contains(c) })相同。
    1.任何有限长度的非空平衡字符串必须包含一个或多个空分隔符对(()[]{})。删除所有空对不会改变字符串的平衡性。因此,使用replacingOccurrences(of:with:)删除任何这样的空对。
    1.如果在删除所有空对之后,你有一个空字符串,那么你从一个平衡字符串开始,所以返回true。
    1.如果在删除所有空对之后,您实际上没有删除任何空对(并且您没有空字符串),那么您必须有一个不平衡的分隔符,因此返回false。
    1.如果在删除所有空对之后,您至少删除了一个对,那么现在可能会有新的空对。例如,删除[({})][({})]的空对会得到[()][()],它有新的空对。因此,尝试通过递归调用isBalanced tail-recursively来执行更多的删除操作。
lnxxn5zx

lnxxn5zx3#

要正确执行此操作,需要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返回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)")
}
fkaflof6

fkaflof64#

Aand,一个完全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
    }
}
piok6c0g

piok6c0g5#

只是为了好玩。可能不包含长字符串(约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)]"))
fwzugrvs

fwzugrvs6#

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

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

xqkwcwgp7#

extension String{
    func randomAccessCharacterArray() -> Array<Character> {
        return Array(self)
    }
}
func isContain(_ s : String) -> Bool{
    let charArr = s.randomAccessCharacterArray()
    let dict: Dictionary<Character, Character> = [
        "}":"{",
        "]":"[",
        ")":"("
    ]
    var stack: Array<Character> = []
    for char in charArr {
        if char == "}" || char == ")" || char == "]" {
            if stack.isEmpty || stack.last != dict[char] {
                return false
            } else {
                stack.removeLast()
            }
        } else {
            stack.append(char)
        }
    }
    return stack.isEmpty
    
}

相关问题