Recursive Array Manipulation in Swift

Question

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.

Pass the stack into rollOpStack instead of reading from an instance variable. Have rollOpStack call itself with the next layer of the stack. — Aaron Brager
– Aaron Brager, Commented Aug 15, 2015 at 22:01
Does it have to be recursive? Also, what if I give something like ["+", "100", "1", "2", "+", "3"]? — saagarjha
– saagarjha, Commented Aug 15, 2015 at 22:11

jnoor · Accepted Answer · 2015-08-15 22:33:34Z

1

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.

edited Aug 15, 2015 at 22:33

answered Aug 15, 2015 at 22:08

jnoor

813 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

modesitt Over a year ago

I get an error for appending the newArray with the opStack because it is an arraySlice. Should I add the arrays instead?

jnoor Over a year ago

Oh yeah! My mistake. Use the + operator instead. I'll edit the answer

modesitt Over a year ago

since newArray isnt an array of Ops, it is an array slice, I cannot set it equal to the opStack. I also cant cast newArray as! [Op]. Do you know how to fix this? Sorry for all the questions!

jnoor Over a year ago

I'm not quite sure what the issue is, mostly because I never saw opStack or Op's declaration. opStack is of type [Op], correct? If so, you should be able to just declare var newArray: [Op] = opStack[index..<opStack.count]

modesitt Over a year ago

You can! I just get an error from opStack = newArray because it says I cannot assign a value of type ArraySlice<(Modal.OP)> to a value of [(Modal.Op)]

|

Collectives™ on Stack Overflow

Recursive Array Manipulation in Swift

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related