题解 | #表达式求值#

递归下降

1. 如果字符串是数字，直接返回数字
2. 如果字符串是括号表达式，则递归求解括号里面的值
3. 找到字符串中的操作符，如果遇到乘除，先用ret存起来 递归下降需要 先把加减抠出来，然后递归求解左右两部分，只有这样才能保证先算乘除法
4. 递归求解决剩余部分

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    string str;
    bool isNum(int l, int r)
    {
        for (int i = l; i <= r; i++) 
            if ('0' > str[i] || str[i] > '9') return false;
        return true;
    }
    int getNum(int l, int r)
    {
        int res = 0;
        for (int i = l; i <= r; i ++) res = res * 10 + (str[i] - '0');
        return res;
    }
    bool isSub(int l, int r)
    {
        if (str[l] != '(' || str[r] != ')') return false;
        int cnt = 0;
        for (int i = l; i < r; i ++)
        {
            if (str[i] =='(') cnt++;
            if (str[i] == ')') cnt--;
            if (cnt == 0) return false;
        }
        return true;
    }
    int get(int l, int r)
    {
        int ret = -1;
        int cnt = 0;
        for (int i = r; i >= l; i --)
        {
            if (str[i] == '(') cnt++;
            if (str[i] == ')') cnt--;
            if (cnt != 0) continue;
            if (str[i] == '+' || str[i] == '-') return i;
            if (ret == -1 &&(str[i] == '*' || str[i] == '/')) ret = i;
        }
        return ret;
    }
    int cal(int l, int r)
    {
        if (l > r) return 0;
        if (isNum(l, r)) return getNum(l, r);
        if (isSub(l, r)) return cal(l + 1, r - 1);
        int mid = get(l, r);
        if (str[mid] == '+') return cal(l, mid - 1) + cal(mid + 1, r);
        if (str[mid] == '-') return cal(l, mid - 1) - cal(mid + 1, r);
        if (str[mid] == '*') return cal(l, mid - 1) * cal(mid + 1, r);
        if (str[mid] == '/') return cal(l, mid - 1) / cal(mid + 1, r);
        return 0;
    }
    int solve(string s) {
        str = s;
        return cal(0, s.size() - 1);
        
        // write code here
    }
};