------------恢复内容开始------------
| 这个作业属于哪个课程 | 软件工程 |
|---|---|
| 这个作业要求在哪里 | 作业要求 |
| 这个作业的目标 | 四则运算 |
PSP表格
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 40 | 30 |
| Estimate | 估计这个任务需要多少时间 | 10 | 10 |
| Development | 开发 | 300 | 300 |
| Analysis | 需求分析 (包括学习新技术) | 120 | 180 |
| Design Spec | 生成设计文档 | 20 | 20 |
| Design Review | 设计复审 | 20 | 30 |
| Coding Standard | 代码规范 (为目前的开发制定合适的规范) | 10 | 10 |
| Design | 具体设计 | 40 | 3 |
| Coding | 具体编码 | 240 | 240 |
| Code Review | 代码复审 | 60 | 30 |
| Test | 测试（自我测试，修改代码，提交修改） | 60 | 50 |
| Reporting | 报告 | 90 | 120 |
| Test Repor | 测试报告 | 20 | 20 |
| Size Measurement | 计算工作量 | 20 | 10 |
| Postmortem & Process Improvement Plan | 事后总结, 并提出过程改进计划 | 60 | 70 |
| 合计 | 1110 | 1150 |
算术表达式使用递归算法生成二叉树
代码的核心思想是：找到表达式中最后使用的操作符，作为二叉树根节点，左侧右侧递归生成的二叉树分别为左孩子和右孩子
那关键是：找表达式中最后使用的操作符
算数表达式的计算顺序: 先括号 先乘除 后加减 加减运算以及乘除运算都是从左到右
1. #include <iostream>
2. #define MAXSIZE 1000
3.
4. using namespace std;
5.
6. //二叉树结点结构体定义
7. typedef struct BtreeNode{
8. char data;
9. struct BtreeNode *lchild;
10. struct BtreeNode *rchild;
11. }BtreeNode;
12.
13. //算术表达式转化二叉树
14. /*
15. afa为指向表达式字符串的指针
16. s为要转化的表达式字符串的起始位置
17. e为要转化的表达式字符串的结束位置的后一个
18. */
19. BtreeNode* afaToBtree(char *afa,int s,int e){
20. //如果只有一个数那就是叶子结点了
21. if(e-s==1)
22. {
23. BtreeNode* bn=(struct BtreeNode*)malloc(sizeof(struct BtreeNode));
24. bn->data=afa[s];
25. bn->lchild=NULL;
26. bn->rchild=NULL;
27. return bn;
28. }
29. /*
30. local_r记录当前要转化的表达式生成二叉树的根节点操作符的位置
31. flag记录是否当前搜索在括号里面
32. m_m_p记录当前表达式中括号外面最右边的+、-位置
33. a_s_p记录当前表达式中括号外面最右边的*、/位置
34. */
35. int local_r=0,flag=0;
36. int m_m_p=0,a_s_p=0;
37. for(int i=s;i<e;i++)
38. {
39. if(afa[i]=='(')flag++;
40. else if(afa[i]==')')flag--;
41. if(flag==0){
42. if(afa[i]=='*'||afa[i]=='/')
43. m_m_p=i;
44. else if(afa[i]=='+'||afa[i]=='-')
45. a_s_p=i;
46. }
47. }
48. if((m_m_p==0)&&(a_s_p==0))
49. //如果式子整个有括号如(5-2*3+7)，即括号外面没有操作符，则去掉括号找二叉树
50. afaToBtree(afa,s+1,e-1);
51. else
52. {
53. //如果有+或者-，则根节点为最右边的+或-，否则是最右边的*或/
54. if(a_s_p>0)local_r=a_s_p;
55. else if(m_m_p>0)local_r=m_m_p;
56. //确定根节点和根节点的左孩子和右孩子
57. BtreeNode* b=(struct BtreeNode*)malloc(sizeof(struct BtreeNode));;
58. b->data=afa[local_r];
59. b->lchild=afaToBtree(afa,s,local_r);
60. b->rchild=afaToBtree(afa,local_r+1,e);
61. return b;
62. }
63. }
64.
65. void main(){
66.
67. char input[MAXSIZE];
68. int len=0;
69. //初始化
70. memset(input,'\0',sizeof(input));
71.
72. cin >> input ;
73.
74. BtreeNode* myBtree=(struct BtreeNode*)malloc(sizeof(struct BtreeNode));
75.
76. //myBtree就是input算术表达式产生的二叉树的根节点(指针类型哦)
77.
78. myBtree=afaToBtree(input,0,strlen(input));
79.
80. }
用后缀表达式进行运算
建立一个栈S 。从左到右读表达式，如果读到操作数就将它压入栈S中，如果读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作符运算，再将运算的结果代替原栈顶的n项，压入栈S中 。如果后缀表达式未读完，则重复上面过程，最后输出栈顶的数值则为结束
先将前面的数字入栈
栈 :6 5 2 3
遇到 ” + ” 取栈顶的两个操作数做加法, 2 + 3 = 5 , 入栈
栈 :6 5 5
遇到 ” 8 ” 入栈
栈 :6 5 5 8
遇到 ” * ” 取栈顶的两个操作数做乘法, 5 * 8 = 40 , 入栈
栈 :6 5 40
遇到 ” + ” 取栈顶的两个操作数做加法, 5 + 40 = 45 , 入栈
栈 :6 45
遇到 ” 3 ” 入栈
栈 :6 45 3
遇到 ” + ” 取栈顶的两个操作数做加法, 45 + 3 = 48 , 入栈
栈 :6 48
遇到 ” * ” 取栈顶的两个操作数做加法, 6 * 48 = 288 , 入栈
栈 :288
具体代码如下
1. lass Calculation:
2. def eval(op, a, b): # 当只有一个操作符的计算
3. answer = 0
4. if op == "+":
5. answer = operator.add(a, b)
6. elif op == "-":
7. if operator.lt(a, b): # a是否小于b
8. raise NegativeError() # 当被减数大于减数的时候，抛出异常
9. else:
10. answer = operator.sub(a, b)
11. elif op == "*":
12. answer = operator.mul(a, b)
13. elif op == "/":
14. answer = operator.truediv(a, b)
15. if isinstance(answer, float): # 当答案为浮点数，转换为分数
16. answer = operator.truediv(Fraction(a), Fraction(b))
17. return answer
19. def get_answer(formula_list): # 后缀表达式的计算
20. num_list = list()
21. for formula in formula_list:
22. if isinstance(formula, int) or isinstance(formula, Fraction):
23. num_list.append(formula)
24. else:
25. b = num_list.pop()
26. a = num_list.pop()
27. res = Calculation.eval(formula, a, b)
28. num_list.append(res)
29. return num_list.pop()
从中序表达式 转换为 后序表达式
由于后续表达式更易计算机去解决，所以我们在运算算术表达式时要先转换为后序的。方法如下
建立符号栈
顺序扫描中序表达式
a） 是数字， 直接输出
b） 是运算符
i : “(” 直接入栈
ii : “)” 将符号栈中的元素依次出栈并输出, 直到 “(“, “(“只出栈, 不输出
iii: 其他符号, 将符号栈中的元素依次出栈并输出, 直到 遇到比当前符号优先级更低的符号或者”(“。 将当前符号入栈。
扫描完后, 将栈中剩余符号依次输出
例 : 3+(2-5)*6/3
遇到 3 是数字输出
表达式 : 3
符号栈 :
表达式 : 3
符号栈 : +
遇到”(” , 利用 法则i, 直接入栈
表达式 : 3
符号栈 : + (
遇到”2” 输出
表达式 : 3 2
符号栈 : + (
遇到 “-” , 利用法则iii , 遇到”(“, 没有出栈符号, 直接入栈
表达式 : 3 2
符号栈 : + ( -
遇到”5” 输出
表达式 : 3 2 5
符号栈 : + ( -
遇到”)” 利用法则ii , 将”-“号出栈输出, “(” 出栈
表达式 : 3 2 5 -
符号栈 : +
遇到”” 利用法则ii , “” 比”+”的优先级低, 所以遇到优先级更低的符号, 不用出栈, 将”*”入栈
表达式 : 3 2 5 -
符号栈 : + *
遇到”6” 输出
表达式 : 3 2 5 - 6
符号栈 : + *
遇到”/” 利用法则ii , “/” 与””的优先相同, 就是说””不是优先级更低的符号, 所以出栈输出, 继续 “+”比”/”的优先级低, 不用出栈, 将”/”入栈
表达式 : 3 2 5 - 6 *
符号栈 : + /
遇到”3” 输出
表达式 : 3 2 5 - 6 * 3
符号栈 : + /
扫描完成 将符号栈内的符号依次输出
表达式 : 3 2 5 - 6 * 3 / +