[路飞]_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 整数

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

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

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