ZJU_1145 OR POJ_1100 Dreisam Equations

Dreisam Equations

{ 两个网站的题有点不一样（ZJH有特判）POJ时间卡得紧，建议去POJ过 }

题目大意：

　　给你一个字符串：是一个等式，等式左边是一个数，右边由若干个数和（）构成，要求加入（+、- 或 *）来使得等式成立，注意：这道题抛弃了原本的优先级，除了括号一律采用从左到右的计算顺序。

题目陷阱：

　　测试数据中可能有 2= (1)(1) 或者 2=((1)1) ，不一定只是在空格处加符号。

题目思路：

　　可以对原字符串进行加工，也就是先预先处理空格，不过这样子比较麻烦，可以考虑到，符号只能加在以下四种情况：

　　1. 数字和数字之间

　　2. 数字和（之间

　　3. ）和数字之间

　　4. ）和（之间

　　这样子分情况以后就容易了许多，可以遍历一遍字符串，将数字存到num数组，（当作 -1，）当作 -2，有可能加符号的地方当作 -3；

　　然后深入优先搜索，遍历所有可能，因为最多等号右边12个数，也就是最多11个符号，也就是3的11次方，基本不会超时。

AC 代码：（两个网站的题 long long 的格式不一样，所以%I64d 可能需要改下）

  1 #include<stdio.h>
  2 typedef long long LL;
  3 LL sum;
  4 LL num[40],no;
  5 LL st[20],so;
  6 char tt[100];
  7 LL to;
  8 
  9 void push(LL x)
 10 {
 11   if(to==0||to>0&&tt[to-1]=='(') st[so++]=x;
 12   else
 13   {
 14     switch(tt[to-1])
 15     {
 16       case '+':st[so-1]=st[so-1]+x;break;
 17       case '-':st[so-1]=st[so-1]-x;break;
 18       case '*':st[so-1]=st[so-1]*x;break;
 19       default: break;
 20     }
 21     to--;
 22   }
 23 }
 24 
 25 // -4 +
 26 // -5 -
 27 // -6 *
 28 
 29 bool dfs(int pos)
 30 {
 31   if(pos>=no)
 32   {
 33     if(st[so-1]==sum) return true;
 34     else return false;
 35   }
 36   if(num[pos]==-3)
 37   {
 38     LL Sst[20],Sso=so;
 39     for(int i=0;i<so;i++)
 40       Sst[i]=st[i];
 41     char Stt[100];
 42     LL Sto=to;
 43     for(int i=0;i<to;i++)
 44       Stt[i]=tt[i];
 45     num[pos]=-4;
 46     tt[to++]='+';
 47     if(dfs(pos+1)) return true;
 48     so=Sso;
 49     for(int i=0;i<so;i++)
 50       st[i]=Sst[i];
 51     to=Sto;
 52     for(int i=0;i<to;i++)
 53       tt[i]=Stt[i];
 54     num[pos]=-5;
 55     tt[to++]='-';
 56     if(dfs(pos+1)) return true;
 57     so=Sso;
 58     for(int i=0;i<so;i++)
 59       st[i]=Sst[i];
 60     to=Sto;
 61     for(int i=0;i<to;i++)
 62       tt[i]=Stt[i];
 63     num[pos]=-6;
 64     tt[to++]='*';
 65     if(dfs(pos+1)) return true;
 66     num[pos]=-3;
 67   }
 68   else if(num[pos]==-1)
 69   {
 70     tt[to++]='(';
 71     if(dfs(pos+1)) return true;
 72   }
 73   else if(num[pos]==-2)
 74   {
 75     to--;
 76     so--;
 77     push(st[so]);
 78     if(dfs(pos+1)) return true;
 79   }
 80   else
 81   {
 82     push(num[pos]);
 83     if(dfs(pos+1)) return true;
 84   }
 85   return false;
 86 }
 87 int main()
 88 {
 89   char s[100];
 90   int cas=1;
 91   while(gets(s))
 92   {
 93     if(s[0]=='0'&&s[1]==0) break;
 94     int i=0;
 95     no=0;
 96     for(;s[i];i++)
 97     {
 98       if(s[i]<='9'&&s[i]>='0')
 99       {
100         if(no>1&&num[no-1]!=-1) num[no++]=-3;
101         num[no]=0;
102         for(;s[i]<='9'&&s[i]>='0';i++)
103         {
104           num[no]=num[no]*10+s[i]-'0';
105         }
106         no++;
107         i--;
108       }
109       else if(s[i]=='(')
110       {
111         if(no>1&&num[no-1]!=-1) num[no++]=-3;
112         num[no++]=-1;
113       }
114       else if(s[i]==')')
115       {
116         num[no++]=-2;
117       }
118     }
119     sum=num[0];
120     so=to=0;
121     printf("Equation #%d:
",cas++);
122     if(!dfs(1))
123     {
124       printf("Impossible

");
125     }
126     else
127     {
128       printf("%I64d=",sum);
129       for(int i=1;i<no;i++)
130       {
131         if(num[i]>=0) printf("%I64d",num[i]);
132         else
133         {
134           switch(num[i])
135           {
136             case -1:printf("(");break;
137             case -2:printf(")");break;
138             case -4:printf("+");break;
139             case -5:printf("-");break;
140             case -6:printf("*");break;
141             default:break;
142           }
143         }
144       }
145       printf("

");
146     }
147   }
148   return 0;
149 }