题解 | #表达式求值#

复习栈解决表达式求值，注意表达式的优先级，注意引用！不用引用的话参数无法改变

#include <stack>
#include <map>
#define ADD 0
#define SUB 1
#define MUL 2
#define LEFTP 3
#define RIGHTP 4
#define NUM 5
#define ADD_CHAR '+'
#define SUB_CHAR '-'
#define MUL_CHAR '*'
#define LEFT_CHAR '('
#define RIGHT_CHAR ')'
const int pri[NUM][NUM] = {1, 1, 0, 0, 1, 
                          1, 1, 0, 0, 1, 
                          1, 1, 1, 0, 1, 
                          0, 0, 0, 0, 2, 
                          -1, -1, -1, -1, -1};

void compute(stack<char>& op_stack, stack<int>& num_stack){
    char op = op_stack.top();
    op_stack.pop();
    int num1 = num_stack.top();
    num_stack.pop();
    int num2  = num_stack.top();
    num_stack.pop();
    int res;
    if(op == ADD_CHAR)
        res = num1 + num2;
    else if(op == SUB_CHAR)
        res = num2 - num1;
    else
        res = num1 * num2;
    num_stack.push(res);
}
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        // write code here
        map<char, int> m;
        m['+'] = ADD;
        m['-'] = SUB;
        m['*'] = MUL;
        m['('] = LEFTP;
        m[')'] = RIGHTP;
        s = s + ")";
        stack<char> op_stack;
        stack<int> num_stack;
        op_stack.push(LEFT_CHAR);
        int i = 0;
        while(i < s.size()){
            char c = s[i];
            if(c >= '0' and c <= '9'){
                // 读取数字直到遇到操作符
                int res = 0;
                while(i < s.size() and s[i] >= '0' and s[i] <= '9'){
                    res = res * 10 + (s[i] - '0');
                    i++;
                }
                num_stack.push(res);
            }
            char last = op_stack.top();
            char now = s[i];
            int last_id = m[last];
            int now_id = m[now];
            if(pri[last_id][now_id] == 1){
                compute(op_stack, num_stack);
            }
            else if(pri[last_id][now_id] == 0){
                op_stack.push(now);
                i++;
            }else{
                op_stack.pop();
                i++;
            }
        }
        return num_stack.top();
        
    }
};