网络异常，图片无法展示
|
「这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战」
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
示例 1：
输入： s = "3+2*2" 输出： 7 复制代码
示例 2：
输入： s = " 3/2 " 输出： 1 复制代码
示例 3：
输入： s = " 3+5 / 2 " 输出： 5 复制代码
提示：
1 <= s.length <= 3 * 105s由整数和算符('+', '-', '*', '/')组成，中间由一些空格隔开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
如有任何问题或建议，欢迎留言讨论！
