分治算法

  基本思想是将一个规模为 N的问题分解为 K 个规模较小的问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可以得到原问题的解。是一种分目标完成程序算法，简单问题用二分法完成就行。

解题步骤

• 分解，将要解决的问题划分成若干规模较小的同类问题。
• 求解，当子问题划分得足够小时，用较简单的方法解决。
• 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

题目1 为运算表达式设计优先级

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

// 输入: "2*3-4*5"
// 输出: [-34, -14, -10, -10, 10]
// (2*(3-(4*5))) = -34 
// ((2*3)-(4*5)) = -14 
// ((2*(3-4))*5) = -10 
// (2*((3-4)*5)) = -10 
// (((2*3)-4)*5) = 10

思路

• 分解： 按运算符分成左右两部分，分别求解。 以 2 * 3 - 4 * 5 为例。可以划分为
  2 和 3 - 4 * 5 两部分，中间是 * 号相连。
  2 * 3 和 4 * 5 两部分，中间是 - 号相连。
  2 * 3 - 4 和 5 两部分，中间是 * 号相连。
  有了两部分的结果，然后再通过中间的符号两两计算加入到最终的结果中即可。
• 解决： 实现一个递归，输入算式，返回算式解。
• 合并： 根据运算符合左右两部分的解，得到最终解。

代码实现如下:

function calc (num1, op, num2) {
    switch (op) {
        case "+":
            return num1 + num2
        case "-":
            return num1 - num2
        case "*":
            return num1 * num2
    }
}
function isOperation(op){
    return ["+","-","*"].includes(op);
}
function diffWaysToCompute(str){
    const len=str.length;
    if(!len) return;
    let arr1,arr2,op,value
    const result=[];
    for(let i=0;i<len;i++){
        op=str[i]
        if(isOperation(op)){
            arr1=diffWaysToCompute(str.slice(0,i));
            arr2=diffWaysToCompute(str.slice(i+1))
            for(let j=0;j<arr1.length;j++){
                for(let k=0;k<arr2.length;k++){
                    value=calc(arr1[j],op,arr2[k])
                    result.push(value);
                }
            }
        }
    }
    //没有结果时，就将当前数字添加到数组中
    if(result.length == 0){
        result.push(parseInt(str))
    }
    return result;
}