题解 | 表达式求值

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        // write code here
        //首先中缀表达式转后缀表达式
        stack<char> st1;//用来转化为后缀表达式的栈
        string hzh = "";//用来存放后缀表达式的变量
        for(int i = 0; i < s.length(); i++){
            char c = s.at(i);
            if(c == '('){//'('直接压入栈
                //分隔数字
                if(!hzh.empty() && hzh.back() >= '0' && hzh.back() <= '9'){
                    hzh.push_back('#');
                }
                st1.push(c);
            }
            else if(c == ')'){//是')'则弹出栈内所有操作符并加入后缀表达式直到弹出'('(弹出)为止              //分隔数字
                if(!hzh.empty() && hzh.back() >= '0' && hzh.back() <= '9'){
                    hzh.push_back('#');
                }
                while(!st1.empty()){
                    char tmp = st1.top();
                    st1.pop();
                    if(tmp == '('){
                        break;
                    }
                    else{
                        hzh.push_back(tmp);
                    }
                }
            }
            else if(c == '*'){//是'*'则直接入栈
                //分隔数字
                if(!hzh.empty() && hzh.back() >= '0' && hzh.back() <= '9'){
                    hzh.push_back('#');
                }
                st1.push(c);
            }
            else if(c == '+' || c == '-'){//是加减号则弹出所有运算符直到'('(不弹出)为止              //分隔数字
                if(!hzh.empty() && hzh.back() >= '0' && hzh.back() <= '9'){
                    hzh.push_back('#');
                }
                while(!st1.empty()){
                   char tmp = st1.top();
                   if(tmp == '('){
                     break;
                   }
                   else{
                     hzh.push_back(tmp);
                   }
                   st1.pop();
                } 
                st1.push(c);
            }
            else{
                hzh.push_back(s.at(i));
            }
        }
        while(!st1.empty()){
            char c = st1.top();
            if(!hzh.empty() && hzh.back() >= '0' && hzh.back() <= '9'){
                    hzh.push_back('#');
                }
            hzh.push_back(c);
            st1.pop();
        }
        
        //后缀表达式求值
        stack<int> st2;
        string tmp = "";//存储提取的单个操作数
        for(int i = 0; i < hzh.length(); i++){
           char c = hzh.at(i);
           if(c == '#'){//压入操作数，重置tmp
              int tmp_i = stoi(tmp);
              st2.push(tmp_i);
              tmp = "";
           }
           else if(c == '+'){
            int y = st2.top();
            st2.pop();
            int x = st2.top();
            st2.pop();
            int r = x + y;
            st2.push(r);
           }
           else if(c == '-'){
            int y = st2.top();
            st2.pop();
            int x = st2.top();
            st2.pop();
            int r = x - y;
            st2.push(r);
           }
           else if(c == '*'){
            int y = st2.top();
            st2.pop();
            int x = st2.top();
            st2.pop();
            int r = x * y;
            st2.push(r);
           }
           else{
            tmp.push_back(c);
           }
        }
        //栈顶存放即为答案
        return st2.top();
    }
};