[路飞]_leetcode-227-基本计算器 II - 掘金

「这是我参与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 整数

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

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

代码如下：

//  获取字符权重
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

如有任何问题或建议，欢迎留言讨论！

常见问题FAQ

免费下载或者VIP会员专享资源能否直接商用？: 本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。

提示下载完但解压或打开不了？: 最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量，若小于网盘提示的容量则是这个原因。这是浏览器下载的bug，建议用百度网盘软件或迅雷下载。若排除这种情况，可在对应资源底部留言，或联络我们.。

找不到素材资源介绍文章里的示例图片？: 对于PPT，KEY，Mockups，APP，网页模版等类型的素材，文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买，且本站不负责(也没有办法)找到出处。同样地一些字体文件也是这种情况，但部分素材会在素材包内有一份字体下载链接清单。