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

Question

Braces in a string are considered to be balanced if they met the following conditions,

1. All braces must be closed. braces come in a pair of the form of (), {}, []. The left brace opens the pair and the right one closes it.
2. In any set of nested braces, the braces between any pair must be closed.

For example, [{}] is a valid grouping of braces but [}]{} is not.

I tried with the below code snippet but not getting the expected result,

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
}

Any lead to the solution will be appreciated. Thanks in advance.

Coccidioidomycosis

@Vadian Actually actually ? false: true = !isMissing, therefore it is redundant :P. Also @Bappaditya, what is "item" in check(:String)? – Resee

I updated the code it should be brace – Coccidioidomycosis

Is the string you want to check only allowed to contain one of the 6 brace characters? What about a string like {[}]? – Leucas

Answer 1

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

}

To explain:

1. filter("()[]{}".contains) removes any characters except the delimiters. It means the same as filter({ c in "()[]{}".contains(c) }).

2. Any finite-length, non-empty balanced string must contain one or more empty delimiter pairs ((), [], or {}). Deleting all empty pairs doesn't change the balanced-ness of the string. So delete any such empty pairs using replacingOccurrences(of:with:).

3. If, after deleting all empty pairs, you have an empty string, then you started with a balanced string, so return true.

4. If, after deleting all empty pairs, you didn't actually remove any empty pairs (and you don't have an empty string), then you must have an unbalanced delimiter, so return false.

5. If, after deleting all empty pairs, you removed at least one pair, then you might now have new empty pairs. For example, deleting the empty pairs of [({})][({})] gives [()][()], which has new empty pairs. So try to do more deleting by calling isBalanced tail-recursively.

Woosley

Wow, how simple! ;) But, efficiency isn't as good as with Swift Geek's solution, right? (I'm just curious) – Parada

This may be slick and all but this could definitely use some explanation. – Leucas

@RobertDresler Yes, it's O(N²) instead of O(N). I just wanted to see how small I could make it. – Woosley

@Leucas Okay, I've explained it some. – Woosley

Answer 2

Here is the solution I came up with:

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
}

Test Cases:

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

All we are doing here is iterating over each Character in the String. If we find a starting parenthesis ie. "(", then we push the ending parenthesis to the stack ie. ")". We do this as long as the current character is a starting parenthesis.

Once we find an ending parenthesis, it must be the last character in the stack based on how we were adding them. If this is true, then the parentheses were valid and we may proceed.

If none of the above are true, we either have an invalid character (not a parentheses) or a case where the parenthesis aren't balanced. With that being said, we can return false here.

After iterating over every character in the String our stack will be empty if the parentheses were balanced. If the stack isn't empty this means the parentheses weren't balanced.

Diathesis

Better: if let match = pairs[char] { stack.append(match) } else ... – Woosley

@martin I will make the change now, thank you for the feedback and good idea :) – Diathesis

Also better: else if stack.last == char { stack.popLast() } else ... stack.last returns nil if the stack is empty, so you don't have to check stack.count. – Woosley

@robmayoff Appreciate the feedback -- I made the changes :) – Diathesis

Nice simple solution. (Voted) – Millimeter

In this case return stack.isEmpty would make better sanse maybe – Parada

I used this to make my own algorithim because my case was different. I dont want to add the closing bracket, because I already have the closing bracket in the last. I want to put some string before the last closing bracket. and it helped me out to make my own algo, thanks @Diathesis – Mistaken

Answer 3

To do this right, you need a stack to maintain the opening braces. When you get an opening brace, push it onto the stack. When you get a closing brace, pop off the top opening brace from the stack and check that they match. When you are done parsing the string, the stack should be empty.

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
}

Tests:

checkBalance("{ [ ( ) ] }")

.balanced

checkBalance("{ [ ] { } }")

.balanced

checkBalance("[(")

.unbalanced("missing 2 closing braces")

checkBalance("{ [ ( ) }")

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

checkBalance("}")

.unbalanced("unexpected close brace: }")

---

Note:

checkBalance returns an enum of type Balance. To check if the result is .balanced, you'd do that like this:

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

or you can use a switch:

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

Artair

Answer 4

Aand, a fully FP solution, using a stack to keep track of the unbalanced parentheses:

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

Filomenafiloplume

Answer 5

Just for fun. May not hold long strings(~ 60 levels of left characters, but great for most editing cases ideally).

It’s same as the stack way. 2 integers constructs a stack. 00 is empty, 11, 01, 10 of each rightest digits representing “(“ “[“ and “{”. Tell me if there’s error. Hopefully it runs faster than a conceptual stack.

For example , "(({}[]))" Initially, it's 0 0 as both stack integers.

        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

It's balanced.

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

Other characters will be passed, so this can be used in developing situation.

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

Apish

Please provide an explanation of how this code works. – Leucas

Answer 6

My solution requires only string methods:

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
}

Reeding

Answer 7

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
    
}

Daryn

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Imprecate