NC241 计算器(二)

class Solution {
public:
    int calculate(string s) {
        //为了方便处理最后一个数字，在s串的后面加一个结束的标志符
        s+='#';
        //创建两个栈：存数值，存运算符
        stack<int>num;
        stack<char>op;
        //temp存数字，flag用来标记优先级，如果是*/就标记flag=1，表示优先计算
        int temp=0;
        bool flag=false;
        for(int i=0;i<s.length();i++){
            //如果是数字
            if(s[i]>='0'&&s[i]<='9'){
                temp=temp*10+s[i]-'0';
            }else{
                //否则就是运算符
                num.push(temp);
                temp=0;
                //由于*/的优先级比+-高，所以优先处理*/
                if(flag==1){
                    int a=num.top();
                    num.pop();
                    int b=num.top();
                    num.pop();
                    char c=op.top();
                    op.pop();
                    if(c=='*') num.push(a*b);
                    else if(c=='/') num.push(b/a);
                    flag=0;
                }
                //否则如果是+-#,就表明要进行出栈运算（*/+-）
                if(s[i]=='+'||s[i]=='-'||s[i]=='#'){
                     while(!op.empty()){
                        int num1=num.top();
                        num.pop();
                        int num2=num.top();
                        num.pop();
                        char n=op.top();
                        op.pop();
                        if(n=='+') num.push(num1+num2);
                        else if(n=='-') num.push(num2-num1);
                        else if(n=='*') num.push(num1*num2);
                        else if(n=='/') num.push(num2/num1);                        
                     }
                }
                //否则如果是*/，就标记flag=1,表示之后会进行优先运算
                else{
                     flag=1;
                }
                //将运算符加入op中
                 op.push(s[i]);
               
            }
        }
        return num.top();
    }
};