题目：

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: “2-1-1”
输出: [0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2

示例 2:

输入: “23-45”
输出: [-34, -14, -10, -10, 10]
解释:
(2x(3-(4x5))) = -34
((2x3)-(4x5)) = -14
((2x(3-4))x5) = -10
(2x((3-4)x5)) = -10
(((2x3)-4)x5) = 10

简单介绍：
题目：为运算表达式设计优先级
题目难度：中等
使用语言：JAVA
这道题来自leetcode题库的分治算法标签。

解题思路：
首先看题、分析题意，我们可以明确1个关键点：
1.动态规划保存1个数字、…、N个数字的所有结果
既然，我们已经分析出来题目的关键任务了，下面我们就可以开始思考实现了。
我们采用算法与数据结构的思路来剖析一下这题

数据结构：
要实现对数据的操作，我们要先明确存储数据的数据结构。
该题的数据结构的作用：
1.列表来保存数字、操作符

算法：
既然明确了我们的数据结构，我们就可以开始我们的算法分析了。
1.第一步，初始化工作（数字、操作符分开保存）。
2.第二步，编写isOpration函数和caculate函数。
3.第三步，动态规划的方式去保存1个数字、…、N个数字的所有结果。

代码部分：

public class Solution{public List<Integer> diffWaysToCompute(String input) {//第一步，将数字和操作符拆分List<Integer> numList=new ArrayList<>();List<Character> opList=new ArrayList<>();char[] array=input.toCharArray();int num=0;for(int i=0;i<array.length;i++){if(isOpration(array[i])){numList.add(num);num=0;//重新统计数字opList.add(array[i]);continue;//跳过循环体，num的不必要增加}num=num*10+array[i]-'0';}numList.add(num);//把剩余数字加入数字列表//第三步，动态规划int N=numList.size();//数字的个数List<Integer>[][] dp=(ArrayList<Integer>[][])new ArrayList[N][N];//保存i,j计算的结果//一个数字for(int i=0;i<N;i++){List<Integer> res=new ArrayList<>();res.add(numList.get(i));dp[i][i]=res;}//两个数字到N个数字for(int n=2;n<=N;n++){//开始下标for(int i=0;i<N;i++){//结束下标int j=i+n-1;if(j>=N){break;}//把计算分为i-s，与s+1，j两部分List<Integer> res=new ArrayList<>();for(int s=i;s<j;s++){List<Integer> res1=dp[i][s];List<Integer> res2=dp[s+1][j];for(int x=0;x<res1.size();x++)for (int y=0;y<res2.size();y++){char c=opList.get(s);//取操作符res.add(caculate(res1.get(x),c,res2.get(y)));}}dp[i][j]=res;}}return dp[0][N-1];}//第二步，编写isOpration函数和caculate函数int caculate(int num1,char c,int num2){switch (c){case '+':return num1+num2;case '-':return num1-num2;case '*':return num1*num2;}return -1;}boolean isOpration(char c){if(c=='+'||c=='-'||c=='*')return true;else return false;}
}

时间、空间复杂度：

结语：
晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！