计算输入表达式+-*的所有可能计算结果

题目-计算+-*的所有结果 #

给定一个包含数字和运算符的字符串，计算所有可能组合方式的结果。运算符有三种：+，-，*

所谓的不同组合方式指的是用（）来组合。

 比如输入: “2-1-1”.

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

输出：[0,2]

分析 #

再看一个复杂的例子：

输入: “23-45”

(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

输出: [-34, -14, -10, -10, 10]

一般计算这种运算符操作都会用到递归的方法，因为运算符有固定的模式： a + b ， 这种中间固定式运算符，两边是参与运算的数字。

Just Try #

请你自动动手试一下：在线编程环境

想想有没有其他思路？

想想时间和空间复杂度，能否优化一下

真的做不到么？

let you think， think makes you happy!

参考答案 #

想一想逻辑哈，按照操作符来划分，这里面用到一个数组来存储数据。既然是递归，就要想想边界条件

边界条件：

• 操作符分出来第一个数据时，第一个数据没有操作，就把第一个数据放到数组中。最后的一个字符同样。
• 计算的部分比较难理解，可先按照一般情况编写，再验证复杂情况

function isOperator(x){
  return x=="+" || x=="-" || x=="*"
}
function compute(str){
  let res = [];
  for(let i=0; i< str.length; i++){
    if(isOperator(str[i])){
      let lnum = compute(str.substr(0,i))
      let rnum = compute(str.substr(i+1,str.length-1))

      lnum.forEach(l=>{
        rnum.forEach(r=>{
          switch(str[i]){
            case "+": res.push(l+r); break;
            case "-": res.push(l-r); break;
            case "*": res.push(l*r); break;
          }
        })
      })
    }
  }
  if(res.length == 0){
    res.push(+str)
  }
  return res;
}
function algorithm(str){
  return compute(str)
}
function main(param) {
  console.show("参数：" + param, "结果：" + JSON.stringify(algorithm(param)))
  testPerformance(algorithm, param)
}
main("2*3-4*5");

请你自动动手试一下：在线编程环境