【LeetCode】227. 基本计算器 II

227. 基本计算器 II（中等）

在这里插入图片描述

方法：双栈解法

思路

我们可以使用两个栈 nums 和 ops 。
- nums ：存放所有的数字
- ops ：存放所有的数字以外的操作
然后从前往后做，对遍历到的字符做分情况讨论：
- 空格 : 跳过
- 数字 : 从当前位置开始继续往后取，将整一个连续数字整体取出，加入 nums
- +、-、*、/ : 需要将操作放入 ops 中。在放入之前先把栈内可以算的都算掉（只有「栈内运算符」比「当前运算符」优先级高/同等，才进行运算），使用现有的 nums 和 ops 进行计算，直到没有操作，计算结果放到 nums。
细节：可以通过 unordered_map 手动为运算符设置优先级，当遇到操作符号，如果栈内已经存在操作符，先比较它们的优先级，判断是否可以进行运算。
我们可以通过例子来理解 只有「栈内运算符」比「当前运算符」优先级高/同等，才进行运算 是什么意思：
- 因为我们是从前往后做的，假设我们当前已经扫描到 2 + 1 了（此时栈内的操作为 + ）。
- 如果后面出现的 + 2 或者 - 1 的话，满足「栈内运算符」比「当前运算符」优先级高/同等，可以将 2 + 1 算掉，把结果放到 nums 中；
- 如果后面出现的是 * 2 或者 / 1 的话，不满足「栈内运算符」比「当前运算符」优先级高/同等，这时候不能计算 2 + 1。

代码

class Solution {
public:void replace(string &s) {int pos = s.find(" ");while(pos != -1) {s.replace(pos, 1, "");pos = s.find(" ");}}int calculate(string s) {// 存放数字的栈stack<int> nums;// 存放符号的栈stack<char> ops;// 定义符号的优先级unordered_map<char, int> imp_op = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};// 去除空格replace(s);// 开始遍历sfor(int i=0; i<s.size(); ++i) {char c = s[i];// 如果遇到数字，将其之后的连续数字取出并存入numsif(isdigit(c)) {int cur_num = 0;int j = i;while(isdigit(s[j]) && j<s.size()) {cur_num = cur_num * 10 + (s[j++] - '0');}nums.push(cur_num);i = j - 1;}// + - * /else {// 如果符号栈内有符号，需要先将可计算的算完while(!ops.empty() && imp_op[ops.top()] >= imp_op[c]) {calc(nums, ops);}ops.push(c);}} while(!ops.empty()) calc(nums, ops);return nums.top();}void calc(stack<int> &nums, stack<char> &ops) {if(nums.size() < 2 || ops.empty()) return ;int b = nums.top(); nums.pop();int a = nums.top(); nums.pop();char op = ops.top(); ops.pop();int res;if(op == '+')   res = a + b;else if(op == '-') res = a - b;else if(op == '*') res = a * b;else if(op == '/') res = a / b;nums.push(res);}
};