Swift中的遞歸數組操作

Question

我有一個計算器使用的自定義數組，該數組充當RPN堆棧。許多現實生活中的RPN計算器允許對堆棧進行操作，並且我也在努力。爲了得到一個想法示例堆棧將是：

["1", "2", "+"]這將評估爲3.其核心是操作遵循操作數。

["2", "1", "2", "+" "x"]的計算結果爲6 ["3.1415", "sin"]的計算結果爲0

我想能夠「卷我堆」如在採取當前評估的表達式在堆棧的最末端，並滾動到前面。問題在於運算符，因爲二進制和一元運算符的數量會改變堆棧的旋轉方式。

["100", "1", "2", "+"]仍然會評估爲3，因爲100沒有被操作員訪問。

我需要一種遞歸滾動堆棧的方法，以獲取最後一組評估操作數，並將其前滾到所有尚未評估的操作數。

實施例：

["100", "1", "2", "+"]會滾到["1", "2", "+", "100",]然後["100", "2", "1", "2", "+" "x"]會滾到["2", "1", "2", "+" "x", "100"]和["100", "3.1415", "sin"]會滾到["3.1415", "sin","100"]

我有這個問題，並且它的遞歸。目前，我這樣做：

// safeRoll 
    func rollOpStack() { 
     var lastIndex = opStack.count - 1 
     var tmp: Op = opStack[lastIndex] 
     switch tmp { 
     case .UnaryOperation: 
      if opStack.count >= 2 { 
       var tmp2: Op = opStack[lastIndex - 1] 
       var appender: [Op] = [tmp2, tmp] 
       opStack.removeLast() 
       opStack.removeLast() 
       var appended: [Op] = appender + opStack 
       opStack = appended 
      } 

     case .BinaryOperation: 
      if opStack.count >= 3 { 
       var tmp2: Op = opStack[lastIndex - 1] 
       var tmp3: Op = opStack[lastIndex - 2] 
       var appender: [Op] = [tmp3, tmp2, tmp] 
       opStack.removeLast() 
       opStack.removeLast() 
       opStack.removeLast() 
       var appended: [Op] = appender + opStack 
       opStack = appended 
      } 
     default: 
      if opStack.count > 0 { 
       opStack.removeLast() 
       println(opStack) 
       opStack.insert(tmp, atIndex: 0) 
      } 

     } 
    } 

這個工作......直到更多的二元或一元運算符的不僅僅是一個應用，因爲該函數不是遞歸。我怎樣才能遞歸地滾動堆棧，並確保整個最後一個評估列表滾動到堆棧的前面？謝謝您的幫助。

Answer 1

這應該做的伎倆：如果調用beginningIndexForOperationEndingAt(opStack.count-1)你會得到首發指數爲最後一個完整操作，然後你就可以從數組的末尾拼接到開始

func beginningIndexForOperationEndingAt(index: Int) -> Int? { 
    if index < 0 || index >= opStack.count { 
     return nil 
    } 
    switch opStack[index] { 
    case .UnaryOperation: 
     return beginningIndexForOperationEndingAt(index-1) 
    case .BinaryOperation: 
     if let firstOp = beginningIndexForOperationEndingAt(index-1) { 
      return beginningIndexForOperationEndingAt(firstOp-1) 
     } 
     return nil 
    default: 
     return index 
    } 
} 

func rollOpStack() { 
    if let index = beginningIndexForOperationEndingAt(opStack.count-1) { 
     var newArray = opStack[index..<opStack.count] 
     newArray += opStack[0..<index] 
     var i = 0 
     for op in newArray { 
      opStack[i++] = op 
     } 
    } else { 
     //No complete operation... 
    } 
} 

讓我知道你是否遇到過任何問題。希望這可以幫助！如果有，請不要忘記將我的答案標記爲已接受！謝謝。