自动生成四则运算题目(C语言)

Github项目地址：https://github.com/huihuigo/expgenerator

合作者：马文辉（3118005015）、卢力衔（3118005013）

项目简介

1题目：实现一个自动生成小学四则运算题目的命令行程序（也可以用图像界面，具有相似功能）。

2说明：

自然数：0, 1, 2, …。

真分数：1/2, 1/3, 2/3, 1/4, 1’1/2, …。
运算符：+, −, ×, ÷。
括号：(, )。
等号：=。
分隔符：空格（用于四则运算符和等号前后）。
算术表达式：

e = n | e1 + e2 | e1 − e2 | e1 × e2 | e1 ÷ e2 | (e),

其中e, e1和e2为表达式，n为自然数或真分数。

四则运算题目：e = ，其中e为算术表达式。

3需求：

（完成）使用 -n 参数控制生成题目的个数，例如 Myapp.exe -n 10 将生成10个题目。

（完成）使用 -r 参数控制题目中数值（自然数、真分数和真分数分母）的范围，例如 Myapp.exe -r 10 将生成10以内（不包括10）的四则运算题目。
该参数可以设置为1或其他自然数。该参数必须给定，否则程序报错并给出帮助信息。

（完成）生成的题目中计算过程不能产生负数，也就是说算术表达式中如果存在形如e1− e2的子表达式，那么e1≥ e2。
（完成）生成的题目中如果存在形如e1÷ e2的子表达式，那么其结果应是真分数。
（完成）每道题目中出现的运算符个数不超过3个。
（完成）程序一次运行生成的题目不能重复，即任何两道题目不能通过有限次交换+和×左右的算术表达式变换为同一道题目。
例如，23 + 45 = 和45 + 23 = 是重复的题目，6 × 8 = 和8 × 6 = 也是重复的题目。3+(2+1)和1+2+3这两个题目是重复的，由于+是左结合的，1+2+3等价于(1+2)+3，也就是3+(1+2)，也就是3+(2+1)。但是1+2+3和3+2+1是不重复的两道题，因为1+2+3等价于(1+2)+3，而3+2+1等价于(3+2)+1，它们之间不能通过有限次交换变成同一个题目。

生成的题目存入执行程序的当前目录下的Exercises.txt文件，格式如下：

四则运算题目1
四则运算题目2

……

其中真分数在输入输出时采用如下格式，真分数五分之三表示为3/5，真分数二又八分之三表示为2’3/8。

（完成）在生成题目的同时，计算出所有题目的答案，并存入执行程序的当前目录下的Answers.txt文件，格式如下：

答案1
答案2

特别的，真分数的运算如下例所示：1/6 + 1/8 = 7/24。

（完成）程序应能支持一万道题目的生成。
（未完成）程序支持对给定的题目文件和答案文件，判定答案中的对错并进行数量统计，输入参数如下：

Myapp.exe -e <exercisefile>.txt -a <answerfile>.txt

统计结果输出到文件Grade.txt，格式如下：

Correct: 5 (1, 3, 5, 7, 9)

Wrong: 5 (2, 4, 6, 8, 10)

其中“:”后面的数字5表示对/错的题目的数量，括号内的是对/错题目的编号。为简单起见，假设输入的题目都是按照顺序编号的符合规范的题目。

PSP表格

PSP2.1	Personal Software Process Stages	预估耗时（分钟）	实际耗时（分钟）
Planning	计划	30	40
· Estimate	· 估计这个任务需要多少时间	30	40
Development	开发	1080	1100
· Analysis	· 需求分析 (包括学习新技术)	120	120
· Design Spec	· 生成设计文档	60	70
· Design Review	· 设计复审 (和同事审核设计文档)	30	40
· Coding Standard	· 代码规范 (为目前的开发制定合适的规范)	30	30
· Design	· 具体设计	120	120
· Coding	· 具体编码	480	480
· Code Review	· 代码复审	120	120
· Test	· 测试（自我测试，修改代码，提交修改）	120	120
Reporting	报告	90	80
· Test Report	· 测试报告	30	30
· Size Measurement	· 计算工作量	30	20
· Postmortem & Process Improvement Plan	· 事后总结, 并提出过程改进计划	30	30
合计		1200	1220

需求分析及方案介绍

操作数相关的需求分析选取自1.5版本说明：

一些前言

　　采用的方案是将一条四则运算表达式转化为一棵相应的二叉树，表达式的运算顺序与二叉树的树形结构相对应，如果要求随机生成表达式，那么对应的表达式树的结构也是随机的。

所以，可以反向操作，随机生成表达式树的树形结构，也对应随机生成了一条表达式。

方案具体介绍（From 卢力衔，马文辉）：

方案总体是，先随机生成只有运算符的树形结构，在叶子结点加入操作数结点之后，就生成了一条表达式。

　　生成一条随机四则运算表达式的完整过程有 6 条步骤。

　　　　1.先生成当前表达式的运算符数量，再随机选择运算符；

　　　　2.将选择的运算符，组合成一个树形结构，也采用随机的方式；

　　　　3.在运算符树（只有运算符的树）的叶子结点上添加操作数（操作数也随机生成，思路就是上图的需求分析）；

　　　　　　4.判断生成的表达式合不合法（主要检测除数是否为0），如果合法则计算出表达式的结果；

　　　　　　5.检测是否与之前的表达式存在重复关系，即需求6的检测；

　　　　　　　　6.进行文件读写。

设计实现过程

整个程序分为4个cpp文件和1个头文件,分别为

Myapp.h　　　　　　　　　　　//结构体定义和函数声明

Myapp.cpp（main函数文件）　 //main函数中处理命令行参数和程序主逻辑

createExp.cpp　　　　　　　　 //有关创建一条表达式的函数实现，对应上述方案中的1、2、3点

judgeExp.cpp　　　　　　　　 //有关判断表达式的合法性和重复性的函数实现，对应上述方案中的4、5点

writeExpAndAnswer.cpp　　 //有关表达式写入文件的函数实现，对应上述方案中的6点

在一个功能模块编码之前，结对的两人先讨论好功能实现的方案，至少给出一个可行的方案，确定好方案之后，再实行编码。

由于这次的代码文件不大，所以就没用使用github进行版本的交接，而是通过微信相互发送文件，附上当前代码版本的改动说明，

同时一次交接后就更新版本号，便于区分不同阶段的代码。这次的结对项目经过了从1.0版本到最后的2.0版本。

下面是开发过程中的一些版本的说明：

具体设计过程：

第一阶段，不考虑重复性，合法性的检测和命令行参数的输入，先生成运算符的树形结构和添加操作数的操作，操作数考虑上减法和除法的要求；同时，完成在控制台中输出打印表达式的中缀表达式的函数实现。

第二阶段，考虑合法性的检测，显式上的除法已经不会出现1/0这样的表达式了，但是还是有可能生成6/(3 – 3)这样的表达式，因此需要加入合法性的检测。在合法性的检测，是通过计算该表达式的运算结果的方式来检测的。

第三阶段，考虑重复性的检测，例如题目中的(1 + 2) + 3与3 + (1 + 2)的重复情况，同时遇到了一种情况，一开始的输出结果都是在控制台中输出表达式，对于1 + （2 + 3）这种表达式，我们认为加法和乘法满足交换律，就省略了后面括号的输出，以至于出现了（1 * 1）/ 1和1 *（1 / 1）两种表达式都输出为1 * 1 / 1的形式，所以对表达式的中缀输出作了调整。

　　而且，我们的方案检测重复性是与前面生成的所有表达式进行比较，表达式树比较的函数是递归实现的，这样会出现一种循环+递归的代码结构，简单进行循环递归会导致程序运行速度变慢，这不是能接受的方案。因此，提出了先比较两条表达式的基本信息，先比较运算符数量，运算符是否相同，操作数是否相同，结果是否相同的基本信息，最大程度上减少递归比较的次数，只有在前面的基本信息都相同的情况下，才会触发最后的表达式树递归比较。

第四阶段，实现文件读写和命令行参数的输入，错误处理等，重新检查代码。

代码说明

文件中的代码，函数是有顺序的，在函数头的注释中可以找到当前函数的功能，参数和返回值。

//此处为Myapp.h头文件代码
#ifndef MYAPP_H_INCLUDED
#define MYAPP_H_INCLUDED

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <unistd.h>
#define TRUE 1
#define FALSE 0
typedef int Status;

//操作数结构体定义
typedef struct NumInfo{
    //denominator 分母, numerator 分子
    int numerator;
    int denominator;
} NumInfo;

//表达式树结点定义
typedef struct BiTNode{
    union {
        char opSym;         //运算符
        NumInfo numForm;    //操作数
    } value;

    int flag;   //0:value = opSym   1:value = num    -1:undefined
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

//表达式基本信息结构体定义
typedef struct {
    BiTree ExpTree;     //表达式树
    int symCount;       //运算符个数
    char* symArr;       //运算符数组

    NumInfo* opNumArr;  //操作数数组
    NumInfo result;     //表达式结果
} ExpInfo, *ExpInfoPtr;


//生成运算符树部分的函数声明
char* chooseSym(int symNum);
BiTree createSymTree(int sym, char* symArr);
BiTNode* createSymNode(int& symArrIndex, char* symArr);


//插入操作数部分的函数声明
void addOpNumInSymTree(int numRange, BiTree symTree, int& flag);
void setNumForSubtraction(int &num1_numerator, int &num1_denominator, int &num2_numerator, int &num2_denominator, int numRange);
void setNumForDivision(int &num1_numerator, int &num1_denominator, int &num2_numerator, int &num2_denominator, int numRange);
void getRandomNum(int &numerator_, int &denominator_, int numRange);
BiTNode* createNumNode(int numerator, int denominator);


//检查表达式是否合法的函数声明，包含计算表达式的函数
Status isLegalExp(BiTree ExpTree, NumInfo& result);
NumInfo getValue(BiTree ExpTree, int&flag, int model);
int findGCD(int a, int b);
int findLCM(int a, int b);
NumInfo simplify(NumInfo numForm);


//检测是否为重复的表达式的函数声明
Status isRepetitive(ExpInfoPtr ExpArr, ExpInfo tempExpInfo, int ExpIndex);
Status ExpTreeCmp(BiTree T1, BiTree T2);
Status symArrCmp(char* arr1, char* arr2, int length);
Status opNumArrCmp(NumInfo* arr1, NumInfo* arr2, int length);
void addInExpArr(ExpInfoPtr ExpArr, ExpInfo tempExpInfo, int ExpIndex);
void getOpNumArr(BiTree ExpTree, NumInfo* OpNumArr, int& OpNumArrIndex);


//题目和答案文件读写函数的声明
Status Priority_com(char c1, char c2);
void writeExp(BiTree T, FILE* file);
void writeAnswer(NumInfo result, FILE* file);

#endif // MYAPP_H_INCLUDED

下面是Myapp.cpp代码，包含main函数：

  1 #include "Myapp.h"
  2 #include "createExp.cpp"
  3 #include "judgeExp.cpp"
  4 #include "writeExpAndAnswer.cpp"
  5 
  6 Status isNumString(char* str)
  7 {
  8     int i;
  9     for(i = 0; i < strlen(str); i++)
 10         if(str[i] < '0' || str[i] > '9')
 11         return FALSE;
 12     return TRUE;
 13 }
 14 
 15 int main(int argc, char *argv[])
 16 {
 17     int questionCount = 0, numRange = 0; 
 18 
 19     int opt;
 20     while((opt=getopt(argc,argv,"n:r:"))!=-1)
 21     {
 22         switch(opt)
 23         {
 24             case 'n':   if(isNumString(optarg))   questionCount = atoi(optarg);
 25                         break;
 26             case 'r':   if(isNumString(optarg))   numRange = atoi(optarg);
 27                         break;
 28             default:    ;
 29         }
 30     }
 31     if( questionCount == 0 || numRange == 0 )
 32     {
 33         printf("命令行参数输入错误...\n");
 34         printf("输入格式为Myapp.exe -n 题目数(整数) -r 范围值(整数)\n");
 35         exit(1);
 36     }
 37     srand((int)time(0));
 38 
 39 
 40     FILE* questionFile,  *answerFile;
 41     questionFile = fopen("question.txt", "w");
 42     answerFile = fopen("answer.txt", "w");
 43     if(!questionFile || !answerFile)
 44     {
 45         printf("文件打开失败...按任意键退出\n");    getchar();
 46         exit(1);
 47     }
 48 
 49     ExpInfoPtr ExpArr = NULL;
 50     ExpArr = (ExpInfoPtr)malloc( (questionCount+1) * sizeof(ExpInfo));
 51     if(!ExpArr)
 52     {
 53         printf("空间申请失败...按任意键退出\n");    getchar();
 54         exit(1);
 55     }
 56 
 57     int ExpIndex = 1;
 58     int repetiveTime = 0;
 59     int runtimeFlag = TRUE;
 60 
 61     while(ExpIndex <= questionCount)
 62     {
 63         //1、先生成运算符数量，再随机选择运算符
 64         int symCount = rand()%3 +1;   //一条表达式最多选择3个运算符
 65         char* symArr = chooseSym(symCount);
 66         if(!symArr)
 67         {
 68             runtimeFlag = FALSE;
 69             break;
 70         }
 71 
 72         //2、运算符搭成树
 73         BiTree symTree = createSymTree(symCount, symArr);
 74         if(!symTree)
 75         {
 76             runtimeFlag = FALSE;
 77             break;
 78         }
 79 
 80         //3、在运算符树的叶子结点加操作数
 81         int addFlag = TRUE;
 82         addOpNumInSymTree(numRange, symTree, addFlag);
 83         if(addFlag == FALSE)
 84         {
 85             runtimeFlag = FALSE;
 86             break;
 87         }
 88 
 89         //4、判断生成的表达式是否合法，主要检测除数是否为0，并进行文件读写
 90         BiTree ExpTree = symTree;
 91         NumInfo result;
 92 
 93         if( isLegalExp(ExpTree, result) )
 94         {
 95             //5、表达式合法则检查重复性
 96             //5.1   先获取当前表达式的基本信息
 97             ExpInfo tempExpInfo;
 98             tempExpInfo.ExpTree = ExpTree;
 99             tempExpInfo.symCount = symCount;
100             tempExpInfo.symArr = symArr;
101 
102             int opNumCount = symCount+1;
103             NumInfo* opNumArr = (NumInfo*)malloc( opNumCount*sizeof(NumInfo));
104             if(!opNumArr)
105             {
106                 runtimeFlag = FALSE;
107                 break;
108             }
109 
110             int opNumArrIndex = 0;
111             getOpNumArr(ExpTree, opNumArr, opNumArrIndex);
112 
113             tempExpInfo.opNumArr = opNumArr;
114             tempExpInfo.result = result;
115 
116 
117             if(ExpIndex == 1)    //第二条题目开始需要检测重复性
118                 addInExpArr(ExpArr, tempExpInfo, ExpIndex);
119             else{
120 
121                 if( !isRepetitive(ExpArr, tempExpInfo, ExpIndex) )
122                 {
123                     //5.2.1 合法的话，则加入到表达式数组中
124                     addInExpArr(ExpArr, tempExpInfo, ExpIndex);
125                     repetiveTime = 0;
126                 }
127                 else {
128                         //5.2.2 不合法的话，生成重复次数更新，释放空间，防止范围为2，题目数为10000的恶意输入
129                         repetiveTime++;
130                         if(repetiveTime >= ExpIndex)
131                             break;
132                         free(opNumArr);
133                         continue;
134                 }
135             }
136 
137             //6、在控制台、题目文件、答案文件打印题目序号
138             printf("%d.\t", ExpIndex);
139             fprintf(questionFile,"%d.\t", ExpIndex);
140             fprintf(answerFile, "%d.\t", ExpIndex);
141 
142             //6.1 表达式写入题目文件
143             writeExp(ExpTree, questionFile);
144             printf("= ");
145             fprintf(questionFile, "= \n");
146 
147             //6.2 写入答案文件
148             writeAnswer(result, answerFile);
149 
150             //6.3 控制台展示运算过程
151             //int flag = TRUE;
152             //getValue(ExpTree, flag, 1);
153             //printf("\n");
154 
155             //7、 更新题号
156             ExpIndex++;
157         }
158     }
159 
160     //8、 生成完毕，关闭文件，释放表达式数组空间
161     fclose(questionFile);
162     fclose(answerFile);
163     free(ExpArr);
164 
165     if(runtimeFlag == FALSE)
166     {
167         printf("空间申请失败...按任意键退出\n");    getchar();
168         exit(1);
169     }
170     printf("\n当前已生成 %d 道，操作数范围为 %d 的四则运算题目.\n", ExpIndex-1, numRange);
171     printf("题目保存在当前目录下的question.txt文件中\n答案保存在当前目录下的answer.txt文件中\n");
172     return 0;
173 }

下面是createExp.cpp代码：

  1 #include "Myapp.h"
  2 /**
  3  * @function    选择当前生成的表达式中的运算符
  4  * @param       symNum:     运算符数量
  5  *
  6  * @return      symArr:     选择的运算符数组
  7  */
  8 char* chooseSym(int symNum)
  9 {
 10     char* symArr = NULL;
 11     char sym[4] = {'+', '-', '*', '/'};
 12     symArr = (char*)malloc( symNum*sizeof(char));
 13     if(!symArr)
 14         return NULL;
 15 
 16     int i;
 17     for(i = 0; i < symNum; i++)
 18         symArr[i] = sym[rand()%4];
 19 
 20     return symArr;
 21 }
 22 
 23 /**
 24  * @function    根据传入的运算符数组索引创建运算符结点
 25  * @param       symArrIndex:    运算符数组索引;
 26                 symArr:         选择的运算符数组
 27  *
 28  * @return      nodePtr:        新创建运算符结点的指针
 29  */
 30 BiTNode* createSymNode(int& symArrIndex, char* symArr)
 31 {
 32     BiTNode* nodePtr = NULL;
 33     nodePtr = (BiTNode*) malloc(sizeof(BiTNode));
 34 
 35     if(!nodePtr)
 36         return NULL;
 37 
 38     nodePtr->flag = 0;
 39     nodePtr->value.opSym = symArr[symArrIndex++];
 40     nodePtr->rchild = nodePtr->lchild = NULL;
 41 
 42     return nodePtr;
 43 }
 44 
 45 /**
 46  * @function    根据传入的运算符数组组成一棵树
 47  * @param       symCount:     运算符数量;
 48                 symArr:选择的运算符数组
 49  *
 50  * @return      T:只有运算符的树根结点指针
 51  */
 52 BiTree createSymTree(int symCount, char* symArr)
 53 {
 54     BiTree root = NULL;
 55     int symArrIndex = 0, i;
 56     root = createSymNode(symArrIndex, symArr);
 57     if(!root)
 58         return NULL;
 59 
 60     for(i = 0; i < symCount-1; i++)
 61     {
 62         BiTNode* newNodePtr = createSymNode(symArrIndex, symArr);
 63         BiTNode* temp = root;
 64 
 65         while(1)
 66         {
 67             //根据随机数，随机生成运算符的树形结构
 68             if(rand()%2)
 69             {
 70                 if(!temp->lchild)
 71                 {
 72                     temp->lchild = newNodePtr;
 73                     break;
 74                 }
 75                 else temp = temp->lchild;
 76             }
 77             else {
 78                 if(!temp->rchild)
 79                 {
 80                     temp->rchild = newNodePtr;
 81                     break;
 82                 }
 83                 else temp = temp->rchild;
 84             }
 85         }
 86     }
 87     return root;
 88 }
 89 
 90 
 91 /**
 92  * @function    为传入的运算符树添加符合要求的操作数
 93  * @param       numRange:   操作数的范围
 94                 symTree:    运算符树
 95                 flag:       当前步骤是否成功的标记值，默认为TRUE
 96  *
 97  * @return      void
 98  */
 99 void addOpNumInSymTree(int numRange, BiTree symTree, int& flag)
100 {
101     //左孩子指针和右孩子指针都为空
102     if(!symTree->lchild && !symTree->rchild)
103     {
104         //范围大于1，随机生成操作数
105         if(numRange > 1)
106         {
107             int num1_numerator, num1_denominator;
108             int num2_numerator, num2_denominator;
109 
110             //如果运算符是-和/，操作数有要求
111             if( symTree->value.opSym == '-' )
112                 setNumForSubtraction(num1_numerator, num1_denominator, num2_numerator, num2_denominator, numRange);
113 
114             else if( symTree->value.opSym == '/' )
115                 setNumForDivision(num1_numerator, num1_denominator, num2_numerator, num2_denominator, numRange);
116 
117             else {
118                 getRandomNum(num1_numerator, num1_denominator, numRange);
119                 getRandomNum(num2_numerator, num2_denominator, numRange);
120             }
121 
122             symTree->lchild = createNumNode(num1_numerator, num1_denominator);
123             symTree->rchild = createNumNode(num2_numerator, num2_denominator);
124         }
125         else {
126             //范围等于1，操作数只能为0
127             symTree->lchild = createNumNode(0, 1);
128             symTree->rchild = createNumNode(0, 1);
129         }
130 
131         if(!symTree->lchild || !symTree->rchild)
132             flag = FALSE;
133 
134         return;
135     }
136 
137     //左孩子指针和右孩子指针都不为空
138     else if( symTree->lchild && symTree->rchild)
139     {
140         addOpNumInSymTree(numRange, symTree->lchild, flag);
141         addOpNumInSymTree(numRange, symTree->rchild, flag);
142     }
143 
144     //左孩子指针和右孩子指针其中一个为空
145     else
146     {
147         int _numerator, _denominator;
148         getRandomNum(_numerator, _denominator, numRange);
149         BiTNode* newNumNode = createNumNode(_numerator, _denominator);
150 
151         if(!newNumNode)
152             flag = FALSE;
153 
154         //左孩子指针为空，则插入左孩子，否则插入右孩子
155         if(!symTree->lchild){
156             symTree->lchild = newNumNode;
157             addOpNumInSymTree(numRange, symTree->rchild, flag);
158         }
159         else{
160             symTree->rchild = newNumNode;
161             addOpNumInSymTree(numRange, symTree->lchild, flag);
162         }
163     }
164 }
165 
166 /**
167  * @function     根据传入的数值创建运算数结点
168  * @param        numerator:     操作数的分子
169                  denominator:   操作数的分母
170  *
171  * @return       nodePtr:       操作数结点指针
172 */
173 BiTNode* createNumNode(int numerator, int denominator)
174 {
175     BiTNode* nodePtr = NULL;
176     nodePtr = (BiTree)malloc(sizeof(BiTNode));
177     if(!nodePtr)
178         return NULL;
179 
180     nodePtr->flag = 1;
181 
182     nodePtr->value.numForm.numerator = numerator;
183     nodePtr->value.numForm.denominator = denominator;
184 
185     nodePtr->lchild = nodePtr->rchild = NULL;
186     return nodePtr;
187 }
188 
189 /**
190  * @function    随机生成numRange范围内的操作数
191  * @param       numRange:       操作数的范围
192                 numerator:      操作数的分子部分
193                 denominator:    操作数的分母部分
194  *
195  * @return      void
196  */
197 void getRandomNum(int &numerator_, int &denominator_, int numRange)
198 {
199     //denominator 分母, numerator 分子
200     if(numRange != 1)
201     {
202         denominator_ = rand() % (numRange-1) + 1; // [1,numRange)
203         numerator_ = rand() % (numRange*denominator_); //[0, numRange*denominator)
204     }
205     else {
206         //范围numRange == 1， 操作数的分子只能为0， 分母设置为1
207         denominator_ = 1;
208         numerator_ = 0;
209     }
210 }
211 
212 /**
213  * @function    为_减法_设置两个符合要求的操作数
214  * @param       num1_numerator:     操作数1的分子
215                 num1_denominator:   操作数1的分母
216                 num2_numerator:     操作数2的分子
217                 num2_denominator:   操作数2的分母
218                 numRange:           操作数的范围
219  *
220  * @return      void
221  */
222 void setNumForSubtraction(int &num1_numerator, int &num1_denominator, int &num2_numerator, int &num2_denominator, int numRange)
223 {
224     double num1, num2;  //num1 - num2
225     do{
226         getRandomNum(num2_numerator, num2_denominator, numRange);
227         num2 = (double)num2_numerator / (double)num2_denominator;
228 
229         getRandomNum(num1_numerator, num1_denominator, numRange);
230         num1 = (double)num1_numerator / (double)num1_denominator;
231 
232     }while(num1 < num2);
233 }
234 
235 /**
236  * @function    为_除法_设置两个符合要求的操作数
237  * @param       num1_numerator:     操作数1的分子
238                 num1_denominator:   操作数1的分母
239                 num2_numerator:     操作数2的分子
240                 num2_denominator:   操作数2的分母
241                 numRange:           操作数的范围
242  *
243  * @return      void
244  */
245 void setNumForDivision(int &num1_numerator, int &num1_denominator, int &num2_numerator, int &num2_denominator, int numRange)
246 {
247     double num1, num2;  //num1 / num2
248     do{
249         num2_denominator = rand() % (numRange-1) + 1;  // [1,numRange)
250         num2_numerator = rand() % (numRange*num2_denominator - 1) + 1; // [1,numRange*num2_denominator) 除号情况除数不能为0这里需要处理
251         num2 = (double)num2_numerator / (double)num2_denominator;
252 
253         getRandomNum(num1_numerator, num1_denominator, numRange);
254         num1 = (double)num1_numerator / (double)num1_denominator;
255     }while(num1 > num2);
256 }

下面是judgeExp.cpp代码：

  1 #include "Myapp.h"
  2 /**
  3  * @function    表达式合法性检测，即能不能计算结果，能计算结果的返回计算结果
  4  * @param       ExpTree:    完整的表达式树
  5                 result:     存储合法表达式计算结果
  6  *
  7  * @return      flag:       当前表达式是否合法的标记
  8  */
  9 Status isLegalExp(BiTree ExpTree, NumInfo& result)
 10 {
 11     int flag = TRUE;
 12     result = getValue(ExpTree, flag, 0);
 13     return flag;
 14 }
 15 
 16 
 17 /**
 18  * @function    计算合法表达式的值，计算方式采用分数形式的计算
 19  * @param       ExpTree:    完整的表达式树
 20                 flag:       实时检测表达式是否合法的标记值
 21                 model:      控制台是否打印计算过程的标记值; 0:不打印计算过程， 1:打印
 22  *
 23  * @return      result:     当前表达式的计算结果
 24  */
 25 NumInfo getValue(BiTree ExpTree, int&flag, int model)
 26 {
 27     if(ExpTree->flag == 1)
 28         return ExpTree->value.numForm;
 29     else {
 30         NumInfo opNum1 = getValue(ExpTree->lchild, flag, model);
 31         NumInfo opNum2 = getValue(ExpTree->rchild, flag, model);
 32         NumInfo result;
 33 
 34         //通分，获得两个操作数分母的最小公倍数
 35         int LCM = findLCM(opNum1.denominator, opNum2.denominator);
 36 
 37         switch(ExpTree->value.opSym)
 38         {
 39             case '+' :  result.denominator = LCM;
 40                         result.numerator = opNum1.numerator*(LCM / opNum1.denominator) + opNum2.numerator*(LCM / opNum2.denominator);
 41                         break;
 42 
 43             case '-' :  result.denominator = LCM;
 44                         result.numerator = opNum1.numerator*(LCM / opNum1.denominator) - opNum2.numerator*(LCM / opNum2.denominator);
 45                         break;
 46 
 47             case '*' :
 48                         result.denominator = opNum1.denominator * opNum2.denominator;
 49                         result.numerator = opNum1.numerator * opNum2.numerator;
 50                         break;
 51 
 52             case '/' :
 53                         if(opNum2.numerator == 0)
 54                             flag = FALSE;
 55                         else {
 56                             result.denominator = opNum1.denominator * opNum2.numerator;
 57                             result.numerator = opNum1.numerator * opNum2.denominator;
 58                         }
 59                         break;
 60             default: ;
 61         }
 62 
 63         if(flag == TRUE)
 64         {
 65             result = simplify(result);
 66             if(model == 1)
 67                 printf("(%d/%d) %c (%d/%d) = %d/%d\n", opNum1.numerator, opNum1.denominator, ExpTree->value.opSym,
 68                                                     opNum2.numerator, opNum2.denominator, result.numerator, result.denominator);
 69         }
 70         else {
 71             result.numerator = 0;
 72             result.denominator = 1;
 73         }
 74         return result;
 75     }
 76 }
 77 
 78 /**
 79  * @function    寻找最大公约数，辗转相除法
 80  * @param       a:  参数1
 81                 b:  参数2
 82  *
 83  * @return      最大公约数
 84  */
 85 int findGCD(int a, int b)
 86 {
 87     if(a == 0)
 88         return b;
 89     return findGCD(b%a, a);
 90 }
 91 
 92 
 93 /**
 94  * @function    寻找最小公倍数，两数积除以最大公约数
 95  * @param       a:  参数1
 96                 b:  参数2
 97  *
 98  * @return      最小公倍数
 99  */
100 int findLCM(int a, int b)
101 {
102     return (a*b)/findGCD(a, b);
103 }
104 
105 
106 /**
107  * @function    化简分子和分母
108  * @param       numForm:    一个用分子/分母表示的数
109  *
110  * @return      afterSim:   化简后的分子/分母表示的数
111  */
112 NumInfo simplify(NumInfo numForm)
113 {
114     NumInfo afterSim;
115     if(numForm.numerator == 0)
116     {
117         afterSim.numerator = 0;
118         afterSim.denominator = 1;
119         return afterSim;
120     }
121 
122     //寻找最大公因数
123     int GCD = findGCD(numForm.denominator, abs(numForm.numerator));
124     afterSim.numerator = numForm.numerator / GCD;
125     afterSim.denominator = numForm.denominator / GCD;
126     return afterSim;
127 }
128 
129 
130 /**
131  * @function    检测当前生成的表达式是否与前面的题目重复
132  * @param       ExpArr:         表达式数组
133                 ExpTree:        当前表达式树
134                 ExpIndex:       表达式数组的最后一个元素的索引
135  *
136  * @return      flag:   当前表达式是否与前面题目重复的标记值  FALSE:不重复,    TRUE:重复
137  */
138 Status isRepetitive(ExpInfoPtr ExpArr, ExpInfo tempExpInfo, int ExpIndex)
139 {
140     int flag = FALSE;
141     int i;
142     int tempExpInfoOpNumCount = tempExpInfo.symCount+1;
143 
144     for(i = 1; i < ExpIndex; i++)
145     {
146         ExpInfo temp = ExpArr[i];
147         //1、比较表达式运算符数量
148         if( tempExpInfo.symCount == temp.symCount )
149             //2、比较表达式结果，分子分母对应相等
150             if( tempExpInfo.result.denominator == temp.result.denominator && tempExpInfo.result.numerator == temp.result.numerator)
151                     //3、比较表达式的运算符数组
152                     if( symArrCmp(tempExpInfo.symArr, temp.symArr, tempExpInfo.symCount) )
153                         //4、比较表达式的操作数数组
154                         if( opNumArrCmp(tempExpInfo.opNumArr, temp.opNumArr, tempExpInfoOpNumCount) )
155                             //5、比较表达式树的结构
156                             if( ExpTreeCmp(tempExpInfo.ExpTree, temp.ExpTree) )
157                             {
158                                 flag = TRUE;
159                                 break;
160                             }
161     }
162     return flag;
163 }
164 
165 
166 /**
167  * @function    检测表达式1的树结构和表达式2是否有重复关系
168  * @param       T1:     表达式树1
169                 T2:     表达式树2
170  *
171  * @return      flag:   表达式1和表达式2是否有重复关系的标记值, FLASE:不重复,    TRUE:重复
172  */
173 Status ExpTreeCmp(BiTree T1, BiTree T2)
174 {
175     if(T1->flag ==  T2->flag){ //结点类型相同
176         if(T1->flag == 1){ //都是操作数结点
177             if(T1->value.numForm.numerator==0 && T2->value.numForm.numerator==0)
178                 return TRUE;
179             else if(T1->value.numForm.numerator == T2->value.numForm.numerator
180                && T1->value.numForm.denominator == T2->value.numForm.denominator)
181                 return TRUE;
182             else
183                 return FALSE;
184         }
185         else if(T1->flag == 0){ //都是操作符结点
186             if(T1->value.opSym != T2->value.opSym)
187                 return FALSE;
188             // 操作符相同才递归比较
189             else{
190                 if(T1->value.opSym == '*' || T1->value.opSym == '+'){
191                     int flag1, flag2;
192                     flag1 = ExpTreeCmp(T1->lchild, T2->lchild) && ExpTreeCmp(T1->rchild, T2->rchild); //比较左左和右右的结果
193                     flag2 = ExpTreeCmp(T1->lchild, T2->rchild) && ExpTreeCmp(T1->rchild, T2->lchild);  // 比较左右和右左的结果
194                     return flag1 || flag2; //其中某一种相同则相同
195                 }
196                 else
197                     return ExpTreeCmp(T1->lchild, T2->lchild) && ExpTreeCmp(T1->rchild, T2->rchild);
198             }
199         }
200     }
201     else
202         return FALSE;
203 
204 }
205 
206 /**
207  * @function    检测运算符数组1和数组2是否有重复关系
208  * @param       arr1:     运算符数组1
209                 arr2:     运算符数组2
210                 length:   数组长度
211  *
212  * @return      flag:   运算符数组1和数组2是否有重复关系的标记值, FALSE:不重复,    TRUE:重复
213  */
214 Status symArrCmp(char* arr1, char* arr2, int length)
215 {
216     //由于是乱序的数组比较，采用辅助标记数组的方式
217     int* flagArr = (int*) malloc(length * sizeof(int));
218     if(!flagArr)
219         return FALSE;
220 
221     int i, j;
222     for(i = 0; i < length; i++)
223         flagArr[i] = 0;
224 
225     for(i = 0; i < length; i++)
226     {
227         for(j = 0; j < length; j++)
228             if(arr1[i] == arr2[j] && flagArr[j] == 0 )
229             {
230                 flagArr[j] = 1;
231                 break;
232             }
233     }
234 
235     for(i = 0; i < length; i++)
236         if(flagArr[i] != 1)
237             return FALSE;
238 
239     return TRUE;
240 }
241 
242 /**
243  * @function    检测操作数数组1和数组2是否有重复关系
244  * @param       arr1:     操作数数组1
245                 arr2:     操作数数组2
246                 length:   数组长度
247  *
248  * @return      flag:     操作数数组1和数组2是否有重复关系的标记值, FALSE:不重复,    TRUE:重复
249  */
250 Status opNumArrCmp(NumInfo* arr1, NumInfo* arr2, int length)
251 {
252     //由于是乱序的数组比较，采用辅助标记数组的方式
253     int* flagArr = (int*) malloc(length * sizeof(int));
254     if(!flagArr)
255         return FALSE;
256 
257     int i, j;
258     for(i = 0; i < length; i++)
259         flagArr[i] = 0;
260 
261     for(i = 0; i < length; i++)
262     {
263         for(j = 0; j < length; j++)
264             if(arr1[i].numerator == arr2[j].numerator &&
265                     arr1[i].denominator == arr2[j].denominator && flagArr[j] == 0)
266             {
267                 flagArr[j] = 1;
268                 break;
269             }
270     }
271 
272     for(i = 0; i < length; i++)
273         if(flagArr[i] != 1)
274             return FALSE;
275 
276     return TRUE;
277 }
278 
279 /**
280  * @function    把当前表达式的基本信息存入表达式数组中
281  * @param       ExpArr:         表达式数组
282                 ExpInfo:        当前表达式的基本信息
283 
284  * @return      void
285  */
286 void addInExpArr(ExpInfoPtr ExpArr, ExpInfo tempExpInfo, int ExpIndex)
287 {
288     ExpArr[ExpIndex].ExpTree = tempExpInfo.ExpTree;
289     ExpArr[ExpIndex].symCount = tempExpInfo.symCount;
290     ExpArr[ExpIndex].symArr = tempExpInfo.symArr;
291     ExpArr[ExpIndex].opNumArr = tempExpInfo.opNumArr;
292     ExpArr[ExpIndex].result = tempExpInfo.result;
293 }
294 
295 
296 /**
297  * @function    获取当前表达式的操作数，并记录在一个数组中
298  * @param       ExpTree:        表达式树
299                 opNumArr:       操作数数组指针
300                 opNumArrIndex:  操作数数组索引
301  *
302  * @return      void
303  */
304 void getOpNumArr(BiTree ExpTree, NumInfo* opNumArr, int& opNumArrIndex)
305 {
306     if(ExpTree->flag == 1)
307         opNumArr[opNumArrIndex++] = ExpTree->value.numForm;
308 
309     else{
310         getOpNumArr(ExpTree->lchild, opNumArr, opNumArrIndex);
311         getOpNumArr(ExpTree->rchild, opNumArr, opNumArrIndex);
312     }
313 }

下面是writeExpAndAnswer.cpp的代码：

  1 #include "Myapp.h"
  2 /**
  3  * @function    比较运算符优先级
  4  * @param       运算符c1, c2
  5  *
  6  * @return      Bool值
  7  */
  8 Status Priority_com(char c1,char c2){
  9     if((c1 == '+' || c1 == '-' || c1 == '*' || c1 == '/') && (c2 == '+' || c2 == '-' || c2 == '*' || c2 == '/'))
 10     {
 11         if(c1 == '*' || c1 == '/')
 12         {
 13             if(c2 == '+' || c2 == '-')
 14                 return TRUE;
 15             else
 16                 return FALSE;
 17         }
 18         else
 19             return FALSE;
 20     }
 21     else
 22         return FALSE;
 23 }
 24 
 25 
 26 /**
 27  * @function    将当前表达式写入题目文件
 28  * @param       T:      表达式树
 29                 file:   题目文件指针
 30  *
 31  * @return      void
 32  */
 33 void writeExp(BiTree T, FILE* file)
 34 {
 35     if(!T)
 36         return;
 37 
 38     if(T->lchild && T->lchild->flag == 0){ //如果根节点与左子树的根节点是运算符
 39         if(Priority_com(T->value.opSym, T->lchild->value.opSym)){
 40             printf("( ");
 41             fprintf(file,"( ");
 42             writeExp(T->lchild, file);
 43             printf(") ");
 44             fprintf(file,") ");
 45         }
 46         else
 47             writeExp(T->lchild, file);
 48     }
 49     else
 50         writeExp(T->lchild, file);
 51 
 52 
 53     if(T->flag == 0){
 54         printf("%c  ",T->value.opSym);
 55         fprintf(file,"%c  ",T->value.opSym);
 56     }
 57     else {
 58         int numerator = T->value.numForm.numerator;
 59         int denominator = T->value.numForm.denominator;
 60 
 61         if(numerator % denominator == 0){ //自然数
 62             printf("%d  ",numerator/denominator);
 63             fprintf(file,"%d  ",numerator/denominator);
 64         }
 65         else{
 66             if(numerator < denominator){ //真分数
 67                 printf("%d/%d  ",numerator,denominator);
 68                 fprintf(file,"%d/%d  ",numerator,denominator);
 69             }
 70             else{ //带分数
 71                 printf("%d\'%d/%d  ",numerator/denominator,numerator%denominator,denominator);
 72                 fprintf(file,"%d\'%d/%d  ",numerator/denominator,numerator%denominator,denominator);
 73             }
 74         }
 75     }
 76 
 77     if(T->rchild && T->rchild->flag == 0){ //如果根节点与右子树的根节点是运算符
 78             printf("( ");
 79             fprintf(file,"(  ");
 80             writeExp(T->rchild, file);
 81             printf(") ");
 82             fprintf(file,")  ");
 83     }
 84     else
 85         writeExp(T->rchild, file);
 86 }
 87 
 88 /**
 89  * @function    将当前表达式写入答案文件
 90  * @param       T:      表达式树
 91                 file:   答案文件指针
 92  *
 93  * @return      void
 94  */
 95 void writeAnswer(NumInfo result, FILE* answerFile)
 96 {
 97     int numerator = result.numerator;
 98     int denominator = result.denominator;
 99     if(numerator % denominator == 0){ //自然数
100         printf("%d\n",numerator/denominator);
101         fprintf(answerFile,"%d\n",numerator/denominator);
102     }
103     else{
104         if(abs(numerator) < abs(denominator)){ //真分数
105             printf("%d/%d\n",numerator,denominator);
106             fprintf(answerFile,"%d/%d\n",numerator,denominator);
107         }
108         else{ //带分数
109             printf("%d\'%d/%d\n",numerator/denominator,abs(numerator)%denominator,denominator);
110             fprintf(answerFile,"%d\'%d/%d\n",numerator/denominator,abs(numerator)%denominator,denominator);
111         }
112     }
113 }

测试运行

项目小结

　　这次项目是结对项目，需要两个人的合作，一个人编码，一个人设计复审，角色轮流交换。每个阶段都有不同的责任，项目采用功能分块，由简入繁的过程开发，还记得最初的版本，只有一个main函数，两个调用的函数，没用命令行，参数固定，再到后面参数改变，不断测试，有时在测试中找到的是之前写的函数的bug，属实尴尬，不过通过不断的代码复审，代码阅读，时常灵光一闪，这段删掉，这段补上，if-else丢得只剩一个，逻辑简化，效果更佳。也有讨论到入夜已深，手机常亮，想法迸发，落魄发现，方案搞笑，打回重想。但是，个中滋味，回味如甘，编码乐趣，在于敲下。

本文链接：https://www.cnblogs.com/cubeCollector/p/12697690.html