题目:
输入一个(中缀)表达式,请输出它的值。
输入格式 一行一个字符串 s 表示表达式,表达式由 +,-,*,(,) 以及数字构成。数据保证输入的表达式合法(不会出现被 0 除等情况),并且表达式中出现的任意数字 x 满足 1≤x≤10000 。
输出格式 一行一个值表示答案。由于答案可能很大,请输出答案 mod 1e9+7 (如果答案为负数要加上 1e9+7 , 即答案为 0 到 1e9+6 之间的数)。
样例输入 3+(10-5)*2
样例输出 13
数据范围 对于 100% 的数据,保证 1≤|s|≤1000 。
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
using namespace std;
typedef long long ll;
typedef double db;
const ll MOD=1e9+7;
const int N=1e4+23;
string str;
int c1[N],c2[N],c3[N],l1[N],l2[N];
inline ll dfs(int l,int r)
{
if(str[l]=='('&&str[r]==')') return dfs(l+1,r-1);
if(l1[r]>l){if(str[l1[r]]=='+') return 1ll*dfs(l,l1[r]-1)+dfs(l1[r]+1,r)%MOD;
else return 1ll*(dfs(l,l1[r]-1)-dfs(l1[r]+1,r)+MOD)%MOD;}
else if(l2[r]>l) return 1ll*dfs(l,l2[r]-1)*dfs(l2[r]+1,r)%MOD;
else{ll num=0;rep(i,l,r) num=num*10+str[i]-'0';return num%MOD;}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>str;
int lp=1;
memset(c1,-1,sizeof(c1));memset(c2,-1,sizeof(c1));memset(c3,-1,sizeof(c1));
rep(i,0,str.size()-1)
{
if(str[i]=='(') lp++;
if(str[i]==')') lp--;
if(str[i]=='+'||str[i]=='-') c1[lp]=i;
if(str[i]=='*') c2[lp]=i;
l1[i]=c1[lp];l2[i]=c2[lp];
}
cout<<dfs(0,str.size()-1);
}
30pts 哪错了?