轉(zhuǎn)載請(qǐng)保留作者和原始連接http://www.itdecent.cn/p/7768195814cf
源碼參考這里：
https://github.com/aesean/TwentyFour/
有多種語(yǔ)言實(shí)現(xiàn)：Java，Kotlin，Swift，Dart

上篇
http://www.itdecent.cn/p/7768195814cf
如何逆向獲得計(jì)算24的公式，思路比較死，擴(kuò)展很差，很難擴(kuò)展出5個(gè)數(shù)字，以及多種計(jì)算符號(hào)情況下。
新實(shí)現(xiàn)擴(kuò)展成了，給定任意數(shù)量數(shù)字，逆向獲得計(jì)算任意結(jié)果的公式，而且支持自定運(yùn)算符號(hào)，運(yùn)算規(guī)則。
思路其實(shí)很簡(jiǎn)單，實(shí)現(xiàn)一個(gè)排列

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

排列實(shí)現(xiàn)很簡(jiǎn)單，有點(diǎn)類(lèi)似一個(gè)加法器，不停給最后一位+1，直到超出范圍。next方法實(shí)現(xiàn)+1，當(dāng)前位如果大小超出，就給父位+1，同時(shí)把右邊的位全部置為初始0。
拿到數(shù)字排列后，

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

通過(guò)CalculateRule來(lái)遍歷所有運(yùn)算符，把運(yùn)算結(jié)果與剩余數(shù)字，組合成新的組合，然后繼續(xù)用同樣方式計(jì)算。

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

這里需要注意就是，在數(shù)學(xué)計(jì)算中，乘除如果在加減之后就不需要加括號(hào)，這個(gè)邏輯在之前實(shí)現(xiàn)里有加，現(xiàn)在用新邏輯沒(méi)有實(shí)現(xiàn)。所以，最終的計(jì)算不管是否能省略括號(hào)，都會(huì)把括號(hào)加上。
最后tree.find filter會(huì)把所有合法結(jié)果返回，然后根據(jù)自己需要過(guò)濾結(jié)果。比如是否等于24。這里需要注意一點(diǎn)是浮點(diǎn)計(jì)算會(huì)有精度問(wèn)題，比如1/3*3后結(jié)果可能不為1，所以這里需要定義一個(gè)誤差，比如0.00001等，否則會(huì)有些組合永遠(yuǎn)無(wú)法==24。