题解 | #表达式求值#

中缀转后缀
对于普通中缀表达式的计算，我们可以将其转化为后缀表达式再进行计算。转换方法也十分简单。只要建立一个用于存放运算符的栈，扫描该中缀表达式：

（1）如果遇到数字，直接将该数字输出到后缀表达式（以下部分用「输出」表示输出到后缀表达式）；
（2）如果遇到左括号，入栈；
（3）如果遇到右括号，不断输出栈顶元素，直至遇到左括号（左括号出栈，但不输出）；
（4）如果遇到其他运算符，不断去除所有运算优先级大于等于当前运算符的运算符，输出。（5）最后，新的符号入栈；
（6）把栈中剩下的符号依次输出，表达式转换结束。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        // write code here
        unordered_map<string, int> opPriority;
        opPriority["*"] = 0;
        opPriority["+"] = 1;
        opPriority["-"] = 1;
        stack<string> stk; //操作符栈;
        vector<string> vec; //后缀表达式
        string digit;
        for(char ch:s){
            if(!(ch >= '0' && ch <= '9')){
                if(digit != ""){
                    vec.push_back(digit);
                    digit = "";
                }
            }
            if(ch >= '0' && ch <= '9') digit += ch;
            else if(ch == '('){
                string op = "";
                op += ch;
                stk.push(op);
            }else if(ch == ')'){
                while(!stk.empty() && stk.top() != "("){
                    vec.push_back(stk.top()); stk.pop();
                }
                stk.pop();
            }
            else{
                string op = "";
                op += ch;
                cout << op;
                while(!stk.empty() && stk.top() != "(" && opPriority[op] >= opPriority[stk.top()]){
                    vec.push_back(stk.top()); stk.pop();
                }
                stk.push(op);
            }
        }
        if(digit != "") vec.push_back(digit); //注意最后是数字需要加入后缀表达式

        while(!stk.empty()){
            vec.push_back(stk.top());
            stk.pop();
        }
        stack<int> resStk;
        for(int i = 0; i < vec.size(); i ++){
            if(vec[i] == "+"){
                int a = resStk.top(); resStk.pop();
                int b = resStk.top(); resStk.pop();
                resStk.push(a + b);
            }else if(vec[i] == "-"){
                int a = resStk.top(); resStk.pop();
                int b = resStk.top(); resStk.pop();
                resStk.push(b - a);
            }else if(vec[i] == "*"){
                int a = resStk.top(); resStk.pop();
                int b = resStk.top(); resStk.pop();
                resStk.push(b * a);
            }else resStk.push(stoi(vec[i]));
        }
        return resStk.top();
    }
};