rt,Subtask 0全对,Subtask 1错了,原因是那个乘方的顺序,但是我已经完全不知道该怎么调了qwq,求大佬看看
#include<bits/stdc++.h>
using namespace std;
int n,x,flag=0,lch[100000],rch[100000],kkk[10000],rett[10000];
char a[100000],s[100000];
int dfs(int left,int right){
flag++;
int u=flag;
// cout<<left<<" "<<right<<endl;
if(left==right){
// cout<<"get leaf="<<a[left]<<"\n";
// system("pause");
s[u]=a[left];
lch[u]=0;
rch[u]=0;
return u;
}
int place1=-1,place2=-1,place3=-1,p=0;
for(int i=left;i<=right;i++){
if(a[i]=='(')p++;
if(a[i]==')')p--;
if(p>0)continue;
if(a[i]=='+'||a[i]=='-')place1=i;
if(a[i]=='*'||a[i]=='/')place2=i;
if(a[i]=='^')place3=i;
}
if(place1==-1){
if(place2==-1){
if(place3==-1){
// cout<<"delete ()\n";
// system("pause");
return dfs(left+1,right-1);
}
else{
place1=place3;
place2=place3;
}
}
else{
place1=place2;
}
}
// cout<<"L="<<left<<" R="<<right<<" ";
// cout<<place1<<endl;system("pause");
s[u]=a[place1];
lch[u]=dfs(left,place1-1);
rch[u]=dfs(place1+1,right);
return u;
}
void tree(int k){
if(kkk[k])
cout<<rett[k]<<" ";
else {
if(lch[k]!=0)tree(lch[k]);
if(rch[k]!=0)tree(rch[k]);
cout<<s[k]<<" ";
}
}
int Count(int x){
int ret1,ret2,ret;
if(lch[x]==0&&rch[x]==0)return s[x]-'0';
ret1=Count(lch[x]);
ret2=Count(rch[x]);
if(s[x]=='+'){
ret=ret1+ret2;
rett[x]=ret;
kkk[x]=1;
tree(1);
cout<<endl;
}
if(s[x]=='-'){
ret=ret1-ret2;
rett[x]=ret;
kkk[x]=1;
tree(1);
cout<<endl;
}
if(s[x]=='*'){
ret=ret1*ret2;
rett[x]=ret;
kkk[x]=1;
tree(1);
cout<<endl;
}
if(s[x]=='/'){
ret=ret1/ret2;
rett[x]=ret;
kkk[x]=1;
tree(1);
cout<<endl;
}
if(s[x]=='^'){
ret=pow(ret1,ret2);
rett[x]=ret;
kkk[x]=1;
tree(1);
cout<<endl;
}
return ret;
}
int main(){
cin>>a;
dfs(0,strlen(a)-1);
tree(1);
cout<<endl;
Count(1);
return 0;
}