题解 | #表达式求值#

c++ 双栈实现

定义两个栈一个操作数，一个操作符

优先级设定，+ - * /

比较当前操作符的栈顶和即将入栈的操作符优先级，若大于或等于则先进行一轮计算。

遇到括号时，因为前面已经计算过了则只需要最后一次计算

最后再进行一次计算即可

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * 
@param s string字符串 待计算的表达式
     * 
@return int整型
     */
    stack<long> num;
    stack<char> op;


    void val(){
        int res = 0;
        int num1 = num.top(); num.pop();
        int num2 = num.top(); num.pop();
        char c = op.top(); op.pop();
        if(c == '+') res = num1 + num2;
        if(c == '-') res = num2 - num1;
        if(c == '*') res = num1 * num2;
        if(c == '/') res = num2 / num1;
        num.push(res);
    }


    int solve(string s) {
        // write code here


        //优先级设定
        unordered_map<char, int> h {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};


        for(int i = 0; i < s.size(); i++){
            if(isdigit(s[i])){
                int x = 0;
                int j = i;
                while(j < s.size() && isdigit(s[j])){
                    x = x * 10 + s[j] - '0';
                    j++;
                }
                num.push(x);
                i = j - 1;
            }else if(s[i] == '('){
                //括号入栈
                op.push(s[i]);
            }else if(s[i] == ')'){
                //计算括号内部的
                while(op.top() != '('){
                    val();
                }
                op.pop();//左括号出栈
            }else{
                //当前栈顶的计算优先级大于等于即将入栈的优先级
                while(op.size() && h[op.top()] >= h[s[i]]){
                    val();
                }
                op.push(s[i]);
            }
        }
        while(op.size()){
            val();
        }
        return num.top();
    }
};