分治

题目描述：

给出一个表达式,其中运算符仅包含+,-,*,/,^（加 减 乘 整除 乘方）要求求出表达式的最终值

数据可能会出现括号情况，还有可能出现多余括号情况

数据可能会出现负数的情况

思路：

分治

通过运算符将整个表达式一次次分割来计算

根据优先度低的运算符来分割表达式，这样分治到最后进行数与数的计算的时候就算的是优先度最高的，也就是逆过来了

对于同样优先级的符号，我们取最后一个位置来分割

而且对于在括号里面的加减乘除乘方我们不用其来分割，待去气括号后再用其进行分割

所以，我们每次跑(l, r)的时候，用pos1来记录+或-的位置，用pos2来记录*或/的位置，用pos3来记录^的位置

记录好了以后就先判断特殊的情况，也就是pos1=pos2=pos3=-1，此时括号外面没有运算符，就可能出现两种情况，一是出现多余括号，二是正好最外面一层是括号。那我们就讨论一下，当cnt>0且s[l] = ‘(’,就去掉这个左括号，当cnt<0且s[r] = ')'就去掉这个有括号，当cnt = 0，且s[l] = '(',s[r] = ')'就去掉这两个括号，当cnt = 0，s[l] != '(', s[r] != ')'，就获得这个数。

如果没有上述特殊情况，就从加减再到乘除再到乘方去分割表达式

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline ll llRead(){ll x(0), t(1);char o (getchar());while (o < '0' || o > '9') {if (o == '-') {t = -1;}o = getchar();}for (; o >= '0' && o <= '9'; o = getchar()) {x = (x << 1) + (x << 3) + (o ^ 48);}return x * t;}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}
ll qpow(ll a,ll n){ll ans=1,base=a%mod;while(n){if(n&1)ans=(ans*base)%mod;base=(base*base)%mod;n>>=1;}return ans;}
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

string s;

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

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


int main(){
    cin>>s;
    cout<<calc(0, s.size() - 1)<<endl;
    return 0;
}