class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
	 
	 /*
	 本题思路:将中缀式转化为后缀表达式然后计算
	 使用调度站算法(用于转换表达式)和栈的基础使用
	 两个栈一个char用来转换表达式 一个int用来计算结果
	 第一部分思路为 发现数字就进入新字符串 发现左括号就入栈 其他运算符 空栈的时候直接入栈 
	 有top时 就与top比较 如果它比较级比top高就入栈(先运算) 低的话就让比它高的出栈
	 */
	 
     int IsDiaodu(char c){//调度站算法的基础 用来比较优先级
            if(c=='-'||c=='+'){return 1;}
            else if(c=='*'){return 2;}
            return -1;
        }
    int solve(string s) {
        string str={};
        stack<char>st;//用来将中缀式转化为计算机易懂的后缀式
        stack<int>st2;//用来计算后缀式(逆波兰表达式)
        int m=0;//初始化数字m 将多位数转入后缀时仍然是多位数而不是多个个位数
        for(int i=0;i<s.size();){
            if((isdigit(s[i]))){//判断是否为数字
                while(i < s.size()&&isdigit(s[i])){//循环用于将多位数转换分割到同一部分
                    str+=s[i];
                    i++;
                }
                str+='#';
            }
            else if(s[i]=='('){st.push(s[i]);i++;}//只要是左括号就直接入栈
            else if(s[i]==')'){
                while(st.top()!='('){
                    str+=st.top();
                    st.pop();
                }
                st.pop();
                i++;
            }
            else{//使用while循环可以拿尽符合条件的 if只能判断一次
                while(!st.empty()&&IsDiaodu(s[i])<=IsDiaodu(st.top())){//因为后面会pop删除元素所以要判断非空栈 ，如果当前运算符优先级小于栈顶优先级 就把栈顶的拿出来先放过去
                    str+=st.top();
                    st.pop();
                }
                st.push(s[i]);//没比它大的了就把它放进栈
                i++;
            }
        }
		//最后把栈内的全拿出来
        while(!st.empty()){
            str+=st.top();
            st.pop();
        }
		//-----------接下来是计算逆表达式------------
        for(int i=0;i<str.size();i++){//这里是把数字的数值真实地反馈出来 
            if(str[i]!='+'&&str[i]!='-'&&str[i]!='*'&&str[i]!='#'){
                m=(str[i]-'0')+m*10;
            }
			//发现间隔就把这个m放进去
            else if(str[i]=='#'){
                st2.push(m);
                m=0;}
			//只有数字入栈 发现运算符就取出top1和top2进行计算
            else{
                int top1=st2.top();
                st2.pop();
                int top2=st2.top();
                st2.pop();
                if(str[i]=='+'){st2.push(top1+top2);}
                else if(str[i]=='-'){st2.push(top2-top1);}
                else{
                    st2.push(top1*top2);
                }

            }
        }
        int top_last=st2.top();
        return top_last;


    }
  
  

};

//本人为初学者 代码为经许久调试所成版本 有很多需要改进的地方 初衷为整理思路 思路问题部分望大佬指导