表达式计算4（递归分治重点题型）

注意要多写

#include <bits/stdc++.h>
using namespace std;
string s;

int zhuan(int l, int r){
    int num = 0;
    for(int i = l; i <= r; i++){
        num = num * 10 + s[i] - '0';
    }
    return num;
}

int calu(int l, int r){
    int cnt = 0;
    int pos1 = -1, pos2 = -1, pos3 = -1;
    for(int i = l; i <= r; i++){
        if(s[i] == '(') cnt++;
        if(s[i] == ')') cnt--;
        if(cnt == 0){
            if(s[i] == '+' || s[i] == '-') pos1 = i;
            if(s[i] == '*' || s[i] == '/') pos2 = i;
            if(s[i] == '^') pos3 = i;
        }
    }
//    printf("{%d %d %d}", pos1, pos2, pos3); 
    if(pos1 == -1 && pos2 == -1 && pos3 == -1){
        if(cnt == 0 && s[l] == '(') return calu(l + 1, r - 1);
        if(cnt > 0 && s[l] == '(') return calu(l + 1, r);
        if(cnt < 0 && s[r] == ')') return calu(l, r - 1);
        return zhuan(l, r);
    }
    if(pos1 != -1){
        if(s[pos1] == '+') return calu(l, pos1 - 1) + calu(pos1 + 1, r);
        else return calu(l, pos1 - 1) - calu(pos1 + 1, r);
    }
    else if(pos2 != -1){
        if(s[pos2] == '*') return calu(l, pos2 - 1) * calu(pos2 + 1, r);
        else return calu(l, pos2 - 1) / calu(pos2 + 1, r);
    }
    else{
        return pow(calu(l, pos3 - 1), calu(pos3 + 1, r));
    }
}

int main(){
    cin >> s;
    printf("%d", calu(0, s.length() - 1));
    return 0;
}