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

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

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

所谓的不同组合方式指的是用()来组合。

 比如输入: "2-1-1".

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

输出:[0,2]

分析

再看一个复杂的例子:

输入: "2*3-4*5"

(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");

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

知识共享署名4.0国际许可协议,转载请保留出处; 部分内容来自网络,若有侵权请联系我:前端学堂 » 计算输入表达式+-*的所有可能计算结果

赞 (1) 打赏

评论 0

如果对您有帮助,别忘了打赏一下宝宝哦!

支付宝扫一扫打赏

微信扫一扫打赏