Go|Go Java算法之为运算表达式设计优先级实例 GoJava算法之为运算表达式设计

为运算表达式设计优先级
方法一：动态规划（Java）
方法二：分治（Go）

为运算表达式设计优先级给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以按任意顺序返回答案。
生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。

示例 1：

输入：expression = "2-1-1"
输出：[0,2]

解释：

((2-1)-1) = 0
(2-(1-1)) = 2

示例 2：
输入：expression = "23-45"
输出：[-34,-14,-10,-10,10]

解释：

(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 diffWaysToCompute(String expression) {List ops = new ArrayList(); 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[][] 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(); }}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 left = dp[l][k - 1]; List 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 intif 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）
【Go|Go Java算法之为运算表达式设计优先级实例】以上就是Go Java算法之为运算表达式设计优先级实例的详细内容，更多关于Go Java算法运算表达式优先级的资料请关注脚本之家其它相关文章！