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

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

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

  1. let firstBracketOpening = "("
  2. let firstBracketClosing = ")"
  3. let secondBracketOpening = "{"
  4. let secondBracketClosing = "}"
  5. let thirdBracketOpening = "["
  6. let thirdBracketClosing = "]"
  7. func check(for braces: String) -> Bool {
  8. var isMissing = false
  9. for char in brace {
  10. isMissing = contains(char: char, in: brace)
  11. if isMissing {
  12. break
  13. }
  14. }
  15. return isMissing ? false : true
  16. }
  17. func contains(char: Character, in string: String) -> Bool {
  18. var isMissing = false
  19. if firstBracketOpening.contains(char) {
  20. isMissing = string.contains(firstBracketClosing) ? false : true
  21. }
  22. if secondBracketOpening.contains(char) {
  23. isMissing = string.contains(secondBracketClosing) ? false : true
  24. }
  25. if thirdBracketOpening.contains(char) {
  26. isMissing = string.contains(thirdBracketClosing) ? false : true
  27. }
  28. return isMissing
  29. }

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

kq4fsx7k

kq4fsx7k1#

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

  1. func checkParentheses(s: String) -> Bool {
  2. let pairs: [Character: Character] = ["(": ")", "[": "]", "{": "}"]
  3. var stack: [Character] = []
  4. for char in s {
  5. if let match = pairs[char] {
  6. stack.append(match)
  7. } else if stack.last == char {
  8. stack.popLast()
  9. } else {
  10. return false
  11. }
  12. }
  13. return stack.isEmpty
  14. }

测试用例:

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

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

展开查看全部
gr8qqesn

gr8qqesn2#

  1. import Foundation
  2. extension String {
  3. func isBalanced() -> Bool {
  4. switch self.filter("()[]{}".contains)
  5. .replacingOccurrences(of: "()", with: "")
  6. .replacingOccurrences(of: "[]", with: "")
  7. .replacingOccurrences(of: "{}", with: "") {
  8. case "": return true
  9. case self: return false
  10. case let next: return next.isBalanced()
  11. }
  12. }
  13. }

解释:

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

lnxxn5zx3#

要正确执行此操作,需要stack来维护左大括号。当你得到一个左大括号时,把它推到堆栈上。当你得到一个右花括号时,从堆栈中弹出顶部的左花括号,并检查它们是否匹配。当你解析完字符串后,stack应该是空的。

  1. enum Balance {
  2. case balanced
  3. case unbalanced(String)
  4. }
  5. func checkBalance(_ str: String) -> Balance {
  6. var stack = [Character]()
  7. for char in str {
  8. if ["{", "(", "["].contains(char) {
  9. stack.append(char)
  10. } else if ["}", ")", "]"].contains(char) {
  11. if let top = stack.popLast() {
  12. switch (top, char) {
  13. case ("{", "}"), ("(", ")"), ("[", "]"):
  14. break
  15. default:
  16. return .unbalanced("mismatched braces: \(top), \(char)")
  17. }
  18. } else {
  19. return .unbalanced("unexpected close brace: \(char)")
  20. }
  21. }
  22. }
  23. if !stack.isEmpty {
  24. return .unbalanced("missing \(stack.count) closing braces")
  25. }
  26. return .balanced
  27. }

测试:

  1. checkBalance("{ [ ( ) ] }")
  1. .balanced
  1. checkBalance("{ [ ] { } }")
  1. .balanced
  1. checkBalance("[(")
  1. .unbalanced("missing 2 closing braces")
  1. checkBalance("{ [ ( ) }")
  1. .unbalanced("mismatched braces: [, }")
  1. checkBalance("}")
  1. .unbalanced("unexpected close brace: }")

注:

checkBalance返回Balance类型的枚举。要检查结果是否为.balanced,可以这样做:

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

也可以使用switch

  1. switch checkBalance("() { [ ] }") {
  2. case .balanced:
  3. // do something if balanced
  4. case .unbalanced(let reason):
  5. print("Not balanced: \(reason)")
  6. }
展开查看全部
fkaflof6

fkaflof64#

Aand,一个完全FP的解决方案,使用堆栈来跟踪不平衡的括号:

  1. extension StringProtocol {
  2. func correctlyClosedParentheses() -> Bool {
  3. return reduce([Character]()) { stack, char in
  4. switch (char, stack.last) {
  5. // opening parentheses, we don't care about the top of the stack
  6. case ("(", _), ("[", _), ("{", _): return stack + [char]
  7. // closing parentheses, we do care about the top of the stack
  8. case (")", "("), ("]", "["), ("}", "{"): return stack.dropLast()
  9. // closing parentheses that failed the top of the stack check
  10. // we just accumulate them to make sure the stack is invalid
  11. case (")", _), ("]", _), ("}", _): return stack + [char]
  12. // other characters, we don't care about them
  13. default: return stack
  14. }
  15. }.isEmpty
  16. }
  17. }
展开查看全部
piok6c0g

piok6c0g5#

只是为了好玩。可能不包含长字符串(约60级左字符,但理想情况下适用于大多数编辑情况)。
这和堆栈的方式是一样的。2个整数构成一个堆栈。00为空,11、01、10个最右边的数字分别代表“(”、“[”和“{”。如果有错误请告诉我。希望它比概念堆栈运行得更快。
例如,“(({}[]))”最初,它是0 0作为两个堆栈整数。

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

很平衡。

  1. func test(_ s: String) -> Bool{
  2. var os1 : Int = 0; var os2 : Int = 0
  3. for c in s{
  4. switch (c, os1 & 0x1, os2 & 0x1) {
  5. case ("(",_,_): os1 <<= 0x1 ; os1 |= 0x1 ; os2 <<= 0x1 ; os2 |= 0x1
  6. case ("[",_,_): os1 <<= 0x1 ; os1 |= 0x0 ; os2 <<= 0x1 ; os2 |= 0x1
  7. case ("{", _,_): os1 <<= 0x1 ; os1 |= 0x1 ; os2 <<= 0x1 ; os2 |= 0x0
  8. case (")",0x1, 0x1), ("]",0x0, 0x1),("}",0x1, 0x0): os1 >>= 0x1 ; os2 >>= 0x1
  9. case (")",_ ,_),("]", _, _), ("}", _, _): return false
  10. default: break
  11. }
  12. }
  13. return os1 == 0 && os2 == 0
  14. }
  15. print (test("[((([])))]"))
  16. print (test("[[[[]]]][[[[]]]]"))

其他字符将被传递,所以这可以在开发环境中使用。

  1. print (test("[((hello([]))my)]"))
展开查看全部
fwzugrvs

fwzugrvs6#

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

  1. import Foundation
  2. func validBraces(_ string:String) -> Bool {
  3. var checkString = string
  4. for _ in 0..<Int(checkString.count / 2) {
  5. checkString = checkString.replacingOccurrences(of: "()", with: "")
  6. .replacingOccurrences(of: "[]", with: "")
  7. .replacingOccurrences(of: "{}", with: "")
  8. }
  9. return checkString.isEmpty
  10. }
xqkwcwgp

xqkwcwgp7#

  1. extension String{
  2. func randomAccessCharacterArray() -> Array<Character> {
  3. return Array(self)
  4. }
  5. }
  6. func isContain(_ s : String) -> Bool{
  7. let charArr = s.randomAccessCharacterArray()
  8. let dict: Dictionary<Character, Character> = [
  9. "}":"{",
  10. "]":"[",
  11. ")":"("
  12. ]
  13. var stack: Array<Character> = []
  14. for char in charArr {
  15. if char == "}" || char == ")" || char == "]" {
  16. if stack.isEmpty || stack.last != dict[char] {
  17. return false
  18. } else {
  19. stack.removeLast()
  20. }
  21. } else {
  22. stack.append(char)
  23. }
  24. }
  25. return stack.isEmpty
  26. }
展开查看全部

相关问题