在昨天,讀書會的學員在開會的時候詢問了我關於後序演算法的實作問題,當下覺得陌生,沒想到是大二的時候資料結構學的postfix notation,回想起來真是有趣,也沒印象當年C語言怎麼實做的(甚至只記得是做過Stack、Queue、Linklist),倒是沒印象實做過真正的運用。

當下請學員們試著實作一個App(順便練習資料結構兼具App XD),自己卻心癢癢想用Swift 實作看看,所以就找了一些資料順便重新了解一下postifix notation。

先查了一下實作方式與原理之後,在找了一下Swift 有沒有人實作過相關的Code,沒想到還真的有,稍微改進了一下他的Node與Stack所儲存的Value型態(原本為NSObject,為了運算方便,改為NSNumber),直接看Code吧!

實作步驟第一步,需要先定義出Node:

class Node {
    var value: NSNumber?
    var next: Node?
    
    init(value: NSNumber) {
        self.value = value
        self.next = Node()
    }
    
    init() {
        
    }
}

Node內有兩個直,一個為要儲存的主要值,另一個為「下一個Node」,而在Swift當中,Class是一種reference型別的變數,所以直接儲存某一個class 的實體將可以記錄下一個Node 是誰。

實作步驟第二步,定義Stack:

class Stack {
    var count: Int = 0
    var head: Node = Node()

    init() {
        
    }
    
    func isEmpty() -> Bool {
        return self.count == 0
    }
    
    func push(value: NSNumber) {
        if isEmpty() {
            self.head = Node()
        }
        
        var node = Node(value: value)
        node.next = self.head
        self.head = node
        self.count++
    }
    
    func pop() -> NSNumber? {
        if isEmpty() {
            return nil
        }
        
        var node = self.head
        self.head = node.next!
        self.count--
        
        return node.value
    }
}

其中pop與push function與資料結構課程學習的概念一樣,還有一個isEmpty function用來判斷Stack是否為空。

接下來只要嘗試使用它就可以了:

var str = "1 2 + 3 4 + *"
var value = str.componentsSeparatedByString(" ")

var stack = Stack()

for i in value {
    if (i.toInt() != nil) {
        println(i.toInt()!)
        var tempInt: Int = i.toInt()!
        stack.push(tempInt)
    }
    else {
        
        var a = Int(stack.pop()!)
        var b = Int(stack.pop()!)        
        
        switch i {
        case "+":
            println("+")
            stack.push(a+b)
        case "-":
            println("-")
            stack.push(a-b)
        case "*":
            println("*")
            stack.push(a*b)
        case "/":
            println("/")
            stack.push(a/b)
        default:
            continue
        }
    }
}

println("Final answer is (stack.pop()!)")

不難吧!其實寫完還蠻好玩的,整個遇到較多問題的部分是在測試的時候NSObject與NSNumber的轉換(所以後來才改存NSNumber),有任何錯誤或疑問歡迎留言,謝拉!

 

Reference:

  1. http://openhome.cc/Gossip/AlgorithmGossip/PostfixCal.htm
  2. https://github.com/serv/algorithms-in-swift