最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • [路飞]_leetcode-227-基本计算器 II - 掘金

    正文概述 掘金(前端_奔跑的蜗牛)   2021-11-25   497

    「这是我参与11月更文挑战的第20天,活动详情查看:2021最后一次更文挑战」

    [题目地址] [B站地址]

    给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。

    整数除法仅保留整数部分。

     

    示例 1:

    输入: s = "3+2*2"
    输出: 7
    

    示例 2:

    输入: s = " 3/2 "
    输出: 1
    

    示例 3:

    输入: s = " 3+5 / 2 "
    输出: 5
    

    提示:

    • 1 <= s.length <= 3 * 105
    • s 由整数和算符 ('+', '-', '*', '/') 组成,中间由一些空格隔开
    • s 表示一个 有效表达式
    • 表达式中的所有整数都是非负整数,且在范围 [0, 231 - 1] 内
    • 题目数据保证答案是一个 32-bit 整数

    本题要求我们将输入字符串的运算结果返回,我们可以通过两个 来维护当前的运算符和数值,每次取出栈顶的元素进行计算,具体解题思路如下:

    1. 创建运算符栈存储运算符
    2. 创建数值栈存储数值
    3. 遍历输入字符串表达式,将对应运算符和数值存储入栈
    4. 运算符的优先级通过一个函数 level 来维护,每次出现新的运算符的时候,将运算符栈中权重大于等于它的运算完成,再将它压入栈
    5. 每次参与运算的值为数值栈的栈顶两个值,运算结果再压入数值栈
    6. 当运算符栈为空时,数值栈中将会剩余一个值,就是我们要求得的结果

    代码如下:

    //  获取字符权重
    function level(operater){
      switch(operater){
        case '+':
        case '-':
        return 1;
        case '*':
        case '/':
        return 2;
        case '@':
        return -1;
        default:
        return 0;
      }
    }
    // 运算
    function calc(num1,operater,num2){
      switch(operater){
        case '+':
        return num1+num2
        case '-':
        return num1-num2;
        case '*':
        return num1*num2;
        case '/':
        return Math.floor(num1/num2)
      }
    }
    var calculate = function(s) {
      // 运算符栈
      const operaters = ['@'],
      // 数值栈
      nums = [];
      // 当前数值
      let num = 0;
      for(let i = 0;i<s.length;i++){
        // 空格跳过
        if(s[i]===' ') continue;
        // 如果是数字,更新当前数值
        if(level(s[i])===0){
          num = num*10+s[i]*1
        }else{
          // 如果是运算符,将数值入栈
          nums.push(num);
          num = 0;
          // 当栈中有权重大于等于当前运算符的值时,进行运算
          while(level(operaters[operaters.length-1])>=level(s[i])){
            const num2 = nums.pop(),
            num1 = nums.pop(),
            operater = operaters.pop();
            nums.push(calc(num1,operater,num2)) 
          }
          // 将本次运算符入栈
          operaters.push(s[i])
        }
      }
      // 将最后一个数值入栈
      nums.push(num);
      // 因为入栈的过程保证了后面的运算符权重更高
      // 所以可以从后向前的进行运算
      while(operaters.length>1){
        const num2 = nums.pop(),
        num1 = nums.pop(),
        operater = operaters.pop();
        nums.push(calc(num1,operater,num2)) 
      }
      return nums[0]
    };
    

    这里我们利用在运算符栈底插入 @ ,并将其权重设置为 -1 的技巧,来省去判断栈为空的情况

    至此我们就完成了 leetcode-227-基本计算器 II

    如有任何问题或建议,欢迎留言讨论!


    起源地 » [路飞]_leetcode-227-基本计算器 II - 掘金

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元