一、GitHub地址：https://github.com/qq544279946/second_homework
二、 PSP2.1表格
PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
Planning | 计划 | 45 | 40 |
· Estimate | · 估计这个任务需要多少时间 | 45 | 40 |
Development | 开发 | 1100 | 1230 |
· Analysis | · 需求分析 (包括学习新技术) | 180 | 150 |
· Design Spec | · 生成设计文档 | 70 | 60 |
· Design Review | · 设计复审 (和同事审核设计文档) | 50 | 40 |
· Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 40 | 30 |
· Design | · 具体设计 | 120 | 100 |
· Coding | · 具体编码 | 500 | 700 |
· Code Review | · 代码复审 | 50 | 60 |
· Test | · 测试（自我测试，修改代码，提交修改） | 90 | 90 |
Reporting | 报告 | 130 | 130 |
· Test Report | · 测试报告 | 50 | 60 |
· Size Measurement | · 计算工作量 | 40 | 30 |
· Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 40 | 40 |
合计 | 1275 | 1400 |
三、效能分析
改进后的算法：我实现生成随机运算表达式和答案的算法用了0.437秒生成由0-100生成的自然数和真分数组成的10000道不相同的运算式，
生成100万道题用时24.36秒
在查式子重复性的时候，我是想到把式子的字符串分成各个运算过程中产生的子表达式字符串，并把子表达式按序进入一个列表里，然后与其他已生成的所以算术表达式进行对比。
第一个实现版本：
我刚开始时是：
①遍历算术表达式，判断到第一个括号的范围，就把那个括号的子表达式字符串放进列表里
②如果在遍历过程中遇到括号，把括号子表达式的运算值替换掉括号形成新的算术表达式，重新遍历新的算术表达式，直到表达式里没有括号为止。
③算术表达式里没有括号，就把最后的算术表达式运算生成的子表达式放进列表里。
④把这个列表 和 之前已经生成的算术表达式的所有列表按顺序进行比较，相同就抛弃，不相同，就加入到列表组里。
改进版本实现：
①我先把算术表达式的字符串转换成后缀表达式，然后根据逆波兰算法，在运算子表达式的时候把每一个子表达式设置成一个结点，根据运算的过程生成一棵由子表达式生成的二叉树。
②把这棵二叉树和之前生成的所有树进行递归比较，相同就抛弃，不相同就加入二叉树组里。
两个版本的效能对比：
进行加法和乘法的判断时，我规定了小的数为x，大的数为y，
我的第一个版本在这两个运算时，当要交换x 和 y 时，交换该子表达式的x和y的位置，还需要交换对应的两个子表达式在列表中的位置，所以比较麻烦。
我的改进版本的实现只需要在要交换一个子表达式中的x和y位置时，因为是一棵数，所以只需要交换两个子树x结点 和 y结点的位置就可以了，省去了交换对应的两个子表达式在列表中的位置的时间。
四、设计实现过程：
流程图
我这个程序，主要由View类，Create类，Expression类，Calculate类，Number类，CheckTheAnswer类，和两个异常类。
其中，我的View类主要是用来接收命令行参数，输入错误时，返回信息提醒，参数格式规范正确就调用Create类的creator（）生成算术表达式然后调用Expression类的getResult()方法。
getResult()方法是把算术表达式的字符串转换成后缀表达式，并返回一棵以Number为结点的二叉树，其中Number类{Number x，Number y，String z，String op}用来保存子表达式。
CheckTheAnswer类主要用于输入表达式和答案文本文件路径，生成Grade的成绩文本文件。这个类只有一个check（）方法，这个方法会调用Expression，Calculate，Number类来计算算术表达式的答案和用户的答案。
五、代码说明
1.数字类
①这个类是用来存储运算过程中产生的子表达式，并且这些表达式随着运算的过程组成一棵二叉树，其中结点的x的int值 < y的int值。
②这个类还有一个通过递归来判断判断两棵树是否相同的方法isExpressionEqual（）；
public class Number {
//算术运算符
private String op;
//运算的操作数
private Number x;
private Number y;
//运算结果z
private String z;
public Number(String op, Number x, Number y, String z) {
super();
this.op = op;
this.x = x;
this.y = y;
this.z = z;
}
public String toString() {
return z;
}
/**
* 判断两个结点Node的值是否相等
* @param other Number 另一个结点
* @return true 相等 false 不相等
*/
public boolean isEqual(Number other) {
if(x.toString().equals(other.x.toString())
&& y.toString().equals(other.y.toString())
&& op.toString().equals(other.op.toString()))
return true;
return false;
}
/**
* 遍历整棵树的递归方法
*/
public void foreach() {
foreachInner(this);
}
/**
* 遍历的内部方法
* @param n Number 要遍历的结点
*/
private void foreachInner(Number n) {
if(n.op == null) {
return;
}
foreachInner(n.x);
foreachInner(n.y);
System.out.println(n.x.toString() + n.op + n.y.toString() + "=" + n.z);
}
/**
* 遍历整棵二叉树，判断两颗树是否相等（判断两个运算表达式是否相等）
* @param root1 Number 表达式1
* @param root2 Number 表达式2
* @return Boolean true 相同 false 不相同
*/
public static boolean isExpressionEqual(Number root1, Number root2) {
if(root1.op == null && root2.op != null)
return false;
if(root1.op != null && root2.op == null)
return false;
if(root1.op == null && root2.op == null)
return true;
if(!root1.isEqual(root2))
return false;
return isExpressionEqual(root1.x,root2.x) && isExpressionEqual(root1.y,root2.y);
}
} 2.生成中序表达式的类
①createExpression（），生成表达式主要是通过递归的方式生成，其中n为1-3的随机整数，用来决定生成的运算符数目。
②createNumber（int r），一个随机生成自然数和分数的方法，r是数字的范围。
/**
* 这个类用于生成一个字符串表示的一个算术表达式，只有一个对外的getCreate（）对外创建Create类和
* 唯一一个一个对外生成表达式的方法
* @author sjx
*
*/
public class Create {
private int n = 0;
private int numberOfExpression;
private int rangeOfNumber ;
private Create(int numberOfExpression, int rangeOfNumber) {
super();
this.numberOfExpression = numberOfExpression;
this.rangeOfNumber = rangeOfNumber;
}
/**
* 生成Create类
* @param numberOfExpression int 表达式的数目
* @param rangeOfNumber int 数的范围
* @return Create 返回Create的实例对象
*/
public static Create getCreate(int numberOfExpression, int rangeOfNumber) {
return new Create(numberOfExpression, rangeOfNumber);
}
public void createExpression() throws FileNotFoundException {
PrintStream ps = new PrintStream("C:/Users/Administrator/Desktop/exercisefile.txt");
PrintStream ps2 = new PrintStream("C:/Users/Administrator/Desktop/answerfile.txt");
ArrayList<Number> list = new ArrayList<>();
for(int i = 0;i < numberOfExpression; ) {
String exp = creator();
Expression e = new Expression(exp);
try {
Number n1 = e.getResult();
boolean isEqual = false;
for (Number n : list) {
if(Number.isExpressionEqual(n1, n)) {
isEqual = true;
break;
}
}
if(!isEqual) {
//输出式子
ps.println(i+1 + ". " + exp + " = ");
ps2.println(i+1 + ". " + n1.toString());
//System.out.println(i+1 + ": " + exp);
i++;
}
} catch (Exception e1) {
//System.out.println(e1.getMessage());
}
}
ps.close();
}
/**
*
* @return String 算数运算表达式
*
*/
private String creator() {
Random r = new Random();
int time = r.nextInt(3) + 1;
String expression = creatorInner(time);
n = 0;
return expression;
}
/**
*
* @param time int 运算符的个数为随机的1-3个
* @return String 子表达式
*
*/
private String creatorInner(int time) {
if(n == time) {
//return (int)(Math.random() * 11) + "";
return createNumber(rangeOfNumber);
}
//return "n";
Random r = new Random();
int chose = r.nextInt(8);
if(chose >= 4 && n ==0)
chose = r.nextInt(4);
switch(chose) {
case 0:
n++;
return creatorInner(time) + " + " +creatorInner(time);
case 1:
n++;
return creatorInner(time) + " - " +creatorInner(time);
case 2:
n++;
return creatorInner(time) + " × " +creatorInner(time);
case 3:
n++;
return creatorInner(time) + " ÷ " +creatorInner(time);
case 4:
n++;
return "(" + creatorInner(time) + " + " +creatorInner(time) + ")";
case 5:
n++;
return "(" + creatorInner(time) + " - " +creatorInner(time) + ")";
case 6:
n++;
return "(" + creatorInner(time) + " × " +creatorInner(time) + ")";
case 7:
n++;
return "(" + creatorInner(time) + " ÷ " +creatorInner(time) + ")";
}
return null;
}
private String createNumber(int bound){
Random r = new Random();
int choose = r.nextInt(6);
switch(choose) {
case 0:
case 1:
case 2:
case 3:
return r.nextInt(bound+1) + "";
case 4:
int fenMu = (int)Math.round((bound - 2) * Math.random()) + 2;
int fenZi = (int) (Math.round((fenMu - 2) * Math.random()) + 1 );
return fenZi + "/" + fenMu;
case 5:
fenMu = (int)Math.round((bound - 2) * Math.random()) + 2;
fenZi = (int) ((fenMu - 2) * Math.random() + 1 );
int jiaShu = r.nextInt(bound - 1 ) + 1;
return jiaShu + "'" + fenZi + "/" + fenMu;
}
return null;
}
}3.Expression类
①这个类可以用toRight（）方法转成后缀表达式
②调用Calculate类的计算方法（下面介绍），并把子表达式转成Number结点构成树
/**
* 该类用于将表达式的字符串形式转换成逆波兰算法的后缀表达式，输入表达式，得到一棵存储了运算过程中生成的子式的二叉树。
* @author sjx
*
*/
public class Expression {
private ArrayList<String> expression = new ArrayList<>();//存储中序表达式
private ArrayList<String> right = new ArrayList<>();// 存储右序表达式
private Number result;// 结果
// 依据输入信息创建对象，将数值与操作符放入ArrayList中
public Expression(String input) {
String left = input.replaceAll("\\(", "( ").replaceAll("\\)", " )");
String[] strs = left.split(" ");
for (String s : strs) {
expression.add(s);
}
}
// 将中序表达式转换为右序表达式
private void toRight() {
Stack<String> aStack = new Stack<>();
String operator;
int position = 0;
while(true) {
if(Calculate.isOperator(expression.get(position))) {
if(aStack.isEmpty() || expression.get(position).equals("(")) {
aStack.push(expression.get(position));
}else {
if(expression.get(position).equals(")")) {
while(true) {
if(!aStack.isEmpty() && !aStack.peek().equals("(")) {
operator = aStack.pop();
right.add(operator);
}else {
if(!aStack.isEmpty())
aStack.pop();
break;
}
}
}else {
while(true) {
if(!aStack.isEmpty()
&& Calculate.priority(expression.get(position))
<= Calculate.priority(aStack.peek())) {
operator = aStack.pop();
if (!operator.equals("("))
right.add(operator);
}else{
break;
}
}
aStack.push(expression.get(position));
}
}
}else
right.add(expression.get(position));
position++;
if(position >= expression.size())
break;
}
while(!aStack.isEmpty()) {
operator = aStack.pop();
if(!operator.equals("("))
right.add(operator);
}
}
/**
* 调用该方法来获得子表达式构成的一棵二叉树
* @return Number 二叉树
* @throws ExpressionException 计算算术表达式时出现的算术异常
*/
public Number getResult() throws ExpressionException {
this.toRight();
Stack<Number> aStack = new Stack<>();
Number op1, op2 = null;
for (String is : right) {
if(Calculate.isOperator(is)) {
op1 = aStack.pop();//y
op2 = aStack.pop();//x
aStack.push(Calculate.twoResult(is, op1, op2));
}else
aStack.push(new Number(null,null,null,is));
}
result = aStack.pop();
//System.out.println("********************************************");
//result.foreach();
return result;
}
}4.Calculate计算类
①把两个Number结点传入进行计算。
②计算是先判断是否为分数，是，通分再用处理分数的方法计算，否，直接自然数计算
③在这里规定＋×运算的结点x的值 < y的值，便于查重。
④在遇到 x - y < 0 或 ÷ 0 时 抛出ExpressionException异常。
/**
* 这个类封装了关于两个数计算，判断运算符号优先级，对一个数进行通分的方法
* @author sjx
*
*/
public class Calculate {
//判断是否为操作符
public static boolean isOperator(String operator) {
if (operator.equals("+") || operator.equals("-")
|| operator.equals("×") || operator.equals("÷")
|| operator.equals("(") || operator.equals(")"))
return true;
else
return false;
}
// 设置操作符号的优先级别
public static int priority(String operator) {
if (operator.equals("+") || operator.equals("-"))
return 1;
else if(operator.equals("×") || operator.equals("÷"))
return 2;
else
return 0;
}
// 做2值之间的计算
public static Number twoResult(String operator, Number aa, Number bb) throws ExpressionException {
String a = aa.toString();
String b = bb.toString();
String op = operator;
String z;
//有真分数的表达式和自然数的表达式分开处理运算
if(a.contains("/") || b.contains("/")) {
String x = tongFen(b);
String y = tongFen(a);
String[] xs = x.split("/");
String[] ys = y.split("/");
int xFenZi = Integer.parseInt(xs[0]);
int xFenMu = Integer.parseInt(xs[1]);
int yFenZi = Integer.parseInt(ys[0]);
int yFenMu = Integer.parseInt(ys[1]);
int zFenZi = 0;
int zFenMu = 0;
if(op.equals("+")) {
zFenZi = xFenZi * yFenMu + yFenZi * xFenMu;
zFenMu = xFenMu * yFenMu;
if(xFenZi * yFenMu > yFenZi * xFenMu) {
z = resultTongFen(zFenZi, zFenMu);
return new Number(op, aa, bb, z);
}
}else if(op.equals("-")) {
zFenZi = xFenZi * yFenMu - yFenZi * xFenMu;
zFenMu = xFenMu * yFenMu;
if(zFenZi < 0)
throw new ExpressionException("x - y < 0");
}else if(op.equals("×")) {
zFenZi = xFenZi * yFenZi;
zFenMu = xFenMu * yFenMu;
if(xFenZi * yFenMu > yFenZi * xFenMu) {
z = resultTongFen(zFenZi, zFenMu);
return new Number(op, aa, bb, z);
}
}else if(op.equals("÷")) {
//数为0/1情况讨论
if(yFenZi == 0)
throw new ExpressionException("/Zero");
zFenZi = xFenZi * yFenMu;
zFenMu = xFenMu * yFenZi;
}
z = resultTongFen(zFenZi, zFenMu);
return new Number(op, bb, aa, z);
}
int x = Integer.parseInt(b);
int y = Integer.parseInt(a);
if(op.equals("+")) {
z = x + y + "";
if(x > y) {
return new Number(op, aa, bb, z);
}
}
else if(op.equals("-")) {
if(x - y < 0)
throw new ExpressionException("x - y < 0");
z = x - y + "";
}
else if(op.equals("×")) {
z = x * y + "";
if(x > y) {
return new Number(op, aa, bb, z);
}
}
else if(op.equals("÷")) {
if(y == 0)
throw new ExpressionException("/Zero");
z = resultTongFen(x,y);
}
else
z = "0";
return new Number(op, bb, aa, z);
}
private static String tongFen(String n) {
if(n.matches("-?\\d+"))
n = n + "/1";
if(n.contains("'")) {
String[] ns = n.split("'|/");
int pang = Integer.parseInt(ns[0]);
int fenZi = Integer.parseInt(ns[1]);
int fenMu = Integer.parseInt(ns[2]);
fenZi = fenZi + fenMu * pang;
return fenZi + "/" + fenMu;
}
return n;
}
private static String resultTongFen(int fenzi, int fenmu) {
int pang = fenzi / fenmu;
fenzi = fenzi % fenmu;
int x = fenmu;
int y = fenzi;
//分子为0的情况
if(fenzi == 0)
return pang + "";
int i = x % y;
while(i!=0){
x = y;
y = i;
i = x % y;
}
fenzi = fenzi / y;
fenmu = fenmu / y;
if(pang == 0) {
return fenzi + "/" + fenmu;
}else
return pang + "'" + fenzi + "/" + fenmu;
}
}5.检查答案的类
①这个类主要还是根据路径一行行传入表达式和用户答案，表达式还是一样通过上面方法计算出答案，然后和用户答案对比
②对答案的前提是题号要一致，不一致的话，会选下一题的题号对比，直到题号相同为止。
③答案对错，直接定义变量统计数目。
/**
* 该类只有一个静态方法check()，来检查答案的对错
* @author sjx
*
*/
public class CheckTheAnswer {
/**
* 根据给定的题目路径 和 答案的文件路径 生成一个 检查答案对错后的成绩文本文件
* @param exercisefile String 算术表达式文件路径
* @param answerfile String 答案文档目录
* @throws Exception 文件IO异常
*/
public static void check(String exercisefile, String answerfile) throws Exception {
int correct = 0;
int wrong = 0;
boolean flagOfLine2 = true;
ArrayList<String> correctList = new ArrayList<>();
ArrayList<String> wrongList = new ArrayList<>();
try (BufferedReader br1 = new BufferedReader(new FileReader(exercisefile));
BufferedReader br2 = new BufferedReader(new FileReader(answerfile));
PrintStream ps = new PrintStream("C:/Users/Administrator/Desktop/Grade.txt")){
String line1;
String line2 = null;
while((line1 = br1.readLine()) != null) {
String[] exerSplit = line1.split("\\.");
String labelOfExer = exerSplit[0];
String exer = exerSplit[1].replaceAll("=","").trim();
Expression exp = new Expression(exer);
Number answ = exp.getResult();
if(flagOfLine2) {
line2 = br2.readLine();
}
if(line2 == null) {
break;
}
String[] answSplit = line2.split("\\.");
String labelOfUserAnswer = answSplit[0];
String userAnswer = answSplit[1].trim();
if(!labelOfExer.equals(labelOfUserAnswer) ) {
flagOfLine2 = false;
continue;
}
if(answ.toString().equals(userAnswer)) {
correct++;
correctList.add(labelOfUserAnswer);
flagOfLine2 = true;
}else {
wrong++;
wrongList.add(labelOfUserAnswer);
flagOfLine2 = true;
}
}
int i;
ps.print("Correct: " + correct + "(");
for(i = 0; i < correctList.size(); i++) {
if(i <= correctList.size() - 2)
ps.print(correctList.get(i) + ", ");
else
ps.print(correctList.get(i) + ")");
}
if(i == 0)
ps.print(")");
ps.println();
ps.print("Wrong: " + wrong + "(");
for(i = 0; i < wrongList.size(); i++) {
if(i <= wrongList.size() - 2)
ps.print(wrongList.get(i) + ", ");
else
ps.println(wrongList.get(i) + ")");
}
if(i == 0)
ps.print(")");
ps.println();
}
}
}六、测试运行
测试10000道题目 -n 10000 -r 100
测试检查答案的功能：
这里我随机挑选了刚刚生成的answer.txt中的一些答案，并把两个答案修改成错误的。
测试结果如下：
七、项目小节
在这次的结对编程中，我发现两个人一起讨论改进算法的实现比一个人独自想的效率更高，而且两个人一起进行项目的开发消耗的时间也大大提高了，而且准确率也提升了上来。可以说结对编程在一些情况下是十分有意义的一个开发流程。