Stack Problem - Balancing of Symbols

Stack Problem - Balancing of Symbols

Problem:

Given an expression string exp , write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp.

Example:

Input: exp = “[()]{}{[()()]()}”
Output: Balanced

Input: exp = “[(])”
Output: Not Balanced

Algorithm:

• Create a stack.
• while ( end of input is not reached ) {
  • If the character read is not a symbol to be balanced, ignore it.
  • If the character is an opening delimiter like ( , {  or [ , PUSH it into the stack.
  • If it is a closing symbol like ) , } , ] , then if the stack is empty report an error, otherwise POP the stack.
  • If the symbol POP-ed is not the corresponding delimiter, report an error.
• At the end of the input, if the stack is not empty report an error.

Implementation :

func balancingOfSymbols(string:String)->Bool{
        guard string.count > 0 else { return false }
        let symbols:[Character:Character] = ["{":"}","[":"]","(":")",]
        var symbolStack:Stack<Character> = Stack()
        var isBalanced = true
        
        for char in string  {
            if symbols.keys.contains(char){
                symbolStack.push(char)
            }else if symbols.values.contains(char){
                if let poppedSymbol = symbolStack.pop(), symbols[poppedSymbol] == char{
                    continue
                }else{
                     isBalanced = false
                    break
                }
            }
        }
        isBalanced = isBalanced ? symbolStack.count == 0 : isBalanced
        return isBalanced
    }

Time Complexity: O(n)

In case if you are wondering, how to implement a STACK, Please click here.