Balanced Parentheses in Swift

Following task is given: Define that sequence of parenthesis is balanced (correct). For example,

• ((( ))) is balanced
• (( ))) is NOT balanced
• ) (( )) is NOT balanced
• (( )) () is balanced

Simple Case (One type of parenthesis)

Algorithm

1. For any open parenthesis found in string we will increment counter by 1
2. For any close parenthesis found in string we will decrease counter by 1
3. If after all the characters in the string are checked, the counter is equal to zero then it is balanced parentheses sequence.  

func isBalancedParenthesisV1(_ string: String) -> Bool {
    var balance = 0
    for ch in string {
        if ch == "(" {
            balance += 1
        } else if ch == ")" {
            balance -= 1
        }
    }
    let result = (balance == 0)
    return result
}

This algorithm will work for simple cases when close parenthesis appears after open.
For example, it will work correct for "((( )))".
But in case when close parenthesis appears before open this algorithm will be wrong and return true even if  parentheses are not balanced. So, for fixing this mistake we need to check that current balance is equal to zero before decrease operation (Zero balance means that next must be open parenthesis but not close. And if next parenthesis is close and current balance is equal to zero then we have NOT balanced parentheses).

Simple Case with Checking

In case of when next character is close parenthesis we need to check current balance and return false if balance is equal to zero.

func isBalancedParenthesisV2(_ string: String) -> Bool {
    var balance = 0
    for ch in string {
        if ch == "(" {
            balance += 1
        } else if ch == ")" {
            if (balance == 0) {
                return false
            } else {
                balance -= 1
            }
        }
    }
    let result = (balance == 0)
    return result
}

Case with Multiple Types of Parentheses (Using Stack)

But what if there are more then one type of parenthesis, for example, three: {}, [], ().
In this case we need more advanced algorithm for resolving this task, because simple counter cannot handle this. Here we can solve this using Stack Data Structure. Idea is following: add to stack every next OPEN parenthesis and get from stack when next parenthesis is CLOSE and compare that they are valid pair.

I already wrote about Stack Data Structure

• Generic in Swift
• Stack and Queue in Swift

Stack Implementation

struct Stack<T> {
    
    var array: [T] = []
    
    var isEmpty: Bool {
        return array.isEmpty
    }
    
    mutating func push(_ element: T) {
        array.append(element)
    }
    
    mutating func pop() -> T? {
        if (!isEmpty) {
            let value = array.popLast()
            return value
        }
        return nil
    }
    
    func peek() -> T? {
        if (!isEmpty) {
            let value = array.last
            return value
        }
        return nil
    }
}

Algorithm

1. For each open parenthesis we add it to stack 
2. For each close parenthesis we do following:
1. If stack is empty then return false (NOT balanced parentheses)
2. Pop value from stack and compare with this close parenthesis, if they NOT equal then return false (NOT balanced parentheses)
3. After loop if finished we check that stack is empty, if it is empty then we have balanced parentheses

func isBalancedParenthesisV3(_ string: String) -> Bool {
    
    func isValidPair(_ ch1: Character, _ ch2: Character) -> Bool {
        if (ch1 == "(" && ch2 == ")") {
            return true
        } else if (ch1 == "{" && ch2 == "}") {
            return true
        } else if (ch1 == "[" && ch2 == "]") {
            return true
        }
        return false
    }
    
    var stack = Stack<Character>()
    for ch in string {
        if (ch == "(" || ch == "{" || ch == "[") {
            stack.push(ch)
        }
        if (ch == ")" || ch == "}" || ch == "]") {
            if (stack.isEmpty) {
                return false
            } else if (!isValidPair(stack.pop()!, ch)) {
                return false
            }
        }
    }
    let result = stack.isEmpty
    return result
}

Source Code

Source code can be found on GitHub: Balanced Parentheses in Swift

References

The list of useful links

1. http://interactivepython.org/courselib/static/pythonds/BasicDS/SimpleBalancedParentheses.html
2. https://stackoverflow.com/questions/18482654/to-check-if-parenthesis-are-balanced-without-stack
3. http://blog.cybdev.org/pravilnaya-skobochnaya-posledovatelnost-ili-zadacha-o-skobkah
4. https://stackoverflow.com/questions/23187539/java-balanced-expressions-check
5. https://www.youtube.com/watch?v=IhJGJG-9Dx8
6. https://www.youtube.com/watch?v=1kseKf5HAaM
7. http://www.geeksforgeeks.org/check-for-balanced-parentheses-in-an-expression/