Необходимо проверить, что скобки в данном массиве сбалансированы или нет
Брекеты в строке считаются сбалансированными, если они удовлетворяют следующим условиям:
- Все брекеты должны быть закрыты. брекеты бывают в виде пары
(), {}, [], Левая скобка открывает пару, а правая закрывает ее. - В любом наборе вложенных скобок скобки между любой парой должны быть закрыты.
Например, [{}] является допустимой группировкой скобок, но [}]{} не является.
Я попытался с приведенным ниже фрагментом кода, но не получил ожидаемый результат,
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
}
Любой вывод к решению будет оценен. Заранее спасибо.
7 ответов
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:),Если после удаления всех пустых пар у вас есть пустая строка, то вы начали со сбалансированной строки, поэтому верните true.
Если после удаления всех пустых пар вы фактически не удалили пустых пар (и у вас нет пустой строки), то у вас должен быть несбалансированный разделитель, поэтому верните false.
Если после удаления всех пустых пар вы удалили хотя бы одну пару, у вас могут появиться новые пустые пары. Например, удаление пустых пар
[({})][({})]дает[()][()], который имеет новые пустые пары. Так что попробуйте сделать больше удаления, позвонивisBalancedХвост-рекурсивно.
Вот решение, которое я придумал:
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 Вот.
После итерации каждого символа в строке наш стек будет пустым, если круглые скобки были сбалансированы. Если стек не пустой, это означает, что скобки не сбалансированы.
Чтобы сделать это правильно, вам нужен 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)")
}
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
}
}
Просто для удовольствия. Может не содержать длинные строки (~ 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)]"))
Мое решение требует только строковых методов:
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
}
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
}