南通的互联网公司网站,前端网站开发项目经验,如何设计网站布局,做竞价网站服务器多少钱227. 基本计算器 II#xff08;中等#xff09; 方法#xff1a;双栈解法
思路 我们可以使用两个栈 nums 和 ops 。 nums #xff1a; 存放所有的数字ops #xff1a;存放所有的数字以外的操作 然后从前往后做#xff0c;对遍历到的字符做分情况讨论#xff1a; 空格 …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) {// 存放数字的栈stackint nums;// 存放符号的栈stackchar ops;// 定义符号的优先级unordered_mapchar, int imp_op {{, 1}, {-, 1}, {*, 2}, {/, 2}};// 去除空格replace(s);// 开始遍历sfor(int i0; is.size(); i) {char c s[i];// 如果遇到数字将其之后的连续数字取出并存入numsif(isdigit(c)) {int cur_num 0;int j i;while(isdigit(s[j]) js.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(stackint nums, stackchar 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);}
};参考资料
【宫水三叶】使用「双栈」解决「究极表达式计算」问题
