填运算符（C语言）

最近看到一个有趣的老问题，填运算符。给定五个数字 比如 5 5 5 5 = 5，
要求在等号左边的四个5之间填写{+，-，*,/}使其满足等式，编写程序枚举运算符号出现的各种可能，可以求所有满足条件的情况。
如果问题再一般化一点呢？这些数字不一定相同，而且个数不定，比如有这样一个需求：
从文件读入一行数字共有N个数字，前面N-1个数字进行加减乘除四则运算，看计算结果是否等于最后一个数字，
如果等于，则记录到文件out.txt
输出所有可能的符合条件的情况结果存入文件中.
例如
in.txt
3 3 3 3
out.txt
3+3-3=3
3-3+3=3
3*3/3=3
3/3*3=3

算法分析：
决定用C语言实现这个算法，程序采用主程序子程序风格
 程序需要实现如下几个功能
 1.从文件中读取数据
   1.1 读入的数据需要存储到方便操作的数据结构中，自然这里会想到使用数组来存储读入的前N-1个整数，
     然后用一个整数result存储最后一个数字，为了使计算结果和result相比较，来确定是否符合条件
     所以这里还需要定义一个整型变量存储计算结果。
     经过分析可有如下数据结构：
     int[MAX_SIZE] num; //存储整数
     int num_len;//存储整数数组的实际长度
     int result;//存储运算式的结果
     int t_result;//存储运算式的实际运算结果
   
   1.2 定义一下函数名称
     read();
   
 2.处理数据，这个子功能点是程序的核心，需要详细分析
   2.1 根据num_len就可以知道数字之间需要有num_len-1个符号，分析到这里就会遇到，这些符号怎样表示的问题。要计算
     加减乘除四则运算，总得需要一个结构存储表示它才行，所以这里想到用0，1，2，3四个整型常量来代表{+-*/},为什么
     不直接使用{+-*/}的char类型来表示呢？因为它们的ascii码不连续(+43 *42 -45 /47),为每个位置上的字符赋值的时候
     就不能用for循环直接赋值来遍历{+-*/}。确定了表示方式，就可以确定符号的存储结构了，用整型数组来表示。
     经分析可有如下存储结构：
     int[MAX_SIZE] sign;//存储整数中间的符号
     int sign_len;//存储符号的实际个数(=num_len-1)
   
   2.2 确定了符号的存储结构和表示方式后，我们就可以产生出一个可能的符号组合方式，比如{0000}代表数字之间运算
     符号全为+号，{0001}代表数字之间前三个运算符号为+号，最后一个为-号。要列出所有符号条件的记录就需要生成所有的
     可能情况，这里很容易想到用多个for循环嵌套，在每个字符位置上循环{0123}代表{+-*/}四种可能情况，但那是在知道
     循环嵌套层数的情况下，也就是sign_len确定的情况下才适用。所以我们这里用递归来实现生成所有可能情况的任务
     把这个函数定义为generator();
     
     当然这里还有其他的非递归方法来产生符号数组的方法，可以人为规定符号位为4进制值的整数(逢四进一)，
     由num_len确定sign_len,(sign_len=num_len-1)也即是四进制数组的实际长度，每次让最后一个符号位加一，然后从后
     往前扫描一遍数组，有大于等于4的就进一位，一遍扫描完成后，数组就是符号位可能情况的一种表示，
     直到数组全为3结束,即是从{000000}-{333333}。
     
   
   2.3 生成一个可能的情况后，我们就可以根据num[],num_len,sign[],sign_len这些数据计算出表达的结果t_result，然后与result
     向比较，如果相同就写入文件，考虑到每次发现一个符合条件的记录就写入文件，频繁写入操作影响效率，这里使用一个
     缓冲区来存放满足条件的记录，等到缓冲区满后在写入文件,但是把写表达式到缓冲区的时候，是不能用{0123}表示运算符的
     所以需要一个char数组来存储与其对应的符号。在计算表达式结果的时候我们需要自定义一个计算函数，来计算两个
     数之间的四则运算结果。
     经分析可有如下存储结构：
     buffer[][];//固定大小的缓冲区
     char[]={'+','-','*','/'};
   2.4 根据2.3的分析我们可以定义三个函数
     cal(number1,oper,number2);//计算两个整数的四则运算值，参数number1为第一数，oper为操作符{0123},
                   参数number2为第二个数，函数返回计算结果
                  
     getResult();//计算表达式的值，返回表达式的计算结果
     writerBuffer();//根据计算结果t_result和result比较确定是否把表达式写入缓冲区，并且监测缓冲区是否已满
     
 3.把符合条件的记录写入文件
   3.1 当缓冲区超过一定长度时，就需要调用writefile()函数来写文件，这里还有个情况，就是满足情况的记录很少一直没有触发
     写文件操作，这时我们就需要在程序结束的时候，把缓冲区的内容写入文件。

程序源代码：

 

#include<stdio.h>
#define BLOCK_SIZE 1024
#define MAX_LEN 20

/**********************全局数据区****************************/
const char *filein="in.txt"; //输入文件
const char *fileout="out.txt"; //输出文件

int num[MAX_LEN]; //存储从文件读取的整数
int num_len=0; //存储整数数组的实际长度

int sign[MAX_LEN]; //存储整数中间的符号
int sign_len=0; //存储符号的实际长度

int result=0; //存储期望结果
float t_result=0; //存储实际结果

char op[]={'+','-','*','/'}; //
char buffer[BLOCK_SIZE]; //输出记录的缓冲区
int buffer_len=0; //buffer的实际长度



/**********************全局数据区****************************/



/**********************函数声明开始****************************/
void read(const char * filename,int num[],int *num_len,int *result);
void generator(int sign_point);
void getResult();
float calc(float a,int p,float b);
void writeBuffer();
void convertINTtoSTR(int num,char str[],int * str_len);
void writefile(const char * filename ,const char * buffer);

void showNum(int num[],int num_len);
void showSign(int sign[],int sign_len);
void showBuffer(char * buffer);
/**********************函数声明结束****************************/
int main()
{

  read(filein,num,&num_len,&result);
  showNum(num,num_len);
  generator(0);
  showBuffer(buffer);
  buffer[buffer_len]='\0';
  writefile(fileout,buffer);
  getchar();
  return 0;
}


/**********************函数定义开始****************************/


/******************************************************
*函数功能：从文件中读取整数
*参数说明：*filename 文件名
* num[] 存储整数的数组
           num_len 数组长度
           *result 期望结果
*******************************************************/
void read(const char * filename,int num[],int *num_len,int *result){
    int c;
    int tmp=0;
    FILE *fp=fopen(filename,"r+");
    if(!fp){
         printf("error to open file ");
         return ;
    }
    while((c=fgetc(fp))!=EOF)
    {
          if(c==32)
          {
               num[(*num_len)++]=tmp;
               tmp=0;

          }else if(c>='0' && c<='9'){
                tmp=tmp*10+c-'0';
          }
    }
   (*result)=tmp;
    fclose(fp);
    //(*num_len)=(*num_len)+1;
    sign_len=(*num_len)-1;
}
/******************************************************
*函数功能：递归产生所以可能的符号组合
*参数说明：sign_point 当前符号位置指针
*******************************************************/
void generator(int sign_point){
//负责产生一种运算符可能的排列情况
//参数 sign_point 指示当前指针在数组sign中的位置
//程序采用递归方式，
//    如果sign_point==len则说明sign_point已经指向数组尾部，也就是说现在sign数组中的状态代表了一种可能的运算符排列情况
//    否则
//        a所指向的那个sign[sign_point]元素（运算符）有{+,-,*,/}四种可能，分别用{0,1,2,3}来表示
//            当sign[sign_point]运算符确定后，指针继续下移一位，再次调用generator函数

     if(sign_point==sign_len){

         showSign(sign,sign_len);
         getResult();
         printf("reslut=%d,t_result=%f\n",result,t_result);
         writeBuffer();

     }else{
           for(int i=0;i<4;i++){
                   sign[sign_point]=i;
                   generator(sign_point+1);
           }
     }

}
/******************************************************
*函数功能：计算表达式的实际结果
*******************************************************/
void getResult(){

    //为了方便计算，假设在num[0]前还有个0+，即是0+num[0]
    float left=0;
    int op_cur=0;
    float right=num[0];

    for(int i=0;i<sign_len;i++){
        if(sign[i]<2){
            //如果当前符号为加减，就计算前面的两个数的运算值
            left=calc(left,op_cur,right);
            op_cur=sign[i];
            right=num[i+1];
        }else{
           //如果当前符号为乘除，因为乘除优先级高，就计算当前符号位后面的数和right的运算值
            right=calc(right,sign[i],num[i+1]);

        }
    }
    //计算最后的结果
    t_result=calc(left,op_cur,right);

}
/******************************************************
*函数功能：计算两个数的四则运算值
*******************************************************/
float calc(float a,int p,float b){
//这里做除法操作时，如果b=0会产生错误
    switch(p){
        case 0:
            return a+b;
        case 1:
            return a-b;
        case 2:
            return a*b;
        case 3:
            return a/b;
    }
}
/******************************************************
*函数功能：把符合条件的记录写入缓冲区

*******************************************************/

void writeBuffer(){
     int tmp=0;
     char str[4];//整数最多为4位
     int str_len=0;

     if((float)t_result==result){

         for(int i=0;i<num_len;i++)
         {
                 //把数字num[i]转换成字符类型
                 convertINTtoSTR(num[i],str,&str_len);
                 for(int j=str_len-1;j>=0;j--){
                         buffer[buffer_len++]=str[j];
                 }

                 buffer[buffer_len++]=op[sign[i]];
         }

         buffer[buffer_len-1]='=';
          //把数字result转换成字符类型
           convertINTtoSTR((int)result,str,&str_len);
           for(int j=str_len-1;j>=0;j--){
               buffer[buffer_len++]=str[j];
           }
          //添加换行符
         buffer[buffer_len++]='\n';

         //如果缓冲区快满了，就调用writefile()函数写入文件，并清空缓冲区
         if(buffer_len>BLOCK_SIZE-50){
                 buffer[buffer_len]='\0';
                 writefile(fileout,buffer);
                 buffer_len=0;
         }
     }

}

/******************************************************
*函数功能：把整数转换为字符数组 (倒序存储的)
*参数说明：num 要转换的整数
* str 字符数组
           str_len 转换后的字符数组长度
*******************************************************/

void convertINTtoSTR(int num,char str[],int * str_len){

     (*str_len)=0;
     if(num<=0){
        str[(*str_len)++]=0+'0';
        return;
     }
     while(num){
                str[(*str_len)++]=(num%10)+'0';
                num=num/10;
         }

}
/******************************************************
*函数功能：写缓冲区内容到文件
*******************************************************/
void writefile(const char * filename ,const char * buffer){

     FILE *fp=fopen(filename,"w");

     if(!fp){
     printf("error to open file");
     return ;
     }
     //函数遇到'\0'结束
     fputs(buffer,fp);

     fclose(fp);
}


/**********************函数定义结束****************************/



/****************辅助函数，用于输出数据区内容*****************/

void showNum(int num[],int num_len){

     for(int i=0;i<num_len;i++){
             printf("%d ",num[i]);
     }
     printf("\n%d\n",result);
}

void showSign(int sign[],int sign_len){
     for(int i=0;i<sign_len;i++){
             printf("%d ",sign[i]);
     }
     printf("\n");
}

void showBuffer(char * buffer){

     printf("%s",buffer);
}

/****************辅助函数，用于输出数据内容*****************/