建行网站济南,专业模板建站哪家好,摄影网站cnu视觉联盟,网站后台是怎么做出来的224. 基本计算器#xff08;困难#xff09; 方法#xff1a;双栈解法
思路 我们可以使用两个栈 nums 和 ops 。 nums #xff1a; 存放所有的数字ops #xff1a;存放所有的数字以外的操作#xff0c;/- 也看做是一种操作 然后从前往后做#xff0c;对遍历到的字符做…224. 基本计算器困难 方法双栈解法
思路 我们可以使用两个栈 nums 和 ops 。 nums 存放所有的数字ops 存放所有的数字以外的操作/- 也看做是一种操作 然后从前往后做对遍历到的字符做分情况讨论 空格 : 跳过( : 直接加入 ops 中等待与之匹配的 )) : 使用现有的 nums 和 ops 进行计算直到遇到左边最近的一个左括号为止计算结果放到 nums数字 : 从当前位置开始继续往后取将整一个连续数字整体取出加入 nums/- : 需要将操作放入 ops 中。在放入之前先把栈内可以算的都算掉使用现有的 nums 和 ops 进行计算直到没有操作或者遇到左括号计算结果放到 nums 一些细节 由于第一个数可能是负数为了减少边界判断。一个小技巧是先往 nums 添加一个 0。为防止 () 内出现的首个字符为运算符将所有的空格去掉并将 (- 替换为 (0-( 替换为 (0。
代码
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;// 为了防止第一个数是负数在最前面补0nums.push(0);// 将所有空格去掉replace(s);// 存放所有操作符stackchar ops;for(int i0; is.size(); i) {char c s[i];if(c () ops.push(c);else if(c )){// 计算到最近一个左括号为止while(!ops.empty()) {char op ops.top();if(op ! () calc(nums, ops);else {ops.pop();break;}}}else {// 数字if(isdigit(c)) {int cur_num 0;int j i;// 将从 i 开始后面的连续数字整体取出加入numswhile(j s.size() isdigit(s[j])) {cur_num cur_num * 10 (s[j] - 0); }nums.push(cur_num);i j - 1;}// -else {if(i 0 (s[i-1] ( || s[i-1] || s[i-1] -)) {nums.push(0);}// 有新操作要入栈时把栈内可以算的算了while(!ops.empty() ops.top() ! () {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();nums.push(op ? ab : a-b); }
};参考资料
【进阶补充】双栈解决通用「表达式计算」问题
