241. 为运算表达式设计优先级（JS实现）

朱雀 2022-11-27 15:46 136阅读 0赞

## 1 题目 ##

> 给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 \* 。  
> 示例 1:  
> 输入: “2-1-1”  
> 输出: \[0, 2\]  
> 解释:  
> ((2-1)-1) = 0  
> (2-(1-1)) = 2  
> 示例 2:  
> 输入: “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

链接：https://leetcode-cn.com/problems/different-ways-to-add-parentheses

## 2 思路 ##

**这道题主要用分治的思想来做，对于一个表达式，我们可以以其中一个运算符为分界，将其划分为两个子表达式，原表达式的计算结果就是这两个子表达式计算结果再进行运算而得到的，而这子表达式又可以进一步分割为两个表达式，如此递归下去，直至表达式不可分割，也就是只剩一个数字，所有的分割方法就是最后的答案**

## 3代码 ##

/** * @param {string} input * @return {number[]} */
    var diffWaysToCompute = function(input) { 
    if (input.length === 0) return [];
      let num = parseInt(input);
      if (num == input) return [num];    //如果是数字，则不可分割
    
      let result = [];
      for (let i=1; i<input.length-1; i++) { 
        if (parseInt(input[i]) == input[i]) continue;
        let nums1 = diffWaysToCompute(input.slice(0,i));    //以第i个运算字符，进行分割
        let nums2 = diffWaysToCompute(input.slice(i+1));
        let res;
        for (let num1 of nums1) {        //将所有子表达式的可能结果进行运算
          for (let num2 of nums2) { 
            if (input[i] === '+') { 
              res = num1 + num2;
            } else if (input[i] === '-') { 
              res = num1 - num2;
            } else { 
              res = num1 * num2;
            }
            result.push(res);
          }
        }
      }
    
      return result;
    };