Calculate 24

Posted on

算24点还是挺考验一个人的心算能力的，作为一个数学比较差劲的人，每次和别人玩24点总是会慢一个节拍，可以说是非常伤自尊了。不过虽然心算算不过别人，我们可以写一个自动计算24点的程序和别人比嘛，嘻嘻。

expression tree

ExpressionTree

我们可以利用表达式树来确定运算的优先级，进而确定运算的顺序，表达式树属于二叉树，其叶结点存储运算数（ val ），非叶子结点存储运算符 op （ +，-，*，/ ）及运算结果（ val = l.val op r.val ）。每个节点都有指向其左子节点（ l ）和右子节点（ r ）的指针，叶节点中这两个指针均为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
type node struct {
    l    *node
    r    *node
    op   rune
    val  float64
}

func (n *node) set(l, r *node, op rune) {
    n.l  = l
    n.r  = r
    n.op = op
    switch op {
    case '+':
        n.val = float64(n.l.val + n.r.val)
    case '-':
        n.val = float64(n.l.val - n.r.val)
    case '*':
        n.val = float64(n.l.val * n.r.val)
    case '/':
        n.val = float64(n.l.val / n.r.val)
    }
}

func (n *node) String() string {
    if n.op != rune(0) {
        return fmt.Sprintf(" %c ", n.op)
    }
    return fmt.Sprintf("%d", int(n.val))
}

build tree

由于存在运算优先级的原因，所以在运算数和运算符都相同的情况下当其运算顺序不同时得出的表达式树的形态也不同，例如 (1 + 8) * (7 - 13) 与 1 + 8 * 7 - 13 的运算顺序是不同的，(1 + 8) * (7 - 13) 对应的是下面第一棵树的形态， 1 + 8 * 7 - 13 对应的是下面第四棵树的形态。

1
2
3
4
5
6
7
    x               x               x                x               x
   / \             / \             / \              / \             / \
  x   x           x   x           x   x            x   x           x   x
 / \ / \             / \             / \          / \             / \
x  x x  x           x   x           x   x        x   x           x   x
                   / \                 / \          / \         / \
                  x   x               x   x        x   x       x   x

为了得出所有的可能结果，我们需要构建所有不同形态的表达式树，buildAllTrees 利用递归方法来建树，例如给定 3，4，5，6 这四个数，可以构建出上面5种形态的树。 3，4，5，6 作为参数传入，然后将数组分割为两个部分，例如上面的 3，4，5，6 可以分割为 3 和 4，5，6 或者 3，4 和 5，6 或者 3，4，5 和 6 ，然后对这两个部分分别再进行递归建树操作，当数组长度为1时也就是当 len(s) == 1 作为递归函数退出的条件，此时返回一个叶节点，按照这样的方式最终可以得到所有可能形态的树的根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func buildAllTrees(s []int) []*node {
    if len(s) == 1 {
       tree := &node{result: float64(s[0])}
       return []*node{tree}
    }

    treelist := []*node{}
    for i := 1; i < len(s); i++ {
        left := s[:i]
        right := s[i:]
        leftTrees := buildAllTrees(left)
        rightTrees := buildAllTrees(right)
        for _, l := range leftTrees {
            for _, r := range rightTrees {
                combinedTree := build(l, r)
                treelist = append(treelist, combinedTree...)
            }
        }
    }
    return treelist
}

因为存在四种运算符，例如利用 a 和 b 这两个节点构建树的时候，可以有 a+b ， a-b ， a*b ， a/b 这四种可能，所以要分别列举。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func build(l, r *node) []*node {
    var list []*node
    tree1 := &node{}
    tree1.set(l, r, '+')
    list = append(list, tree1)
    tree2 := &node{}
    tree2.set(l, r, '-')
    list = append(list, tree2)
    tree3 := &node{}
    tree3.set(l, r, '*')
    list = append(list, tree3)
    if r.result != 0.0 {
        tree4 := &node{}
        tree4.set(l, r, '/')
        list = append(list, tree4)
    }
    return list
}

我们可以通过中序遍历表达式树来遍历输出构建的表达式，由于上面我们定义了每个节点的 String 方法，如果节点为运算符，则输出其 op 的值，如果节点为叶结点，则输出其 val 值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func in(root *node) {
    if n == nil {
        return
    }
    if n.op != rune(0) {
        fmt.Print("(")
    }
    in(root.l)
    fmt.Print(n.String())
    in(root.r)
    if n.op != rune(0) {
        fmt.Print(")")
    }
}

permutation

上面的方法是对一个数组其固定的顺序构建表达式树，例如 3，4，5，6 。为了获得所有的运算表达式，我们需要对数组的所有排列组合进行表达式树的构建，例如对 6，5，4，3 ，5，6，4，3 这样的排列组合构建表达式树。也就是说除了树形态不同的这点区别之外，还要注意叶结点值存储顺序不同的带来的可能（可能会导致重复）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func Perm(a []int, f func([]int)) {
    perm(a, f, 0)
}

func perm(a []int, f func([]int), i int) {
    if i > len(a) {
        f(a)
        return
    }
    perm(a, f, i+1)
    for j := i + 1; j < len(a); j++ {
        a[i], a[j] = a[j], a[i]
        perm(a, f, i+1)
        a[i], a[j] = a[j], a[i]
    }
}

main

在主函数中我们每隔五秒钟获得一个随机的扑克牌数字，然后对于该组数字所有的排列组合分别构建表达式树，对每棵构建好的树判断其根节点的值是否接近于24（由于涉及到除法操作，所以有小数点），如果接近，则将其表达式通过中序遍历输出，这样就可以得出一组数字所有24点的可能了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
func main() {
    for {
        s := rand24()
        fmt.Println(s)
        Perm(s, func(a []int) {
            treelist := buildAllTrees(a)
            for _, root := range treelist {
                if math.Abs(24-tree.result) < 0.000001 {
                    in(root)
                    fmt.Println()
                }
            }
        })
        time.Sleep(5 * time.Second)
    }
}

func rand24() (r []int) {
    rand.Seed(time.Now().UnixNano())

    club    := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
    heart   := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
    spade   := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
    diamond := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
    
    var all []int
    all = append(all, spade...)
    all = append(all, heart...)
    all = append(all, diamond...)
    all = append(all, club...)

    r = make([]int, 4)

    exist = make(map[int]bool)
    for i := 0; i < 4; i++ {
        for {
            x := rand.Int() % len(all)
            if !exist[x] {
                exist[x] = true
                r[i] = all[x]
                break
            }
        }
    }
}
Yangyi, Yi
Pieces of Valuable Programming Knowledges
Back to Top
Go to Bottom