表达式求值求助
  • 板块学术版
  • 楼主da_ke
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/5/12 21:25
  • 上次更新2024/5/13 11:12:17
查看原帖
表达式求值求助
766675
da_ke楼主2024/5/12 21:25

题目:

输入一个(中缀)表达式,请输出它的值。

输入格式 一行一个字符串 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 哪错了?

2024/5/12 21:25
加载中...