Необходимо проверить, что скобки в данном массиве сбалансированы или нет

Question

Скобки в строке считаются сбалансированными, если они удовлетворяют следующим условиям:

1. Все скобки должны быть закрыты.Брекеты поставляются в виде пары (), {}, [].Левая скобка открывает пару, а правая закрывает ее.
2. В любом наборе вложенных скобок скобки между любой парой должны быть закрыты.

Например, [{}]является допустимой группировкой фигурных скобок, но [}]{} - нет.

Я пробовал с приведенным ниже фрагментом кода, но не получил ожидаемого результата,

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

Просто для удовольствия. Может не содержать длинные строки (~ 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 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)

Все, что мы здесь делаем, это итерация по каждому Character в String. Если мы найдем начальную скобку т.е. "(", тогда мы помещаем завершающую скобку в стек, т.е.. ")". Мы делаем это до тех пор, пока текущий символ является начальной скобкой.

Как только мы найдем завершающие скобки, это должен быть последний символ в стеке в зависимости от того, как мы их добавляли. Если это так, то скобки были действительны, и мы можем продолжить.

Если ничего из вышеперечисленного не соответствует действительности, у нас либо есть недопустимый символ (не скобки), либо случай, когда скобки не сбалансированы. С учетом сказанного мы можем 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()
        }
    }

}

Объяснить:

1. filter("()[]{}".contains) удаляет все символы, кроме разделителей. То же самое, что и filter({ c in "()[]{}".contains(c) }).

2. Любая непустая сбалансированная строка конечной длины должна содержать одну или несколько пустых пар разделителей ((), [] или {}). Удаление всех пустых пар не меняет сбалансированность строки. Поэтому удалите все такие пустые пары, используя replacingOccurrences(of:with:).

3. Если после удаления всех пустых пар у вас есть пустая строка, значит, вы начали со сбалансированной строки, поэтому верните true.

4. Если после удаления всех пустых пар вы фактически не удалили пустых пар (и у вас нет пустой строки), то у вас должен быть несбалансированный разделитель, поэтому верните false.

5. Если после удаления всех пустых пар вы удалили хотя бы одну пару, у вас могут появиться новые пустые пары. Например, удаление пустых пар [({})][({})] дает [()][()], в котором есть новые пустые пары. Поэтому попробуйте удалить больше, вызвав isBalanced tail-recursively.

Answer 4

Чтобы сделать это правильно, вам нужно 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)")
}