# include <stdio.h>
# include <stdlib.h>
# include <string.h>
int posnum;
typedef struct
{
   char operator;
   int layer;
}atom;
void init(char line[])
{
     int i;
     for(i=0;i<strlen(line);i++)
       if(line[i]=='=')
        {
         strcpy(line,line+1+i);
         break;
        }
     for(i=0;i<strlen(line);i++)
     {
       if(line[i]=='(')
       {
         while(line[i+1]==' ') strcpy(line+i+1,line+i+2);
       }
       if(line[i]==')')
       {
         while(line[i-1]==' ') strcpy(line+i-1,line+i),i--;              
       }
     }
     char templine[1024],*pos;
     strcpy(templine,strtok(line," "));
     while(pos=strtok(NULL," ")) 
     {
       strcat(templine," ");
       strcat(templine,pos);
     }
     strcpy(line,templine);
     for(i=0;i<strlen(line);i++)
     {
         if(line[i]==')'&&line[i+1]!=')'&&line[i+1]!=' '&&line[i+1]!='\0')
         {
            int j;
            for(j=strlen(line)+1;j>i+1;j--) line[j]=line[j-1];
            line[i+1]=' ';
         }
     }
     for(i=0;i<strlen(line);i++)
     {
      if(line[i]>='0'&&line[i]<='9'&&line[i+1]=='(')
      {
            int j;
            for(j=strlen(line)+1;j>i+1;j--) line[j]=line[j-1];
            line[i+1]=' ';
      }
     }
         
}
int sub_cul(int a,int b,char operator)
{
    switch(operator)
    {
     case '+':return a+b;break;
     case '-':return a-b;break;
     case '*':return a*b;break;
     };
}
int cul(char line[])
{
    int layer=0;
    atom stack2[1024];
    int stack1[1024];
    int top1=-1,top2=-1;
    int i;
    for(i=0;i<strlen(line);i++)
    {
     if(line[i]>='0'&&line[i]<='9') 
     {
       int temp=line[i]-48;
       while(line[i+1]>='0'&&line[i+1]<='9')
       {
         i++;
         temp=temp*10+line[i]-48;                        
       } 
       stack1[++top1]=temp;
     }
     else if(line[i]=='(') layer++;
     else if(line[i]==')') layer--;
     else 
     {
       if(top2>=0&&layer<=stack2[top2].layer)
       {
        while(top2>=0&&layer<=stack2[top2].layer)
        {
          int result=sub_cul(stack1[top1-1],stack1[top1],stack2[top2].operator);
          top1--;
          stack1[top1]=result;
          top2--;
        }
        stack2[++top2].layer=layer;
        stack2[top2].operator=line[i];
       }
       else
       {
           stack2[++top2].layer=layer;
           stack2[top2].operator=line[i];
       }   
     }
    }
    while(top2!=-1)
    {
     stack1[top1-1]=sub_cul(stack1[top1-1],stack1[top1],stack2[top2--].operator);
     top1--;
    }
    return stack1[0];
      
}
int deal(char line[],int pos)
{
    if(line[pos]=='\0')
    {
       if(cul(line)==posnum) return 1;
       else return 0;
    }
    else if(line[pos]!=' ') return deal(line,pos+1);
    else
    {
      line[pos]='+';
      if(deal(line,pos+1)) return 1;
      line[pos]='-';
      if(deal(line,pos+1)) return 1;
      line[pos]='*';
      if(deal(line,pos+1)) return 1;
      line[pos]=' ';
      return 0;
    }
}
      
int main()
{
    char line[1024];
    int count=1;
    while(1)
    {
      gets(line);
      char templine[1024];
      strcpy(templine,line);
      if(!strcmp(line,"0")) break;
      posnum=atoi(strtok(templine,"="));
      init(line);
      printf("Equation #%d:\n",count++);
      if(deal(line,0)) printf("%d=%s\n\n",posnum,line);
      else printf("Impossible\n\n");
    }
    return 0;
}
      

• Re:两个月后终于把它给AC了，字符串处理稍微烦点，要考虑手写算式的多种可能情况，贴代码 (4) lzg666456 2011-03-31 13:37:16