已经确定了运算顺序没问题,为什么样例过不了?
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e3+10;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int n , deep , a[N][2];
char c[N];
string s, t;
int _pow(int a,int b){
int res = 1;
while(b){
if(b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
int calculate(int l,int r){
int w = 0,pos = -1,minn = INF;
for(int i = l; i <= r; i++){
if(s[i] >= '0' && s[i] <= '9') w = w * 10 + s[i] - '0';
else if(a[i][1] <= minn) pos = i,minn = a[i][1];
}
if(pos == -1) return w % mod;
if(c[a[pos][0]] == '1') {
for(int i = l; i <= r; i++){
if((s[i] == '+' || s[i] == '*' || s[i] == '^') && a[i][1] == minn && a[i][0] == a[pos][0]){
pos = i;
break;
}
}
}
int resl = calculate(l,pos-1),resr = calculate(pos+1,r);
if(s[pos] == '+') return (resl + resr) % mod;
if(s[pos] == '*') return (resl * resr) % mod;
if(s[pos] == '^') return _pow(resl,resr) % mod;
}
signed main(){
scanf("%lld%s",&n,c+1);
cin >> s;
int w = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] >= '0' && s[i] <= '9') w = w * 10 + s[i] - '0';
else if(s[i] == '.') {
if(w==0)goto err;
t += to_string(w),w = 0;
}
else if(s[i] == '+' || s[i] == '*' || s[i] == '^') {
if(w == 0) goto err;
t += s[i], a[t.size()-1][0] = w, a[t.size()-1][1] = w + deep,w = 0;
}
else if(s[i] == '(') deep++;
else if(s[i] == ')') deep--;
else goto err;
if(deep < 0) goto err;
}
if(deep != 0) goto err;
s=t;
printf("%lld",calculate(0,s.size()-1));
return 0;
err:
puts("error");
return 0;
}