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

The Heavy Pill Task. Solution in Swift

There are 20 bottles of pills. 19 bottles have pills of weight 1.0 gram, but one has pills of weight 1.1 grams. How to find heavy bottle? There is constraint: you can make only one measurement.

In order to find a bottle with heavy pills let's take 1 pill from a first bottle 2 from the second and so on up to 20. Also, we know in advance the total weight of pills in this calculation if in all bottles the pills weigh 1 gram. It will be 1 + 2 + 3 + ... + 20 = 210 grams. Thus, we need to deduct the summary weight of all normal pills from the summary weight of pills with heavy pills and divide by the difference between the weight of the heavy and normal pills(1.1 - 1 = 0.1 grams).

So, formula is

bottleNumber = (summaryWeightWithHeavy - summaryWeightNormal) / (diff)

where summaryWeightNormal = 210 grams, diff = 0.1 grams

bottleNumber = (summaryWeightWithHeavy - 210) / 0.1

Coding algorithm for checking solution and formula:

1. Generate random number for heavy bottle
2. In loop from 1 to number of bottles we calculate normal weight and "heavy" weight(when one of bottles has heavy pills)
3. According to our formula: We take the normal total weight from the heavy total weight and divide this difference by the difference between the weights for one pill
4. Check that found bottle number equals initial bottle number

Source code

import Foundation

let bottlesCount = 20
let normalPill = 1.0
let heavyPill = 1.1
let diff = heavyPill - normalPill

let heavyBottleNumber = 1 + Int(arc4random_uniform(UInt32(bottlesCount)))
print(heavyBottleNumber)

var normalWeight = 0.0
var heavyWeight = 0.0

for i in 1...bottlesCount {
    normalWeight += Double(i)
    if i == heavyBottleNumber {
        heavyWeight += (Double(i) * heavyPill)
    } else {
        heavyWeight += Double(i)
    }
}


let result = Int(round((heavyWeight - normalWeight) / diff))
print(result)
assert(heavyBottleNumber == result, "failed")

iOS Swift. Difference between leftAnchor and leadingAnchor

When we working with constraint programatically we can have two options for left side: leadingAnchor and leftAnchor, the same for right side: rightAnchor and trailingAnchor.

What is the difference between this anchors?

for left side

self.view.leftAnchor

and

self.view.leadingAnchor

for right side:

self.view.rightAnchor

and

self.view.trailingAnchor

leftAnchor and rightAnchor are strongly fixed and always depend on the left and right sides of the screen. leadingAnchor and trailingAnchor are flexible and depend on the device locale. For locales, where the spelling is from left to right this anchors can be used interchangeably(left with leading and right with trailing). For locales, where the spelling is from right to left leadingAnchor will depend on the right side and trailingAnchor will depend the left side.

For example, you have a screen on which the label is located on the left and textfield on the right for the locale where the writing is from left to right. For a locale where the spelling is from right to left label will be located right and textfield on the left.

You should always use leadingAnchor and trailingAnchor instead of leftAnchor and rightAnchor unless you have special requirements that say that the interface elements are always depend on the left or on the right.

If you want the interface element to be on the screen on the left or right depending on the locale, then use leadingAnchor and trailingAnchor, respectively.

If you want the interface element to always be located on the left or right, regardless of the locale, then use leftAnchor and rightAnchor , respectively.

iOS Swift. All ways to unwrap optional

There I want to enumerate all possible ways to unwrap optional variables that possible in Swift.

1. Force Unwrapping
2. Check for nil (with !=) and Force Unwrapping
3. Ternary Operator
4. if let Construction or Single Optional Binding
5. Multiple Optional Binding
6. Guard Operator
7. Nil Coalescing Operator
8. Switch Operator
9. Optional Chaining

Let's review each of them.

Force Unwrapping

When you have optional and you are sure that this optional has a value you always can just use force unwrapping with ! (exclamation point operator). But it always for your responsibility use this because there can be situations when optional will have no value and force unwrapping will produce error and app crashing.

let dict = [1: "Jack", 2: "John", 9: "Kate", 77: "Charlie"]
let name1 = dict[1]
let name4 = dict[4]
print(name1!) // "Jack"
print(name4!) // Fatal error: Unexpectedly found nil while unwrapping an Optional value

Check for nil

But there is solution for ensure from errors when using force unwrapping - just check optional for nil before that.

let dict = [1: "Jack", 2: "John", 9: "Kate", 77: "Charlie"]

print(dict[1]) // Optional("Jack")
print(dict[4]) // nil

func getName(for index: Int) -> String {
    if dict[index] != nil {
        return dict[index]!
    }
    return "No name for such index"
}

print(getName(for: 1)) // "Jack"
print(getName(for: 4)) // No name for such index

Ternary Operator

The same check for nil can be done with ternary operator.

let dict = [1: "Jack", 2: "John", 9: "Kate", 77: "Charlie"]

print(dict[1]) // Optional("Jack")
print(dict[4]) // nil

func getName(for index: Int) -> String {
    return dict[index] != nil ? dict[index]! : "No name for such index"
}

print(getName(for: 1)) // "Jack"
print(getName(for: 4)) // No name for such index

if let Construction or Optional Binding

This construction if let allows you safety unwrap optional value. If optional has value then this value will be unwrapped to constant/variable. Unwrapped variable/constant will be available only in scope inside this if let statement.

let dict = [1: "Jack", 2: "John", 9: "Kate", 77: "Charlie"]

print(dict[1]) // Optional("Jack")
print(dict[4]) // nil

func getName(for index: Int) -> String {
    if let name = dict[index] {
        return name
    }
    return dict[index] ?? "No name for such index"
}

print(getName(for: 1)) // "Jack"
print(getName(for: 4)) // No name for such index

Multiple Optional binding

There can be optional property of optional object, so you can do some chaining of if let statements. All this if let statements can be written in on line with one if and with commas. Every next statement will be executed only if previous value is unwrapped.

struct A {
    let dict = [1: "Jack", 2: "John", 9: "Kate", 77: "Charlie"]
    func getName(for index: Int) -> String? {
        return dict[index]
    }
}

struct B {
    var names: A?
    
    init() {
        self.names = A()
    }
}

let b: B? = B()

if let b = b {
    if let names = b.names {
        if let name = names.getName(for: 1) {
            print(name) // Jsck
        }
    }
}

if let b = b, let names = b.names, let name = names.getName(for: 1) {
    print(name) // Jack
}

Guard Operator

Guard operator or "Early Exit" check that optional has value and can be unwrapped. If optional has no value then else statement will be executed. Unwrapped value will be available in scope next to guard, opposite to if let statement.

let dict = [1: "Jack", 2: "John", 9: "Kate", 77: "Charlie"]

print(dict[1]) // Optional("Jack")
print(dict[4]) // nil

func getName(for index: Int) -> String {
    guard let name = dict[index] else {
        return "No name for such index"
    }
    return name
}

print(getName(for: 1)) // "Jack"
print(getName(for: 4)) // No name for such index

Nil Coalescing Operator or ??

Special operator ?? works following way: if there is a value in optional then this value will be return else default value will be return.

let dict = [1: "Jack", 2: "John", 9: "Kate", 77: "Charlie"]

print(dict[1]) // Optional("Jack")
print(dict[4]) // nil

func getName(for index: Int) -> String {
    return dict[index] ?? "No name for such index"
}

print(getName(for: 1)) // "Jack"
print(getName(for: 4)) // No name for such index

Switch Operator

We can use switch operator for unwrapping optionals because if we open source code of Optional we can see that Optional is an enum with 2 cases: none and some.

public enum Optional<Wrapped> : ExpressibleByNilLiteral {
    case none
    case some(Wrapped)
}

In case of .none - there is no value (it means nil). In case of .some - there is a value that we can use and this value will be unwrapped.

let dict = [1: "Jack", 2: "John", 9: "Kate", 77: "Charlie"]

func getName(for index: Int) -> String {
    let name =  dict[index]
    switch name {
    case .some(let value):
        return value
    case .none:
        return "No name for such index"
    }
}

print(getName(for: 1)) // Jack
print(getName(for: 4)) // No name for such index

Optional Chaining

In some cases optional instance of struct or class can have optional properties. So, when we need to get optional property of optional object it is a chain of optionals. Every next optional value will be unwrap only if previous is can be unwrapped. For, example

b?.names?.getName(for: 1)?.count

Property count will be getting only if b can be unwrapped, names can be unwrapped and value which will be returned by getNames() can be unwrapped too. If any of values in chain cannot be unwrapped then property count will be nil.

struct A {
    let dict = [1: "Jack", 2: "John", 9: "Kate", 77: "Charlie"]
    func getName(for index: Int) -> String? {
        return dict[index]
    }
}

struct B {
    var names: A?
    
    init() {
        self.names = A()
    }
}

let b: B? = B()
b?.names?.getName(for: 4)?.count

print(b?.names?.getName(for: 1)?.count) // Optional(4) because "Jack" has 4 letters
print(b?.names?.getName(for: 4)?.count) // nil because no name for such index