| 这个作业属于哪个课程 | 软件工程 |
|---|---|
| 这个作业的要求在哪里 | 结对项目 |
| 参与人 | 马楚泽（3121005225），谢剑滔（3121005232） |
PSP表格
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 30 | 30 |
| Estimate | · 估计这个任务需要多少时间 | 525 | 520 |
| Development | 开发 | 60 | 90 |
| Analysis | 需求分析 (包括学习新技术) | 60 | 90 |
| Design Spec | 生成设计文档 | 20 | 15 |
| Design Review | 设计复审 | 20 | 15 |
| Coding Standard | 代码规范 (为目前的开发制定合适的规范) | 20 | 20 |
| Design | 具体设计 | 60 | 60 |
| Coding | 具体编码 | 120 | 160 |
| Code Review | 代码复审 | 20 | 25 |
| Test | 测试（自我测试，修改代码，提交修改） | 30 | 50 |
| Reporting | 报告 | 30 | 50 |
| Test Repor | 测试报告 | 15 | 15 |
| Size Measurement | 计算工作量 | 20 | 15 |
| Postmortem & Process Improvement Plan | 事后总结, 并提出过程改进计划 | 20 | 25 |
| 合计 | 525 | 660 |
效能分析
一万个表达式生成的效能分析，主要使用类有String
设计实现过程
- Create类：
select方法：随机选择生成是整数或真分数的数值；
creatBackExp方法：根据中缀表达式生成后缀表达式。
create方法：调用上面的select和creatBackExp两个方法，依据总结的表达式格式以及中后缀表达式的比较生成不重复的有效表达式 - IOFile类：
writeFile方法:将字符串写入文件；
readFile方法：以字符串形式读取文件内容 - Reverse类：
cal方法：依据中缀转化后缀表达式的方法计算表达式 - main类：
主类，调用create类生成表达式、Reverse类计算结果、使用IOFile类处理文件的输出和读取
代码说明
Create类：
生成表达式
生成题目类我们选择了比较简单粗暴的方法，首先利用随机数选择表达式符号的个数，然后再随机选择表达式的类型，表达式的类型我们分为两种，有括号的和无括号的，有括号又根据括号的位置和多少继续分，表达式的数值和符号都是随机生成的，数值select函数随机生成正数或真分数。这样我们就构造出了所有可能的表达式结果
public String select (int r){//选择生成整数还是分数
String s;
int x,y;
switch ((int)(Math.random()*2+1)){
case 1:s=Integer.toString((int) (Math.random() * r + 1));break;//生成整数
case 2:x=(int)(Math.random()*r+1);//生成真分数
y=(int)(Math.random()*r+1);
if(x<y) { s=x+"/"+y; }
else
s=y+"/"+x;
break;
default:
throw new IllegalStateException("Unexpected value: " + (int) (Math.random() + 1));
}
return s;
}
判断表达式是否相同
表达式实际上可以看作一颗表达式树，中缀实际上就是这棵树的中序遍历。后缀表达式就是这棵树的后序遍历。遍历顺序，意味着计算顺序，由此我们将表达式是否相同的问题转化成表达式树是否相同的问题
那应该如何确定一颗二叉树是否相同呢，这里我们采取的是二叉树的后序遍历+二叉树的中序遍历的比较。当两个表达式中序和后序遍历都不相同时，我们判断这两个表达式不是同一个
//根据中缀生成后缀,利用该方法在create中判断两个表达式是否相同
public static String creatBackExp(String midExp){
List<String> list = new ArrayList<>();
char[] arr = midExp.toCharArray();
//存放数字临时变量
StringBuffer tmpStr = new StringBuffer();
for (char c : arr) {
//如果是数字或小数点，添加到临时变量中
if (c>='0' && c<='9') {
tmpStr.append(c);
}
else if(c=='.') {
tmpStr.append(c);
}
//如果是加减乘除或者括号，将数字临时变量和运算符依次放入List中
else if (c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')') {
if (tmpStr.length() > 0) {
list.add(tmpStr.toString());
tmpStr.setLength(0);
}
list.add(c + "");
}
else if (c==' ') {
continue;
}
}
if (tmpStr.length() > 0) {
list.add(tmpStr.toString());
}
//初始化后缀表达式
List<String> strList = new ArrayList<>();
//运算过程中，使用了两次栈结构，
//第一次是将中缀表达式转换成后缀表达式，第二次是计算后缀表达式的值
Stack<String> stack = new Stack<>();
//声明临时变量，存放栈元素
String tmp;
//将中缀表达式转换成后缀表达式
for (String s : list) {
//如果是左括号直接入栈
if (s.equals("(")) {
stack.push(s);
}
//如果是右括号，执行出栈操作，依次添加到后缀表达式中，直到出栈元素为左括号，左括号和右括号都不添加到后缀表达式中
else if (s.equals(")")) {
while (!(tmp = stack.pop()).equals("(")) {
strList.add(tmp);
}
}
//如果是加减乘除，弹出所遇优先级大于或等于该运算符的栈顶元素（栈中肯定没有右括号，认为左括号的优先级最低），然后将该运算符入栈
else if (s.equals("*") || s.equals("/")) {
while(!stack.isEmpty()) {
//取出栈顶元素
tmp = stack.peek();//取出但不移除
if (tmp.equals("*") || tmp.equals("/")) {
stack.pop();
strList.add(tmp);
}
else {
break;
}
}
stack.push(s);
}
else if (s.equals("+") || s.equals("-")) {
while(!stack.isEmpty()) {
//取出栈顶元素
tmp = stack.peek();
if (!tmp.equals("(")) {
stack.pop();
strList.add(tmp);
}
else {
break;
}
}
stack.push(s);
}
//如果是数字，直接添加到后缀表达式中
else {
strList.add(s);
}
}
//最后依次出栈，放入后缀表达式中
while (!stack.isEmpty()) {
strList.add(stack.pop());
}
//List<String>转换成String
StringBuffer backExp=new StringBuffer();
//转化成字符串
for (String s : strList){
backExp.append(s);
}
return backExp.toString();
}
reverse类：
这个类的功能是对Create传过来的表达式进行处理，将表达式的中缀转化成后缀，因为中缀虽然方便人们计算，但是对于计算机而言，每次计算需要判断整个表达式中运算符的优先级，复杂度太高。中缀转成后缀的计算方式就可以仅通过两次遍历就可以完成表达式的计算。
中缀转化后缀思路
-
从左到右依次扫描中缀表达式，如果读到的是操作数，直接存入 exp 栈
-
如果读到的是运算符，则进行判断
该运算符是 ’ ( '，则直接存入 opt 栈
该运算符是 ’ ) '，则将 opt 栈中对应 ‘(’ 前的所有运算符出栈，存入 exp 栈（这一对括号就可以直接舍弃了） -
如果该运算符不是括号，则将该运算符和 opt 栈顶运算符做比较
- 优先级大于或等于 opt 栈顶运算符，则直接存入 opt 栈
- 优先级小于 opt 栈顶运算符，则让 opt 栈顶运算符出栈并存入 exp 栈中。如果此时新的栈顶运算符优先级大于等于该运算符，继续让栈顶运算符出栈存入exp栈。最后再将该运算符存入 opt 栈
-
当扫描完成后，opt 栈中还有运算符，则将 opt 所有运算符出栈，存入 exp 栈中
public static String cal(String str) {
//中缀转化后缀
List<String> list = new ArrayList<>();
char[] arr = str.toCharArray();
//存放数字临时变量
StringBuffer tmpStr = new StringBuffer();
for (char c : arr) {
//如果是数字或小数点，添加到临时变量中
if (c>='0' && c<='9') {
tmpStr.append(c);
}
else if(c=='.') {
tmpStr.append(c);
}
//如果是加减乘除或者括号，将数字临时变量和运算符依次放入List中
else if (c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')'||c=='÷') {
if (tmpStr.length() > 0) {
list.add(tmpStr.toString());
tmpStr.setLength(0);
}
list.add(c + "");
}
else if (c==' ') {
continue;
}
}
if (tmpStr.length() > 0) {
list.add(tmpStr.toString());
}
//初始化后缀表达式
List<String> strList = new ArrayList<>();
//运算过程中，使用了两次栈结构，
//第一次是将中缀表达式转换成后缀表达式，第二次是计算后缀表达式的值
Stack<String> stack = new Stack<>();
//声明临时变量，存放栈元素
String tmp;
//将中缀表达式转换成后缀表达式
for (String s : list) {
//如果是左括号直接入栈
if (s.equals("(")) {
stack.push(s);
}
//如果是右括号，执行出栈操作，依次添加到后缀表达式中，直到出栈元素为左括号，左括号和右括号都不添加到后缀表达式中
else if (s.equals(")")) {
while (!(tmp = stack.pop()).equals("(")) {
strList.add(tmp);
}
}
//如果是加减乘除，弹出所遇优先级大于或等于该运算符的栈顶元素（栈中肯定没有右括号，认为左括号的优先级最低），然后将该运算符入栈
else if (s.equals("*") || s.equals("/")||s.equals("÷")) {
while(!stack.isEmpty()) {
//取出栈顶元素
tmp = stack.peek();//取出但不移除
if (tmp.equals("*") || tmp.equals("/")||tmp.equals("÷")) {
stack.pop();
strList.add(tmp);
}
else {
break;
}
}
stack.push(s);
}
else if (s.equals("+") || s.equals("-")) {
while(!stack.isEmpty()) {
//取出栈顶元素
tmp = stack.peek();
if (!tmp.equals("(")) {
stack.pop();
strList.add(tmp);
}
else {
break;
}
}
stack.push(s);
}
//如果是数字，直接添加到后缀表达式中
else {
strList.add(s);
}
}
//最后依次出栈，放入后缀表达式中
while (!stack.isEmpty()) {
strList.add(stack.pop());
}
后缀计算思路
-
建立一个空栈 stack。
-
遍历后缀表达式（此后将遍历到的字符称为 s）。
-
当 s 为数字时，将其压入 stack 栈。
-
当 s 为运算符时，弹出 stack 栈顶和次栈顶的两个数字，并将两个数字按照运算符 s 进行运算，然后将运算结果压入stack 栈 。
-
当遍历结束时，存留在栈 stack 中还剩下唯一一个数字，该数字便是运算结果。
//计算后缀表达式的值
Stack<BigDecimal> newStack = new Stack<>();
for (String s : strList) {
//若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的放到运算符的左边
//运算后的结果再进栈，直到后缀表达式遍历完毕
if (s.equals("*") || s.equals("/") || s.equals("+") || s.equals("-")||s.equals("÷")) {
BigDecimal b1 = newStack.pop();
BigDecimal b2 = newStack.pop();
switch (s) {
case "+":
newStack.push(b2.add(b1));
break;
case "-":
newStack.push(b2.subtract(b1));
break;
case "*":
newStack.push(b2.multiply(b1));
break;
case "/":
newStack.push(b2.divide(b1, 2, BigDecimal.ROUND_HALF_UP));
break;
case "÷":
newStack.push(b2.divide(b1, 2, BigDecimal.ROUND_HALF_UP));
break;
}
}
//如果是数字，入栈
else {
newStack.push(new BigDecimal(s));
}
}
//栈中仅有一个元素，返回计算结果
return newStack.peek().toString();
测试运行
10道十以内的题目运行（命令行）
- 题目表达式
- 正确答案--我的答案（对比）
- 输出成绩
10000道十以内的题目运行（命令行）
- 题目表达式
- 正确答案--我的答案（对比）
- 输出成绩
项目小结
对于本次结对项目的体验总结主要为团队协作和任务分工
- 团队协作：通过两人结对完成同个项目，能初步感受到团队协作的魅力，我们可以相互沟通交流，分享自己对项目的看法和见解，不断完善计划，选出最优方案，完成项目过程中出现问题，可以向对方寻求帮助，可以更好的解决问题，完善项目，沟通交流的过程也能互相提升。当然，我们还要尽力去配合对方，相互适应。
- 任务分工：每个人对编程的掌握熟练程度不同，擅长的地方也不同，通过合理的分配任务，才能更好的提高开发效率和编码质量，同时让每个人都参与到其中。