如何逆向获得计算24的公式续

转载请保留作者和原始连接http://www.jianshu.com/p/7768195814cf
源码参考这里：
https://github.com/aesean/TwentyFour/
有多种语言实现：Java，Kotlin，Swift，Dart

上篇
https://www.jianshu.com/p/7768195814cf
如何逆向获得计算24的公式，思路比较死，扩展很差，很难扩展出5个数字，以及多种计算符号情况下。
新实现扩展成了，给定任意数量数字，逆向获得计算任意结果的公式，而且支持自定运算符号，运算规则。
思路其实很简单，实现一个排列

class Arrangement {
    private let size: Int
    private var mainIndex = -1
    private var childIndex = -1

    init(_ size: Int) {
        self.size = size
    }

    private func next() -> Bool {
        if mainIndex == -1 && childIndex == -1 {
            mainIndex = 0
            childIndex = 1
            return true
        }
        childIndex += 1
        var check = false
        if childIndex < size {
            check = true
        } else {
            childIndex = 0
            mainIndex += 1
            if mainIndex < size {
                check = true
            }
        }
        if check {
            if mainIndex == childIndex {
                return next()
            } else {
                return true
            }
        }
        return false
    }

    func traversal(_ result: (_ left: Int, _ right: Int) -> Void) {
        mainIndex = -1
        childIndex = -1
        while next() {
            result(mainIndex, childIndex)
        }
    }
}

排列实现很简单，有点类似一个加法器，不停给最后一位+1，直到超出范围。next方法实现+1，当前位如果大小超出，就给父位+1，同时把右边的位全部置为初始0。
拿到数字排列后，

class CalculateRuleImpl: CalculateRule {
    private static let SYMBOLS = ["+", "-", "×", "÷"]

    func size() -> Int {
        return CalculateRuleImpl.SYMBOLS.count
    }

    func calculate(a: String, index: Int, b: String) throws -> String {
        let aNum = NSDecimalNumber(string: a)
        let bNum = NSDecimalNumber(string: b)

        switch index {
        case 0:
            return aNum.adding(bNum).stringValue
        case 1:
            return aNum.subtracting(bNum).stringValue
        case 2:
            return aNum.multiplying(by: bNum).stringValue
        case 3:
            if b == "0" || b == "0.0" {
                throw CalculateError()
            }
            return aNum.dividing(by: bNum).stringValue
        default:
            return ""
        }
    }

    func symbol(index: Int) -> String {
        return CalculateRuleImpl.SYMBOLS[index]
    }
}

通过CalculateRule来遍历所有运算符，把运算结果与剩余数字，组合成新的组合，然后继续用同样方式计算。

class Tree {
    let nodes: [Node]
    let calculateRule: CalculateRule
    let nodeArrangement: Arrangement

    init(nodes: [Node], mathRule: CalculateRule) {
        self.nodes = nodes
        self.calculateRule = mathRule
        self.nodeArrangement = Arrangement(nodes.count)
    }

    func find(filter: (_ result: Node) -> Void) {
        nodeArrangement.traversal({ (left: Int, right: Int) -> Void in
            let leftNode = nodes[left]
            let rightNode = nodes[right]

            for symbolIndex in 0..<calculateRule.size() {
                var result: [Node] = []
                for i in 0..<nodes.count {
                    if i != left && i != right {
                        result.append(nodes[i])
                    }
                }

                var number: String
                do {
                    number = try calculateRule.calculate(a: leftNode.number, index: symbolIndex, b: rightNode.number)
                } catch {
                    continue
                }
                let node = Node(num: number)
                node.desc = "(\(leftNode.desc)\(calculateRule.symbol(index: symbolIndex))\(rightNode.desc))"
                result.append(node)
                if result.count > 1 {
                    Tree(nodes: result, mathRule: calculateRule).find(filter: filter)
                } else {
                    filter(result[0])
                }
            }
        })
    }
}

这里需要注意就是，在数学计算中，乘除如果在加减之后就不需要加括号，这个逻辑在之前实现里有加，现在用新逻辑没有实现。所以，最终的计算不管是否能省略括号，都会把括号加上。
最后tree.find filter会把所有合法结果返回，然后根据自己需要过滤结果。比如是否等于24。这里需要注意一点是浮点计算会有精度问题，比如1/3*3后结果可能不为1，所以这里需要定义一个误差，比如0.00001等，否则会有些组合永远无法==24。