题解 | #表达式求值#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    char c;
    int pos = 0;
    stack<char> C;
    stack<int> I;
    bool getc(string s) {
        if (pos < s.size()) {
            c = s[pos++];
            return 1;
        } else
            return 0;
    }
    void cal() {
        char op = C.top();
        C.pop();
        int n2 = I.top();
        I.pop();
        int n1 = I.top();
        I.pop();
        int val;
        switch (op) {
            case '+':
                val = n1 + n2;
                break;
            case '-':
                val = n1 - n2;
                break;
            case '*':
                val = n1 * n2;
                break;
            case '/':
                val = n1 / n2;
                break;
        }
        I.push(val);
    }
    void E(string s) {
        T(s);
        while (c == '+' || c == '-') {
            C.push(c);
            getc(s);
            T(s);
            cal();
        }
        return;
    }
    void T(string s) {  //
        F(s);
        while (c == '*' || c == '/') {
            C.push(c);
            getc(s);
            F(s);
            cal();
        }
        return;
    }
    void F(string s) {
        if (c == '(') {
            getc(s);
            E(s);
            getc(s);
            return;
        }
        //此处必然是数字
        int val = 0;
        while (c >= '0' && c <= '9') {
            val = val * 10 + (c - '0');
            if (!getc(s))
                break;
        }
        I.push(val);
    }
    int solve(string s) {
        // write code here
        if (!getc(s))
            return 0;
        E(s);
        return I.top();
    }
};

编译技术中自顶向下递归子程序法来解，懂得编译原理的牛牛们一定不陌生。

由于不需要考虑语法错误，逻辑性上就可以简化部分。

虽然调用的函数块过多，但逻辑是极为清晰的。

函数分为solve、E（多项式）、T（加减数）、F（因子）

E函数用于处理各个项之间的加减运算，

T用来处理乘除法，

F用来处理具体因子或者括号。