题解 | #表达式求值#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    //give operators the priority of '><=',1='>',2='<',3='='
    int table[7][7]={1,1,2,2,2,1,1,1,1,2,2,2,1,1,1,1,1,1,2,1,1,1,1,1,1,2,1,1,2,2,2,2,2,3,3,1,1,1,1,3,1,1,2,2,2,2,2,3,3}; 
    //string to int
    int toint(string s) {
        int x = 0;
        if (s[0] != '-') x = s[0] - '0';
        for (int i = 1; i < s.size(); i++) {
            x *= 10;
            x += s[i] - '0';
        }
        if (s[0] == '-') x = -x;
        return x;
    }
    //mach +-*/()# with 0123456 in the table
    int give(char c){
        if(c=='+') return 0;
        else if(c=='-') return 1;
        else if(c=='*') return 2;
        else if(c=='/') return 3;
        else if(c=='(') return 4;
        else if(c==')') return 5;
        else return 6;
    }
    //compute 
    int compute(int a, int o, int b){
        if(o==0) return a+b;
        else if(o==1) return a-b;
        else if(o==2) return a*b;
        else return a/b;
    }

    int solve(string s) {
        // write code here
        s.push_back('#');
        string num;
        stack<int> nums;
        stack<char> op;
        op.push('#');
        int t1=-1,t2=-1;
        for (int i = 0; i < s.size(); i++) {
            //nums
            if((s[i]=='-'&&(i==0||s[i-1]=='('))||(s[i]<='9'&&s[i]>='0')){
                num.push_back(s[i]);
            }
            //op
            else{
                if(num!="") nums.push(toint(num));
                num="";
                t1=give(op.top());
                t2=give(s[i]);
                int flag=table[t1][t2];
                //case'=' 查询到括号或者完结符#，把上一个（退栈
                if(flag==3){
                    op.pop();
                }
                //case'<' 旧操作符优先度小于新操作符，保留旧操作符并让新符入栈
                else if(flag==2){
                    op.push(s[i]);
                }
                //case'>' 计算上一个操作符，并使当前s[i]维持到下一轮
                else{
                    int b=nums.top();
                    nums.pop();
                    int a=nums.top();
                    nums.pop();
                    int o=give(op.top());
                    op.pop();
                    nums.push(compute(a,o,b));
                    i--;
                }
            }
        }
        return nums.top();
    }
};