亲宝软件园·资讯

展开

Go Java算法运算表达式优先级

黄丫丫 人气:0

为运算表达式设计优先级

给你一个由数字和运算符组成的字符串 expression ,按不同优先级组合数字和运算符,计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

生成的测试用例满足其对应输出值符合 32 位整数范围,不同结果的数量不超过 104 。

输入:expression = "2-1-1"

输出:[0,2]

解释:

((2-1)-1) = 0

(2-(1-1)) = 2

解释:

(2*(3-(4*5))) = -34

((23)-(45)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-4)*5) = 10  

提示:

1 <= expression.length <= 20

expression 由数字和算符 '+'、'-' 和 '*' 组成。

输入表达式中的所有整数值在范围 [0, 99] 

方法一:动态规划(Java)

因为最终的答案是由一个个子问题(子表达式)的答案所构成,所以我们可以采用动态规划,将问题划分为一个个子问题来求解。

做出此题最关键的一步是要写出合理的动态规划递归式。第一想法是定义dp[i]表示前i个数计算的结果,这样定义我们很快会发现我们无法写出dp[i+1],因为它们相互包含,没有明确的界限。

比较好的递归式是定义dp[i][j]表示从第i个数开始到第j个数的表达式计算的结果,最终结果就是要求dp[0][N-1]。

首先我们将字符串分成digit、op、digit、op、digit、op、digit.....这样的序列,并且可知序列的长度是奇数个,所以子问题的最小长度为3(长度为1的digit不需要计算),也就是一个op运算需要至少三个元素(两个digit和一个op),下一个子问题的长度为当前子问题+2(加一个op和一个digit),所以我们可以从最小长度为3的子问题一步步求解最大长度的解。

class Solution {
    static final int ADDITION = -1;
    static final int SUBTRACTION = -2;
    static final int MULTIPLICATION = -3;
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> ops = new ArrayList<Integer>();
        for (int i = 0; i < expression.length();) {
            if (!Character.isDigit(expression.charAt(i))) {
                if (expression.charAt(i) == '+') {
                    ops.add(ADDITION);
                } else if (expression.charAt(i) == '-') {
                    ops.add(SUBTRACTION);
                } else {
                    ops.add(MULTIPLICATION);
                }
                i++;
            } else {
                int t = 0;
                while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
                    t = t * 10 + expression.charAt(i) - '0';
                    i++;
                }
                ops.add(t);
            }
        }
        List<Integer>[][] dp = new List[ops.size()][ops.size()];
        for (int i = 0; i < ops.size(); i++) {
            for (int j = 0; j < ops.size(); j++) {
                dp[i][j] = new ArrayList<Integer>();
            }
        }
        for (int i = 0; i < ops.size(); i += 2) {
            dp[i][i].add(ops.get(i));
        }
        for (int i = 3; i <= ops.size(); i++) {
            for (int j = 0; j + i <= ops.size(); j += 2) {
                int l = j;
                int r = j + i - 1;
                for (int k = j + 1; k < r; k += 2) {
                    List<Integer> left = dp[l][k - 1];
                    List<Integer> right = dp[k + 1][r];
                    for (int num1 : left) {
                        for (int num2 : right) {
                            if (ops.get(k) == ADDITION) {
                                dp[l][r].add(num1 + num2);
                            } else if (ops.get(k) == SUBTRACTION) {
                                dp[l][r].add(num1 - num2);
                            } else if (ops.get(k) == MULTIPLICATION) {
                                dp[l][r].add(num1 * num2);
                            }
                        }
                    }
                }
            }
        }
        return dp[0][ops.size() - 1];
    }
};

时间复杂度:O(2^n)

空间复杂度:O(2^n)

方法二:分治(Go)

分治:定义最后一个生效的符号位置。比如 a+b+c+d,我们定义第二个加号,为最后的计算位置,则可以得到【a+b】+【c+d】,类似这样的格式。然后此时可以发现 A=a+b 是一个表达式,B=c+d也是一个表达式,他们可以分别计算出各自的结果,然后再通过这个加号计算 A+B,每组两部分的和就对应所有可能的结果

对于一个形如 x op y(op 为运算符,x 和 y 为数) 的算式而言,它的结果组合取决于 x 和 y 的结果组合数,而 x 和 y 又可以写成形如 x op y 的算式。

因此,该问题的子问题就是 x op y 中的 x 和 y:以运算符分隔的左右两侧算式解。

分治算法三步走:

import (
    "fmt"
    "strconv"
)
func diffWaysToCompute(input string) []int {
    // 如果是数字,直接返回
    if isDigit(input) {
        tmp, _ := strconv.Atoi(input)
        return []int{tmp}
    }
    // 空切片
    var res []int 
    // 遍历字符串
    for index, c := range input {
        tmpC := string(c)
        if tmpC == "+" || tmpC == "-" || tmpC == "*" {
            // 如果是运算符,则计算左右两边的算式
            left := diffWaysToCompute(input[:index])
            right := diffWaysToCompute(input[index+1:])
            for _, leftNum := range left {
                for _, rightNum := range right {
                    var addNum int
                    if tmpC == "+" {
                        addNum = leftNum + rightNum
                    } else if tmpC == "-" {
                        addNum = leftNum - rightNum
                    } else {
                        addNum = leftNum * rightNum
                    }
                    res = append(res, addNum)
                }
            }
        }
    }
    return res
}
// 判断是否为全数字
func isDigit(input string) bool {
    _, err := strconv.Atoi(input)
    if err != nil {
        return false
    }
    return true
}

时间复杂度:O(2^n)

空间复杂度:O(2^n)

加载全部内容

相关教程
猜你喜欢
用户评论