Leetcode刷题笔记题解(C++):224. 基本计算器

发布时间:2023年12月17日

思路:

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 here
        return 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};
    }
};

文章来源:https://blog.csdn.net/qq_27524749/article/details/135052154
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。