本文主要是介绍Leetcode刷题笔记题解(C++):224. 基本计算器,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
思路:
step 1:使用栈辅助处理优先级,默认符号为加号。
step 2:遍历字符串,遇到数字,则将连续的数字字符部分转化为int型数字。
step 3:遇到左括号,则将括号后的部分送入递归,处理子问题;遇到右括号代表已经到了这个子问题的结尾,结束继续遍历字符串,将子问题的加法部分相加为一个数字,返回。
step 4:当遇到符号的时候如果是+,得到的数字正常入栈,如果是-,则将其相反数入栈,如果是*,则将栈中内容弹出与后一个元素相乘再入栈。
step 5:最后将栈中剩余的所有元素,进行一次全部相加。
#include <stack>
#include <vector>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** 返回表达式的值* @param s string字符串 待计算的表达式* @return int整型*/int calculate(string s) {// write code herereturn function(s, 0)[0];}vector<int> function(string s,int index){stack<int>sk;long long num = 0;char op = '+';int i;for(i = index;i<s.size();i++){if(s[i]==' ') continue;//如果当前为数字else if(s[i]>='0'&&s[i]<='9'){num = num*10+s[i]-'0';//防止连续的数字if(i!=s.length()-1&&s[i+1]!=' ') continue;//如果为数字不执行下面的语句继续遍历,并且下一个字符不为空格}else if(s[i]=='('){//遇到左括号,从左括号开始第一个进行递归,并且下一个字符不为空格vector<int> res = function(s, i+1);num = res[0];//计算出括号中的计算值i = res[1];//得出遍历的下标位置if(i!=s.length()-1&&s[i+1]!=' ') continue;//如果还没结束字符串则继续遍历}switch (op) {case '+':sk.push(num);break;case '-':sk.push(0-num);break;case '*':int temp = sk.top();sk.pop();sk.push(temp*num);break;}num = 0;if(s[i] == ')') break;//遇到右括号则递归结束else op = s[i];}int sum = 0;//计算栈中的所有值的和while (!sk.empty()) {sum += sk.top();sk.pop();}return vector<int> {sum,i};}
};
这篇关于Leetcode刷题笔记题解(C++):224. 基本计算器的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!