题解 | #表达式计算4#

关于分治和递归的最最妙的应用题：表达式计算

using namespace std;
string s;
int getnum(int l , int  r){//这个函数的作用是当式子中只有数时将字符串表示转换成整型的数，第一次写的时候还没考虑到这个问题，当时只想到了当条件l == r 时，返回s[l] - '0'（不过当时甚至连-‘0’都没考虑）寄！！！
    int res = 0;
    for (int i = l ; i <= r ; i ++ ){
        res = res * 10 + s[i] - '0';
    }
    return res;
}
int fenzhi(int l , int  r){
    int pos1 = -1 , pos2 = -1 , pos3 = -1 ;//pos1,2,3分别记录最后面的加减，乘除和乘方的位置（前提是在任何一个括号的外面）
    int cnt = 0;//cnt表示括号配对情况，大于0表示左括号数大，小于0则相反，只有等于0的时候才表示当前配对完整
    if (l == r) return (s[l] - '0');//返回一个单位数
    for (int i = l ; i <= r ; i ++ ){        
        if (s[i] == '(') {
            cnt ++ ;
        }
        else if (s[i] == ')'){
            cnt -- ;
        }
        
        if (cnt == 0){//括号配对完整也即是在正常优先级的条件下去标记符号的位置
        if (s[i] == '*' || s[i] == '/'){
            pos2 = i;
        }
        else if (s[i] == '+' || s[i] == '-'){
            pos1 = i;
        }
        else if (s[i] == '^'){
            pos3 = i;
        }
      }
    }
    //这里开始是分治和递归的关键，最好是能在纸上先一一列举可能的情况，然后再筛选出判断条件的先后，这里其实也很细节，会影响到最后的判断条件
    if (cnt > 0 && s[l] == '('){//下面我都举例各种特殊情况：   ((((3)
        return fenzhi(l + 1, r);
    }
    else if (cnt < 0 && s[r] == ')'){//  (3)))))
        return fenzhi(l , r - 1);
    }
    else if (cnt == 0 && pos1 == -1 && pos2 == -1 && pos3 == -1){
        if (s[l] == '(' && s[r] == ')') return fenzhi(l + 1, r - 1);//   (1 + 2)
        else return getnum(l,r);//   12
    } 
    //这里把有符号位置的条件放在最后也是考虑到cnt在三种情况下的重复现象，提高代码的简洁性
      if (pos1 != -1){
            if (s[pos1] == '+') return fenzhi(l,pos1 - 1) + fenzhi(pos1 + 1 , r);
            else return fenzhi(l,pos1 - 1) - fenzhi(pos1 + 1 , r);//这里刚开始是复制粘贴过来的，所以有很多细微错误都没有发现，CtrlCV需要谨慎，寄！！！
        }
      else if (pos2 != -1){
            if (s[pos2] == '*') return fenzhi(l,pos2 - 1) * fenzhi(pos2 + 1 , r);
            else return fenzhi(l,pos2 - 1) / fenzhi(pos2 + 1 , r);
        }
      else if (pos3 != -1){
            return pow(fenzhi(l,pos3 - 1),fenzhi(pos3 + 1, r));
        }
    return 0;//这句话很重要，不然可能会报错，寄！！！！！！
}
int main(){
    cin>>s;
    cout<<fenzhi(0,s.length() - 1);
    return 0;
}

此题耗时良久，我悟出来递归和分治的不同情况最好在草稿纸上能列举列举，这样有利于思路的完整，继续打天下！