| 这个作业属于哪个课程 | 计科22级12班 |
|---|---|
| 这个作业要求在哪里 | |
| 这个作业的目标 | 完成结对项目，合作实现自动生成小学四则运算题目的功能，了解软件开发流程 |
| 姓名 | 学号 | github地址 |
|---|---|---|
| 雷志毅 | 3122004394 | lzy394 |
| 李耿豪 | 3122004395 | SE-test |
一.PSP表格
| PSP2.1 | Personal Software Process Stages | 预估耗时(分钟) | 实际耗时(分钟) |
|---|---|---|---|
| Planning | 计划 | 10 | 15 |
| Estimate | 估计这个任务需要多少时间 | 50 | 60 |
| Development | 开发 | 180 | 210 |
| Analysis | 需求分析 (包括学习新技术) | 15 | 20 |
| Design Spec | 生成设计文档 | 40 | 40 |
| Design Review | 设计复审 | 30 | 30 |
| Coding Standard | 代码规范 (为目前的开发制定合适的规范) | 10 | 10 |
| Design | 具体设计 | 25 | 20 |
| Coding | 具体编码 | 120 | 100 |
| Code Review | 代码复审 | 40 | 30 |
| Test | 测试（自我测试，修改代码，提交修改） | 20 | 30 |
| Reporting | 报告 | 50 | 60 |
| Test Repor | 测试报告 | 30 | 25 |
| Size Measurement | 计算工作量 | 10 | 10 |
| Postmortem & Process Improvement Plan | 事后总结，并提出过程改进计划 | 30 | 30 |
| 合计 | 660 | 690 |
二.效能分析
生成10000道题目的结果和性能分析如下
生成结果：
性能概览：
CPU负载：
内存开销：
可以看到最终使用的内存为21MB左右，CPU负载不超过40%，没有出现内存泄漏和堆栈溢出的情况，也没有出现运行错误。
三.设计实现过程
1.Fraction类
由于生成的运算式是通过真分数进行计算，所以这里设计了一个Fraction类，里面包括分子(numerator)和分母(denominator)，一开始是考虑到带分数前面有整数，还设计了一个系数number作为整数部分，方便输出成字符串，但是考虑到这样设计会其他部分的实现变得更繁杂，就只写了分子和分母两个属性，而在重写toString方法时需要对分数进行化简操作。另外还有RandomFraction方法，用于生成一个随机真分数，其余的就是加减乘除这些基本运算的实现了。
2.BinaryTree类
一开始是打算直接生成表达式，也就是按“数字 运算符 数字 运算符....”生成一个序列，然后再判断是否随机加入括号，但这样设计的话不好实现。在四则运算的题目中，一个运算符一定包含左右两个数字，而表达式的结果一定是一个数字，以1+1为例，‘+’对应着左边的1和右边的1，那怕是带有括号，例如（1+1）+（1+1），它的‘+’也不过是对应着左边的1+1和右边的1+1，可以看到四则运算的表达式具有一定的递归结构，所以我们可以用二叉树来表示一个四则运算的表达式，其中所有叶子节点作为数字，非叶子节点作为运算符。
以下是离散数学课本（314-315页）上对根树与算式（前缀，中缀和后缀）关系的解释：
既然表达式可以用二叉树来表示，那么生成一个表达式的问题就变成了生成一个二叉树的问题，假设生成的表达式中有n个运算符，那么我们就需要生成一个具有2n+1个节点的二叉树，而后对这棵二叉树进行中序遍历就能得到我们平时看到的中缀表达式（可能会有多余的括号）。树的生成是通过一个数组，与堆的建立相似，前n个节点随机生成运算符，后n+1个节点生成随机自然数或真分数，而且依据树来计算表达式的结果更为方便，只需对二叉树进行递归遍历即可。
3.Equation类
这个类是用来记录表达式和对应的计算结果，由于在需求9实际上是对给定的表达式（中缀形式）进行计算，而由一个中缀表达式生成对应的二叉树，一般是通过将表达式转为后缀，再生成对应的节点进行拼接，而要得到结果还要进行递归计算。所以这里的解决方法是得到后缀表达式使用栈来进行结果的计算。对于其他需求则是将BinaryTree类中随机生成的二叉树的中缀表达式和结果存入，但是考虑到符号运算的优先级以及对表达式中可能会有括号，会用SimpleEquation方法将式子化简后存入，Calculate_post方法则是对给定后缀表达式进行计算。
4.FileUtil类
这个类是负责对文件进行读写操作，使用-n和-r命令时将题目和答案写入到指定文件中，使用-e和-a命令则是从文件中读取题目，进行计算后再与答案文件中的结果逐条比对，将对错情况写入到指定文件中。
5.Main类
负责对输入的命令行参数进行处理，并对于不正确的输入方式进行异常处理
总的来说，Main类是整个程序的入口，在输入对应参数后使用FileUtil类的方法进行读写文件，生成题目时从BinaryTree类生成表达式而后将表达式和结果传入到Equation类，再将表达式和结果写入文件；解答题目时从参数中的路径读取文件内容，而后在Equation进行表达式的变换和计算，结果与答案文件的答案比较，将情况通过FileUtil类提供的WriteFile方法写入到指定的文件中，而这些基本计算都要使用到Fraction类的operation方法。
四.代码说明
以下是各个类中的关键方法
1.Fraction类
RandomFraction方法
按照给定的范围生成自然数和真分数，对于超过范围的边界问题进行处理。
点击查看代码
public static Fraction RandomFraction(int max){
int p=(int)(Math.random()*100)+1;
if(p<=75){//75%的概率生成整数
int numerator=(int)(Math.random()*max);
if(numerator==0)
numerator=1;//防止生成0
return new Fraction(numerator,1);
}
else{
int denominator=(int)(Math.random()*max)+1;
if(denominator==max&&denominator!=1)
denominator--;//防止超过范围
int numerator=(int)(Math.random()*denominator*max)+1;//分子范围在1到分母*max之间
return new Fraction(numerator,denominator);
}
}
operation方法
根据运行符号对两个分数进行相应的运算（加，减，乘，除）。
点击查看代码
public static Fraction operation(String operator,Fraction fa,Fraction fb) {//运算
return switch (operator) {
case "+" -> add(fa, fb);//加法
case "-" -> sub(fa, fb);//减法
case "×" -> mul(fa, fb);//乘法
case "÷" -> div(fa, fb);//除法
default -> null;
};
}
2.BinaryTree类
RandomBinaryTree方法
按照符号数量和数值范围随机生成二叉树
点击查看代码
public static BinaryTree RandomBinaryTree(int n,int max) {//随机生成二叉树
if(n==0) return null;
int num=2*n+1;//节点总数
BinaryTree []Node=new BinaryTree[num];//节点数组
for(int i=0;i<num;i++){//初始化
if(i<n) {
int r = (int) (Math.random() * 4);
Node[i] = new BinaryTree(Symbol[r]);//随机生成运算符
}
else{
Node[i]=new BinaryTree(Fraction.RandomFraction(max).toString());//随机生成分数
}
}
for(int i=0;i<n;i++){//连接
if(2*i+1<num) Node[i].setLeft(Node[2*i+1]);//左子树
if(2*i+2<num) Node[i].setRight(Node[2*i+2]);//右子树
}
for(int i=n-1;i>=0;i--){//更改不合理的节点
if(Node[i].getVal().equals("-")) {//减法结果不能为负数
Fraction result=getResult(Node[i]);
if (Fraction.isNegative(result)) {
Swap(Node[i]);
}
if(result.toString().equals("0"))//减法结果不能为0
RandomBinaryTree(n,max);//重新生成
}
if(Node[i].getVal().equals("÷")) {//除法运算符右边不能为0
Fraction result=getResult(Node[i].getRight());
if(Fraction.isNegative(result)||result.toString().equals("0"))//为除法时不能为负数或0
RandomBinaryTree(n,max);//重新生成
}
}
return Node[0];
}
getResult方法
根据给定的二叉树计算表达式的结果
点击查看代码
public static Fraction getResult(BinaryTree T){//计算结果
if(T==null) return null;//空节点
if(T.getLeft()==null && T.getRight()==null){
return new Fraction(T.getVal());//叶子节点
}
Fraction LeftResult=getResult(T.getLeft());
Fraction RightResult=getResult(T.getRight());
if(T.getVal().equals("÷")&& RightResult.toString().equals("0"))
return new Fraction("-1");//返回负数说明计算出错
return Fraction.operation(T.getVal(),LeftResult,RightResult);//递归计算结果
}
3.Equation类
SimEquation方法
对有多余括号的中缀表达式进行去括号的处理
点击查看代码
public static String SimpleEquation(String Expression) {//化简表达式,去括号
StringBuilder result= new StringBuilder();
int[] a=new int[Expression.length()];//记录是否被处理过
for(int i=0;i<Expression.length();i++) {
char c=Expression.charAt(i);
if(a[i]==1) {//如果已经处理过，则跳过
continue;
}
if(c=='(') {//如果遇到左括号，则找到匹配的右括号
boolean tag=true;
if(i>=1) {
if(Expression.charAt(i-1)=='×' || Expression.charAt(i-1)=='÷' ) {//如果左括号前面是×或÷，则不处理
continue;
}
}
int index=i+1;//右括号位置
int count=0;
boolean tag_sub =true;
if(i>=1) {
if(Expression.charAt(i-1)=='-') {//如果左括号前面是-，则括号里有没有+-，有则不处理
tag_sub =false;//括号里没有+-
}
}
while(true) { //找到匹配的右括号
if(!tag_sub && (Expression.charAt(index)=='+'||Expression.charAt(index)=='-')) { //判断左括号是-时，括号里有没有+
tag=false;
break;
}
if(Expression.charAt(index)==')' && count==0) {//找到匹配的右括号
break;
}
if(Expression.charAt(index)=='(') {//如果遇到左括号，则计数加1
count++;
}
if(Expression.charAt(index)==')') {//如果遇到右括号，则计数减1
count--;
}
index++;
}
if(!tag) {//如果括号里有+，则不处理
continue;
}
boolean tag_delete=true;//记录是否删除括号
if(index+1<Expression.length()) {//避免越界
if(Expression.charAt(index+1)=='×' || Expression.charAt(index+1)=='÷') { //判断右括号右边是否有乘除
tag_delete=false;
}
}
if(tag_delete) {//记录删除的括号位置
a[i]=1;
a[index]=1;
}
}
}
for(int i=0;i<Expression.length();i++) {//删除括号
if(a[i]==0) {
result.append(Expression.charAt(i));
}
}
return result.toString();
}
infixToPostfix方法
将中缀表达式转为后缀表达式
点击查看代码
private String infixToPostfix(String infixExpression){
String []Expression=infixExpression.split("\\s+");//按空格划分
StringBuilder result= new StringBuilder();
Stack<String> S=new Stack<>();
for (String s : Expression) {
if(s.equals(" "))
continue;
if (!isSymbol(s)) {//不是符号,直接输出
result.append(s).append(" ");
} else if (s.equals("(")) {//左括号直接入栈
S.push(s);
} else if (s.equals(")")) {//元素出栈直到遇到左括号
while (!S.isEmpty() && !S.peek().equals("(")) {
result.append(S.pop()).append(" ");
}
S.pop();//匹配后的左括号出栈
} else {//按优先级入栈出栈
while (!S.isEmpty() && SymbolPriority(S.peek()) >= SymbolPriority(s)) {
result.append(S.pop()).append(" ");
}
S.push(s);//入栈
}
}
while(!S.isEmpty()) {//栈不空
result.append(S.pop()).append(" ");
}
return result.toString();//输出后缀表达式
}
Calculate_post方法
按后缀表达式计算结果
点击查看代码
private Fraction Calculate_post(String Expression){
String []exp=Expression.split(" ");
Stack<Fraction> S=new Stack<>();
for (String s : exp) {
if (!isSymbol(s)) {
S.push(new Fraction(s));//分数直接入栈
} else {
if (S.size() < 2) {
throw new RuntimeException("后缀表达式异常");
}
Fraction b = S.pop();
Fraction a = S.pop();
S.push(Fraction.operation(s, a, b));//计算结果
}
}
return S.pop();//最终的结果出栈
}
4.FileUtil类
WriteFile方法
主要用于将表达式和结果写入到指定文件中
点击查看代码
public static void WriteFile(String Path,String str) throws IOException {
File f= new File(Path);
if(!f.exists()){//文件不存在
if(!f.createNewFile()){
System.out.println("创建失败");
System.exit(1);
}
}
try{
FileWriter fw=new FileWriter(f,true);
fw.write(str+"\n");//逐行写入文件
fw.close();//关闭文件流
}catch(IOException e){
throw new IOException("写入文件失败");
}
}
ReadFile方法
读取文件中的表达式和结果
点击查看代码
public static void ReadFile(String Path, List<String> list) throws FileNotFoundException {
File f=new File(Path);
if(!f.exists())
throw new RuntimeException("文件不存在");
try {
BufferedReader br = new BufferedReader(new FileReader(f));
String line;
while((line=br.readLine())!=null){//逐行读取文件
int index= line.indexOf(".");
if(line.contains("="))//判断是否为等式
line= line.substring(index+1, line.length()-1);
else
line= line.substring(index+1);
list.add(line.trim());//去除空格，加入到列表中
}
}catch(Exception e){
throw new RuntimeException("读取文件失败");
}
}
5.Main类
generate方法
生成表达式和答案并记录到文件中
点击查看代码
private static void generate(int num,int max) throws IOException {
int i=0;
while(i<num){
int num_Symbol=(int)(Math.random()*3+1);//随机生成1-3个运算符
Equation e=new Equation(num_Symbol,max);//生成表达式
String result=e.getResult().toString();
if(!Result.isEmpty()&&Result.contains(result))
continue;
Result.add(result);//记录结果，防止重复
String questions=(i+1)+". "+e.getinfixExpression()+"=";
result=(i+1)+". "+result;
FileUtil.WriteFile(exercises_filePath,questions);//写入题目
FileUtil.WriteFile(answers_filePath,result);//写入答案
i++;
}
}
Judge方法
判断答案是否与表达式运算的结果一致，并情况写入到文件中
点击查看代码
private static void Judge(String exercises,String answers) throws IOException {
List<String> exerciseList=new ArrayList<>();
List<String> answerList=new ArrayList<>();
FileUtil.ReadFile(exercises,exerciseList);//读取题目
FileUtil.ReadFile(answers,answerList);//读取答案
if(exerciseList.size()!=answerList.size()){
throw new RuntimeException("题目数量与答案数量不一致");
}
boolean []tag=new boolean[exerciseList.size()];//标记答案是否正确
int num=0;//标记正确答案个数
for(int i=0;i<exerciseList.size();i++){//遍历题目
Equation e=new Equation(exerciseList.get(i));
if(e.getResult().toString().equals(answerList.get(i))){//判断答案是否正确
tag[i]=true;
num++;//记录正确的答案个数
}
}
StringBuilder Correct= new StringBuilder("Correct:" + num + "(");
StringBuilder Wrong= new StringBuilder("Wrong:" + (exerciseList.size() - num) + "(");
for(int i=0;i<tag.length;i++){//将正确答案和错误答案情况分别写入文件
if(tag[i])
Correct.append(i + 1).append(",");
else
Wrong.append(i + 1).append(",");
}
if(Correct.charAt(Correct.length()-1)!='(')//去除最后一个逗号
Correct = new StringBuilder(Correct.substring(0, Correct.length() - 1) + ")");
else
Correct.append(")");//补全括号
if(Wrong.charAt(Wrong.length()-1)!='(')//去除最后一个括号
Wrong = new StringBuilder(Wrong.substring(0, Wrong.length() - 1) + ")");
else
Wrong.append(")");//补全括号
FileUtil.WriteFile("Grade.txt", Correct.toString());
FileUtil.WriteFile("Grade.txt", Wrong.toString());
}
五.测试运行
测试的情况包括读取文件是否存在，命令行参数异常还有计算除法时除数是否为0等情况，分为4个测试类。
DemandTest
验证程序能否生成一万道题目，在效能分析时已经进行测试运行，这里不再重复。
点击查看代码
@Test
public void test(){
Main.main(new String[]{"-n","10000","-r","10"});
}
FractionTest
生成的分数分母不能为0，进行除法计算时除数不能为0。
点击查看代码
@Test
public void test1(){//测试分母为0
assertEquals("分母不能为0",
assertThrows(Exception.class, () -> new Fraction(1, 0)).getMessage());
}
@Test
public void test2(){//测试除数为0
assertEquals("除数不能为0",
assertThrows(Exception.class,
()->Fraction.operation("÷",new Fraction("1"),new Fraction("0"))).getMessage());
}
@Test
public void test3(){//测试加法
assertEquals("3",Fraction.operation("+",new Fraction("2"),new Fraction("1")).toString());
}
@Test
public void test4(){//测试减法
assertEquals("1",Fraction.operation("-",new Fraction("2"),new Fraction("1")).toString());
}
@Test
public void test5(){//测试乘法
assertEquals("2",Fraction.operation("×",new Fraction("2"),new Fraction("1")).toString());
}
@Test
public void test6(){//测试除法
assertEquals("1/2",Fraction.operation("÷",new Fraction("1"),new Fraction("2")).toString());
}
测试结果：
EquationTest
验证随机生成的表达式和给定的表达式是否能获得对应的中缀和后缀表示，计算的结果是否正确。
点击查看代码
@Test
public void test1(){//测试随机生成的表达式
Equation e=new Equation(2,5);
System.out.println(e.getinfixExpression());
System.out.println(e.getPostfixExpression());
System.out.println(e.getResult().toString());
}
@Test
public void test2(){//测试自定义的表达式
Equation e=new Equation("1+2+3");
System.out.println(e.getinfixExpression());
System.out.println(e.getPostfixExpression());
System.out.println(e.getResult().toString());
}
测试结果：
MainTest
测试命令行参数以及对于三种命令（-n、-r、-e和-a）的运行情况。
点击查看代码
@Test
public void test1() {
assertEquals("输入的参数个数有误",
assertThrows(Exception.class, ()->Main.main(new String[]{"","",""})).getMessage());
}
@Test
public void test2() {
assertEquals("生成的表达式数量小于等于0",
assertThrows(Exception.class,()->Main.main(new String[]{"-n","0"})).getMessage());
}
@Test
public void test3() {
assertEquals("生成的表达式数量小于等于0",
assertThrows(Exception.class,()->Main.main(new String[]{"-n","-1"})).getMessage());
}
@Test
public void test4() {//不存在文件运行
assertEquals("文件不存在",
assertThrows(Exception.class,()->Main.main(new String[]{"-e","exercisefile1.txt","-a","answersfile1.txt"})).getMessage());
}
@Test
public void test5() {
Main.main(new String[]{"-n","20","-r","10"}); //测试能否正常运行
}
@Test
public void test6() {
Main.main(new String[]{"-e","exercisefile.txt","-a","answersfile.txt"});
}
测试结果：
test5的结果如下（生成了20道题目，题目中每个数字范围都在10以内）：
test6的结果如下（已将第1题和第6题的答案修改为错误答案，其余都为正确答案）：
Grade.txt文件内容：
可以看到运行结果无误，统计的情况符合预期。
六.项目小结
第一次通过结对编程的方式与他人合作完成一个项目，相互监督鼓励，高效率地完成了本次项目，在应对各种需求时双方都会给出自己的想法，然后综合对方的思路分析，及时统一观点，得出高效的解决方案。
开始的时候双方的思路有一定出入以及常用的编程语言不同，后来经过磨合，互相补充对方思路的不足之处，得出了一个较好的设计方案。在编码过程中会遇到许多错误，需要寻找原因，然后融合两个人的解决方法解决程序存在的问题，最终双方合作完成了项目的所有需求。