表达式解析[笛卡尔树]

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=35,MOD=10007;
typedef long long ll;
int n;
char s[N];
struct node{
    int lc,rc;
    char op;
    ll num;
    node():lc(0),rc(0),num(0){}
}t[N];
int w[N],root,cnt=0;
void build(){
    int p=0;
    for(int i=1;i<=n;i++){//printf("i %d %c\n",i,s[i]);
        if(s[i]==‘(‘) {p++;continue;} 
        if(s[i]==‘)‘) {p--;continue;} 
        
        if(s[i]==‘+‘|| (s[i]==‘-‘&&i!=1&&s[i-1]!=‘(‘)  ) w[++cnt]=p*4+1,t[cnt].op=s[i];
        else if(s[i]==‘*‘||s[i]==‘/‘) w[++cnt]=p*4+2,t[cnt].op=s[i];
        else if(s[i]==‘^‘) w[++cnt]=p*4+3,t[cnt].op=s[i];
        else{
            if(s[i]==‘-‘){//cout<<"p";
                w[++cnt]=p*4+4;
                t[cnt].op=‘a‘;t[cnt].num=0;
                w[++cnt]=p*4+1,t[cnt].op=‘-‘;
                if(s[i+1]<‘0‘||s[i+1]>‘9‘) continue;
                i++;
            }
            //printf("num %d %c\n",i,s[i]);
            
            w[++cnt]=p*4+4;
            ll x=0;
            while(s[i]>=‘0‘&&s[i]<=‘9‘) x=x*10+s[i]-‘0‘,i++;
            i--;
            t[cnt].num=x; t[cnt].op=‘a‘;
        }
        
    //printf("build %d %d %c  %d\n",cnt,w[cnt],t[cnt].op,t[cnt].num);
    }
    
    int st[N],top=0;
    for(int i=1;i<=cnt;i++){
        int k=top;
        while(k>0&&w[st[k]]>=w[i]) k--;
        if(k) t[st[k]].rc=i;
        if(k<top) t[i].lc=st[k+1];
        st[++k]=i;
        top=k;//printf("st %d %c %d\n",top,t[st[top]].op,w[st[top]]);
    }
    root=st[1];
}
inline ll fpow(ll a,ll b){
    ll ans=1;
    for(;b;b>>=1,a*=a)
        if(b&1) ans*=a;
    return ans;
}
ll cal(int u){
    char c=t[u].op;
    if(c==‘a‘) return t[u].num;
    
    ll t1=cal(t[u].lc),t2=cal(t[u].rc);//printf("cal %d  %d %c %d\n",u,t1,c,t2);
    if(c==‘+‘) return t1+t2;
    if(c==‘-‘) return t1-t2;
    if(c==‘*‘) return t1*t2;
    if(c==‘/‘) return t1/t2;
    if(c==‘^‘) return fpow(t1,t2);
}
int main(){
    scanf("%s",s+1); n=strlen(s+1);
    build();
    printf("%lld",cal(root));
}