题解 | #表达式求值#

表达式求值模板

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        // write code here
        int n = s.size();
        int i = 0;
        stack<char>op;
        stack<int> sk;
        unordered_map<char, int> f ;
        f['+'] = f['-'] = 1;
        f['*'] = f['/'] = 2;
        while (i < n) {
            if (s[i] == ' ') {
                i++;
                continue;
            }
            if (s[i] == '(') {
                op.push(s[i++]);
            } else if (s[i] == ')') {
                while (op.size() && op.top() != '(' && f[op.top()] >= f[s[i]])
                    sk.push(todo(sk, op));
                if (op.top() == '(')
                    op.pop();
                i++;
            } else if (s[i] >= '0' && s[i] <= '9') {
                int val = eat(s, i);
                sk.push(val);
            } else {
                if (i == 0) sk.push(0);
                while (op.size() && op.top() != '(' && f[op.top()] >= f[s[i]])
                    sk.push(todo(sk, op));
                op.push(s[i++]);
            }
        }
        while (op.size())
            sk.push(todo(sk, op));
        return sk.top();
    }
    int todo(stack<int>& sk, stack<char>& op) {
        int a = sk.top();
        sk.pop();
        int b = sk.top();
        sk.pop();
        char p = op.top();
        op.pop();
        printf("%d %c %d\n", b, p, a);
        switch (p) {
            case '+':
                return b + a;
            case '-':
                return b - a;
            case '*':
                return b * a;
            case '/':
                return b / a;
            case '(': {
                    puts("error");
                }
        }
        return -1;
    }
    int eat(string& s, int& i) {
        int val = 0;
        while (s[i] >= '0' && s[i] <= '9') {
            val = val * 10 + (s[i++] - '0');
        }
        return val;
    }
};

#ifdef debug


int main() {
    cout << " * " << endl;
    Solution k;
    auto arr = {1, 2, 3, 3, 5};
    cout << "result:  " << k.solve("3+2*3*4-1") << endl;
    return 0;
}


#endif