首页 > 代码库 > 混合表达式

混合表达式

2024-10-09 08:31:39   216人阅读

题目描述

技术分享

输入

仅一行，包含一个仅含有数字和加减号的字符串，表示一个混合表达式。
保证该表达式合法，即至少能计算出一种结果。

 

输出

仅一行，输出一个数 N，表示可能的结果种数。

 

样例输入

+54+-82

样例输出

2

提示

输入输出样例 2

expression.in 

1-9-+73+6-2

expression.out

8

题解：

f[l][r][k]=0,不存在使子串l～r计算结果为k的计算顺序

 

f[l][r][k]=1,存在使子串l～r计算结果可能为k的计算顺序

 

因为可以按照前缀后缀中缀任何一种方式解析，子串l～r中只要数字字符比符号字符多1，就是合法的

 

f[l][r][]通过f[l][k][]和f[k+1][r][]得到，l<=k<r

 

 

 

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 using namespace std;
  6 char s[101];
  7 int len,minx[101][101],maxx[101][101],f[101][101][801],check[101][101],ans;
  8 void expend(int l,int r)
  9 {int sign,i,j,k;
 10     minx[l][r]=1000;
 11     maxx[l][r]=0;
 12     if (s[l]==‘+‘||s[l]==‘-‘)
 13     {
 14         if (s[l]==‘+‘) sign=1;
 15         else sign=-1;
 16         for (i=l+1; i<=r; i++)
 17         {
 18             if (check[l+1][i]&&check[i+1][r])
 19             {
 20                 for (j=minx[l+1][i]; j<=maxx[l+1][i]; j++)
 21                 {
 22                     if (f[l+1][i][j])
 23                         for (k=minx[i+1][r]; k<=maxx[i+1][r]; k++)
 24                             if (f[i+1][r][k])
 25                             {
 26                                 int tmp=j+sign*k;
 27                                 f[l][r][tmp]=1;
 28                                 if (tmp>maxx[l][r]) maxx[l][r]=tmp;
 29                                 if (tmp<minx[l][r]) minx[l][r]=tmp;
 30                             }
 31                 }
 32             }
 33         }
 34     }
 35     if (s[r]==‘+‘||s[r]==‘-‘)
 36     {
 37         if (s[r]==‘+‘) sign=1;
 38         else sign=-1;
 39         for (i=l; i<r; i++)
 40         {
 41             if (check[l][i]&&check[i+1][r-1])
 42             {
 43                 for (j=minx[l][i]; j<=maxx[l][i]; j++)
 44                 {
 45                     if (f[l][i][j])
 46                         for (k=minx[i+1][r-1]; k<=maxx[i+1][r-1]; k++)
 47                             if (f[i+1][r-1][k])
 48                             {
 49                                 int tmp=j+sign*k;
 50                                 f[l][r][tmp]=1;
 51                                 if (tmp>maxx[l][r]) maxx[l][r]=tmp;
 52                                 if (tmp<minx[l][r]) minx[l][r]=tmp;
 53                             }
 54                 }
 55             }
 56         }
 57     }
 58     for (i=l+1; i<r; i++)
 59     {
 60         if (s[i]!=‘+‘&&s[i]!=‘-‘) continue;
 61         if (s[i]==‘+‘) sign=1;
 62         else sign=-1;
 63         if (check[l][i-1]&&check[i+1][r])
 64         {
 65             for (j=minx[l][i-1]; j<=maxx[l][i-1]; j++)
 66             {
 67                 if (f[l][i-1][j])
 68                     for (k=minx[i+1][r]; k<=maxx[i+1][r]; k++)
 69                         if (f[i+1][r][k])
 70                         {
 71                             int tmp=j+sign*k;
 72                             f[l][r][tmp]=1;
 73                             if (tmp>maxx[l][r]) maxx[l][r]=tmp;
 74                             if (tmp<minx[l][r]) minx[l][r]=tmp;
 75                         }
 76             }
 77         }
 78     }
 79 }
 80 int main()
 81 {int i,j,k;
 82     cin>>s;
 83     len=strlen(s);
 84     for (i=0; i<len; i++)
 85     {
 86         for (j=i; j<len; j++)
 87         {
 88             int num=0,sym=0;
 89             for (k=i; k<=j; k++)
 90             {
 91                 if (s[k]==‘+‘||s[k]==‘-‘) sym++;
 92                 else num++;
 93             }
 94             if (num==sym+1)
 95                 check[i][j]=1;
 96             else check[i][j]=0;
 97         }
 98     }
 99     for (i=0; i<len; i++)
100         if (check[i][i])
101         {
102             f[i][i][s[i]-‘0‘]=1;
103             minx[i][i]=maxx[i][i]=s[i]-‘0‘;
104         }
105     for (j=2; j<=len; j++)
106         for (i=0; i<len; i++)
107             if (i+j-1<len)
108                 if (check[i][j+i-1]) expend(i,i+j-1);
109     for (i=minx[0][len-1]; i<=maxx[0][len-1]; i++)
110         if (f[0][len-1][i]) ans++;
111     cout<<ans;
112 }

 

 

混合表达式


联系
我们