分治法

分治法

https://labuladong.gitee.io/algo/4/32/127/

为运算表达式设计优先级

https://leetcode-cn.com/problems/different-ways-to-add-parentheses/

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
func diffWaysToCompute(expression string) []int {
    res := make([]int, 0)

    // 遍历字符串，如果是运算符就【分】
    for i := 0; i < len(expression); i++ {
        c := expression[i]
        if c == '+' || c == '-' || c == '*' {
            // 【分】成左右两边计算可能出现的结果
            left := diffWaysToCompute(expression[:i])
            right := diffWaysToCompute(expression[i+1:])

            // 【治】根据返回的结果，暴力计算出所有可能的值
            for _, a := range left {
                for _, b := range right {
                    switch c {
                        case '+':
                            res = append(res, a + b)
                        case '-':
                            res = append(res, a - b)
                        case '*':
                            res = append(res, a * b)
                    }
                }
            }
        }
    }

    // base case: expression 不包含运算符，它只是一个数字
    if len(res) == 0 {
        n, _ := strconv.Atoi(expression)
        res = append(res, n)
    }

    return res
}