Recursive Array Manipulation in Swift

I have a custom array used by a calculator, the array acts as an RPN stack. Many real life RPN calculators allow manipulation of the stack, and I am working on the same. To get an idea an example stack would be:

["1", "2", "+"] which would evaluate to 3. The core of it is the operations follow the operands.

["2", "1", "2", "+" "x"] evaluates to 6 ["3.1415", "sin"] evaluates to 0

I would like to be able to "roll my stack" As in take the currently evaluated expression at the very end of the stack and roll it to the front. The problem is the operators, as the amount of binary and unary operators changes the way the stack is rotated.

["100", "1", "2", "+"]still would evaluate to 3, because 100 has not been accessed by an operator.

I need a way to recursively roll the stack, to take the last set of evaluated operands and roll it in front off all the operands yet to be evaluated.

Example:

["100", "1", "2", "+"] would roll to ["1", "2", "+", "100",] then ["100", "2", "1", "2", "+" "x"]would roll to ["2", "1", "2", "+" "x", "100"] and ["100", "3.1415", "sin"] would roll to ["3.1415", "sin","100"]

I am having problem with this, and the recursion of it. Currently I am doing this:

 // 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)
            }

        }
    }

This works... until more binary or unary operators are applied than just one, because the function is not recursive. How can I roll the stack recursively, and ensure that the entirety of the last evaluated list is rolled to the front of the stack? Thanks for the help.

Answers


This should do the trick:

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
    }
}

If you call beginningIndexForOperationEndingAt(opStack.count-1) you will get the starting index for the last full operation, which you can then splice from the end of the array to the beginning

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...
    }
}

Let me know if you run into any issues. Hope this helps! If it does, please don't forget to mark my answer as accepted! Thanks.


Need Your Help

Trying to add a Vibrate and Sound to my Alert View

iphone

One thing I've learned at engineering school is to always to intense validation of input. I think it's great that with the iPhone SDK you can create a sound and a vibrate option. I would like to pu...

bar chart in d3 using mysql database

javascript mysql json jsp d3.js

I have created a table by taking two columns from mysql database and converting it json object it was sucessfully working fine but i m not