【分治法】为运算表达式设计优先级题目要求解题思路代码实现总结

53 阅读 0 评论 35 点赞

我是靠谱客的博主拉长刺猬，最近开发中收集的这篇文章主要介绍【分治法】为运算表达式设计优先级题目要求解题思路代码实现总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目要求

给定一个字符串expression，求出这个expression所有的结果集，指定的运算符只有 '+'、'-'、'*' 这三种运算符号。

示例 1：

输入：1*2-3

输出：[-1, -1]

解释：

(1*2)-3 = -1

1*(2-3) = -1

解题思路

这道题实际是一个分治类问题，可以将问题按照运算符号，分解成：左表达式 op 右表达式；

举例说明：

1*2-3+4可以分解成如下：

第一种情况：

left：1，right：2-3+4，op：*

继续分解right可以得到：

-- 针对left

-- 1

-- 针对right

-- left：2，right：3+4，op：-

-- left：2-3，right：4，op：+

第二种情况：

left：1*2，right：3+4，op：-

-- 针对left

-- left：1，right：2，op：*

-- 针对right

-- left：3，right：4，op：+

第三种情况：

left：1*2-3，right：4，op：+

-- 针对left

-- left：1，right：2-3，op：*

-- left：1*2，right：3，op：-

-- 针对right

-- 4

可以写入公式：

leftExpression=expression.substring(0, i)

rightExpression=expression.substring(i+1, expression.length())

op=expression.charAt(i)

代码实现


class Solution {
public List<Integer> diffWaysToCompute(String expression) {
int start = 0;
int length = expression.length();
for (; start < expression.length(); start++) {
if (!Character.isDigit(expression.charAt(start))) {
break;
}
}
if (start == length) {
return Arrays.asList(Integer.parseInt(expression));
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < expression.length(); i++) {
if (!Character.isDigit(expression.charAt(i))) {
char c = expression.charAt(i);
List<Integer> left = diffWaysToCompute(expression.substring(0, i));
List<Integer> right = diffWaysToCompute(expression.substring(i + 1, length));
for (int l : left) {
for (int r : right) {
res.add(cal(l, r, c));
}
}
}
}
return res;
}
int cal(int l, int r, char c) {
if (c == '+') {
return l + r;
} else if (c == '-') {
return l - r;
} else if (c == '*') {
return l * r;
} else {
throw new RuntimeException();
}
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.diffWaysToCompute("2-1-1"));
}
}