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.

Answer 1

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.