题解 | #表达式求值# 将中缀表达式转后缀表达式后求值

1. 将中缀表达式转后缀表达式。使用一个操作符栈，从左到右扫描。

• 如果是数字，记录并继续扫描，直到碰到操作符，将当前记录的数字字符串加入到后缀表达式。
• 如果是( ，加入操作符栈;
• 如果是 )，则操作符栈顶出栈并加入后缀表达式，直至遇到(；并弹出(。
• 如果是其他运算符，则把操作符栈中优先级不低于它的操作符都出栈并加入后缀表达式，然后将该操作符加入操作符栈。

2. 根据后缀表达式求值。扫描后缀表达式，使用一个操作数栈暂存操作数。

• 如果是操作数，则加入操作数栈。
• 如果是操作符，则从栈中连续弹出两个数num2、num1进行运算；并将运算结果加入栈中。
• 扫描完成，返回栈顶的数即为结果。

typedef int (*func)(int,int);
int add(int a, int b){
        return a + b;
    }
    
int sub(int a, int b){
    return a - b;
}

int mul(int a, int b){
    return a * b;
}

int dvd(int a, int b){
    return a / b;
}

class Solution {
public:
    map<char, int> op_priority = {{')', 1 }, {'*', 2}, {'/', 2}, {'+', 3}, {'-', 3}};
    stack<char> ops;
    map<char, func> func_table = {{'+',add}, {'-',sub}, {'*',mul}, {'/',dvd}};

    vector<string> infix2suffix(string s){
        vector<string> suffix;
        string num_str;
        for(size_t i = 0; i < s.size(); i++){
            if(s[i] == ' ') continue;
            if(isdigit(s[i])){
                num_str += s[i];
                if(i == s.size()-1){
                    suffix.push_back(num_str);
                }
            }else{
                if(num_str.size()>0){
                    suffix.push_back(num_str);
                    num_str.clear();
                }
                if(s[i] == '('){
                    ops.push(s[i]);
                }else if(s[i] == ')' ){
                    while(ops.top()!='('){
                        suffix.push_back(string(1, ops.top()));
                        ops.pop();
                    }
                    ops.pop();
                }else if(op_priority.find(s[i]) != op_priority.end()){
                    while(!ops.empty() && ops.top()!='(' && op_priority[ops.top()]<=op_priority[s[i]]){
                        suffix.push_back(string(1, ops.top()));
                        ops.pop();
                    }
                    ops.push(s[i]);
                }
            }        
        }
        
        while(!ops.empty()){
            suffix.push_back(string(1, ops.top()));
            ops.pop();
        }
        return suffix;
    }
    
    int compute(vector<string> suffix){
        stack<int> nums;
        for(auto str: suffix){
            if(op_priority.find(str[0])!=op_priority.end() && nums.size()>=2){
                int num2 = nums.top();
                nums.pop();
                int num1 = nums.top();
                nums.pop();
                nums.push(func_table[str.at(0)](num1, num2));
            }else{
                nums.push(atoi(str.c_str()));
            }
        }
        return nums.top();
        
    }
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        // write code here
        vector<string> suffix = infix2suffix(s);
        int res = compute(suffix);
        return res;
    }
};