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

  • A+
Category:Languages

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.

 


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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: