题解 | 表达式求值

#include <stack>
#include <string>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int priority(char a,char b){
        if(a=='+'||a=='-'){
            if(b=='*'||b=='(') return -1;
            else return 1;
        }
        if(a=='*'){
            if(b=='(') return -1;
            else return 1;
        }
        if(a=='('){
            if(b==')') return 0;
            else return -1;
        }
        return 1;
    }

    int calculate(int x,int y,char ch){
        if(ch=='+') return x+y;
        if(ch=='-') return x-y;
        if(ch=='*') return x*y;
        return 0;
    }

    int solve(string s) {
        int k,a,b;
        char c;
        stack<char> m;
        stack<int> n;
        for(int i=0;i<s.size();i++){
            if(s[i]>='0'&&s[i]<='9'&&(i==0||!(s[i-1]>='0'&&s[i-1]<='9'))) k=i;
            else if(!(s[i]>='0'&&s[i]<='9')&&(s[i-1]>='0'&&s[i-1]<='9')){
                a=stoi(s.substr(k,i-k));
                n.push(a);
            }
            if(!(s[i]>='0'&&s[i]<='9')){
                if(m.empty()||priority(m.top(),s[i])==-1) m.push(s[i]);
                else if(priority(m.top(),s[i])==0) m.pop();
                else{
                    while(!m.empty()&& priority(m.top(),s[i])==1){
                        c=m.top();
                        m.pop();
                        b=n.top();
                        n.pop();
                        a=n.top();
                        n.pop();
                        n.push(calculate(a,b,c));
                    }
                    if(m.empty()||priority(m.top(),s[i])==-1) m.push(s[i]);
                    else m.pop();
                }
            }
        }
        if(s.back()>='0'&&s.back()<='9') n.push(stoi(s.substr(k)));      //注意处理最后字符为数字的情况
        while(!m.empty()){
            c=m.top();
            m.pop();
            b=n.top();
            n.pop();
            a=n.top();
            n.pop();
            n.push(calculate(a,b,c));
        }
        return n.top();
    }
};