class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
  
  //本题答案完全来自牛客er“子夜降晴空”，我只是做出一些自己的解释，如有侵权请联系删除！
  
  /*对于该问题，可以使用递归的思路，我们知道一个简单的计算器是很容易实现的，
  只需要将所有的数按优先级进行加减即可，本题的难点在于对括号的处理。
  
  因为简单的计算器容易实现，我们就可以做出联想，是否有办法将复杂的括号优先级转化为
  简单的计算呢？这就是递归可以做的事情，将括号问题拆解为数个简单计算。
  
  具体的思路如下：
  一、先设置一个栈，后续需要简单运算的数据都存入栈中
  
  二、将问题拆解为简单运算，这里使用if判断，如果遇到左括号说明已经需要进入
  拆解步骤，使用递归对本函数进行调用，遇到左括号进行一层递归，遇到右括号则退出一层递归
  
  三、完善简单计算器，将计算结果返回*/
  
    int solve(string s) {
        // write code here
        stack<int> sum;
        int ret{};//最后返回的结果，跟递归无关
        char sign='+';//计算的前一个符号
	  
	  /*简单计算器的难点：例如“2+1*5”，我们在获取到加号的时候，其实是不知道下一个加数是多少的
	  ，因此计算就进行不下去。要解决这个问题，我们可以把原式看成“0+2+1*5”，也就是在前面添加一个0.这样就能把符号往前推一位，在遇到2+某个数的时候，先把0+2计算出来；在遇到1*5的时候，先把1入栈，此时符号更新为乘号，最后
	  再利用top（）函数乘上5，这样就能解决我们看不到参与运算的下一个数的问题*/
        int num{};//对字符串的数字进行记录

        for(int i=0;i<s.size();i++)//遍历字符串
        {
            if(s[i]>='0'&&s[i]<='9')
            {
                num=num*10+s[i]-'0';//将字符数字转化为整数
            }
            
            if(s[i]=='(')//遇到左括号，准备进入递归
            {
                int left=i++;//定位左括号的位置
                int cnt=1;//左括号的数量加一，可以理解为递归层数
                while(cnt>0)//对左括号进行配对，找到与之对应的右括号，对中间的括号进行忽略
                {
                    if(s[i]=='(')
                    {
                        cnt++;
                    }
                    else if(s[i]==')')
                    {
                        cnt--;
                    }
                    i++;//每次循环都会i++，这是为了定位右括号的位置
                } 

                num=solve(s.substr(left+1,i-2-left));//递归调用自身，将括号内的数据进行调用
                i--;//i--是为了消除循环后多的那一次i++
            }

            if(i==s.size()-1||s[i]=='+'||s[i]=='-'||s[i]=='*')//判断是否遇到运算符或即将运算结束
            {
                if(sign=='+')//这里的sign是前一个符号，理解了这一点下面都能看懂
                {
                    sum.push(num);
                } 
                else if(sign=='-')
                {
                    sum.push(-num);//遇到减号就加上其相反数
                }
                else if(sign=='*')
                {
                    sum.top()*=num;//这里遇到乘号直接用栈顶数据乘num，不用入栈，这是优先级的体现
                }
                sign=s[i];//更新当前符号
                num=0;//重置num
            }
        }

        while(!sum.empty())//对栈内数据进行累加并返回结果
        {
            ret+=sum.top();
            sum.pop();
        } 
        
        return ret;
    }
};