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/

Stack and Queue in Swift. Generic Implementation

I already described Stack and Queue data structures and how to implement them in Swift in my previous post about stack and queue. There I used class (reference type) for implementing stack and queue, also I used them for resolve task for define that string is palindrome.

Now let's update our implementation, for now let's use struct (value type) because it is always preferable to use struct(value type) if it no need for class features (like inheritance for example).

Non generic implementation (only for Int type)

Stack Implementation

// LIFO - Last In First Out
struct Stack {
    
    var array: [Int] = []
    
    var isEmpty: Bool {
        return array.isEmpty
    }
    
    // add new element to the stack
    mutating func push(_ element: Int) {
        array.append(element)
    }
    
    // get the last element from the stack and remove it form stack
    mutating func pop() -> Int? {
        if !isEmpty {
            let value = array.removeLast()
            return value
        }
        return nil
    }
    
    // get the head of stack - the last element
    mutating func peek() -> Int? {
        if !isEmpty {
            let value = array.last
            return value
        }
        return nil
    }
}

Queue Implementation

// FIFO - First In First Out
struct Queue {
    
    var array: [Int] = []
    
    var isEmpty: Bool {
        return array.isEmpty
    }
    
    // add new element to queue
    mutating func enqueue(_ element: Int) {
        array.append(element)
    }
    
    // get the first element and remove it from queue
    mutating func dequeue() -> Int? {
        if !isEmpty {
            let value = array.removeFirst()
            return value
        }
        return nil
    }
    
    // get the head of queue - the first element
    mutating func peek() -> Int? {
        if !isEmpty {
            let value = array.first
            return value
        }
        return nil
    }
}

Here example of adding randomly generated integer number to stack and queue.

var stack = Stack()
var queue = Queue()
    
let randomNumer = Int(arc4random_uniform(100))
stack.push(randomNumer)
queue.enqueue(randomNumer)

Generic Implementation

But it is always useful to write universal solutions for our tasks. So let's implement generic versions of stack and queue.

Stack Implementation

// LIFO - Last In First Out
struct Stack<T> {
    
    var array: [T] = []
    
    var isEmpty: Bool {
        return array.isEmpty
    }
    
    // add new element to the stack
    mutating func push(_ element: T) {
        array.append(element)
    }
    
    // get the last element from the stack and remove it form stack
    mutating func pop() -> T? {
        if !isEmpty {
            let value = array.popLast()
            return value
        }
        return nil
    }
    
    // get the head of stack - the last element
    func peek() -> T? {
        if !isEmpty {
            let value = array.last
            return value
        }
        return nil
    }
    
}

Queue Implementation

// FIFO - First In First Out
struct Queue<T> {
    
    var array: [T] = []
    
    var isEmpty: Bool {
        return array.isEmpty
    }
    
    // add new element to queue
    mutating func enqueue(_ element: T) {
        array.append(element)
    }
    
    // get the first element and remove it from queue
    mutating func dequeue() -> T? {
        if !array.isEmpty {
            let value = array.removeFirst()
            return value
        }
        return nil
    }
    
    // get the head of queue - the first element
    mutating func peek() -> T? {
        if !array.isEmpty {
            let value = array.first
            return value
        }
        return nil
    }
    
}

Now we can easily use stack for any type we need. For Integer:

var stack = Stack<Int>()
var queue = Queue<Int>()
    
let randomNumer = Int(arc4random_uniform(100))
stack.push(randomNumer)
queue.enqueue(randomNumer)

Or for String

var stack = Stack<String>()
var queue = Queue<String>()

Or even for Any, in this case we can add to stack and queue String and Integer both.

var stack = Stack<Any>()
var queue = Queue<Any>()

Demo Application

Stack and Queue before the values are obtained from them

Stack and Queue after the values are obtained from them

Source Code

Source code for demo app can be found on GitHub: Stack vs Queue Demo App

Stack and Queue in Swift. Palindrome Test App

Theory of Stack and Queue

Stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. In the stacks following operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure - elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the top.

Queue is a container of objects that are inserted and removed according to the first-in first-out (FIFO) principle. New additions to a line made to the back of the queue, while removal (or serving) happens in the front. In the queue following operations are allowed enqueue and dequeue. Enqueue means to insert an item into the back of the queue, dequeue means removing the front item.

Definitions getting from https://www.cs.cmu.edu

Task 

Determine that a given string is a palindrome. A palindrome is a phrase which reads the same backward and forward.

Algorithm

Version 1

1. First loop. For each character symbol of string add to queue and to stack.
2. Second loop. From 0 to N - 1 (where N = length of string) get symbol  from queue and from stack (when queue we get symbol from begin, when stack we get symbol from end) and compare them. Because if any pair is not equals then it is not palindrome.

Version 2
We can improve this algorithm. Not check the whole word but only half of it, because it will be enough for determine palindrome.

Implementation

Queue Implementation

import Foundation

// FIFO - First In First Out
class Queue {
    var arr: [Character]
    
    init() {
        self.arr = [Character]()
    }
    
    // add new element to queue
    func enqueue(ch: Character) -> Void {
        self.arr.append(ch)
    }
    
    // get the head of queue - the first element
    func peek() -> Character? {
        return self.arr.first
    }
    
    // get the first element and remove it from queue
    func dequeue() -> Character {
        return self.arr.removeFirst()
    }
}

Stack Implementation

import Foundation

// LIFO - Last In First Out
class Stack {
    var arr: [Character]
    
    init() {
        self.arr = [Character]()
    }
    
    // get the head of stack - the last element
    func peek() -> Character? {
        return self.arr.last
    }
    
    // get the last element from the stack and remove it form stack
    func pop() -> Character {
        return self.arr.removeLast()
    }
    
    // add new element to the stack
    func push(ch: Character) -> Void {
       self.arr.append(ch)
    }
    
}

Checking for Palindrome

@IBAction func checkButtonTapped(_ sender: UIButton) {
    if let str = textField.text, str.count > 0 {
        let count = str.count
        var isPalindrome = true
        let queue = Queue()
        let stack = Stack()
        for ch in str {
            queue.enqueue(ch)
            stack.push(ch)
        }
        for _ in 0...(count - 1) {
            if queue.dequeue() != stack.pop() {
                isPalindrome = false
                break
            }
        }
            
        if isPalindrome {
            resultLabel.text = "Palindrome Found!"
        } else {
            resultLabel.text = "NOT Palindrome!"
        }
    } else {
        resultLabel.text = "Empty String"
    }
}

Checking for Palindrome(Improved - Check only half of word)

@IBAction func checkButtonTapped(_ sender: UIButton) {
    if let str = textField.text, str.count > 0 {
        let count = str.count
        var isPalindrome = true
        let queue = Queue()
        let stack = Stack()
        for ch in str {
            queue.enqueue(ch)
            stack.push(ch)
        }
        for _ in 0...(count / 2) {
            if queue.dequeue() != stack.pop() {
                isPalindrome = false
                break
            }
        }
            
        if isPalindrome {
            resultLabel.text = "Palindrome Found!"
        } else {
            resultLabel.text = "NOT Palindrome!"
        }
    } else {
        resultLabel.text = "Empty String"
    }
}

Results

Results - Not Palindrome

Results - Palindrome

Source Code

Source code for this demo project can be found here: PalindromeTest