关键词:
题目要求:
第一步: 像阿超那样,花二十分钟写一个能自动生成小学四则运算题目的命令行 “软件”, 分别满足下面的各种需求。下面这些需求都可以用命令行参数的形式来指定:
a) 除了整数以外,还要支持真分数的四则运算。 (例如: 1/6 + 1/8 = 7/24)
b) 让程序能接受用户输入答案,并判定对错。 最后给出总共 对/错 的数量。
c) 逐步扩展功能和可以支持的表达式类型,最后希望能支持下面类型的题目 (最多 10 个运算符,括号的数量不限制):
25 - 3 * 4 - 2 / 2 + 89 = ?
1/2 + 1/3 - 1/4 = ?
(5 - 4 ) * (3 +28) =?
d) 一次可以批量出 100 道以上的题目,保存在文本文件中, 并且保证题目不能重复,(1+2) 和 (2+1) 是重复的题目。 怎么保证题目不重复呢,请看详细题目要求
和同学们比较一下各自程序的功能、性能、实现方法的异同等等。
如何对一个表达式求值? 参考资料:
http://hczhcz.github.io/2014/02/27/shunting-yard-algorithm.html
https://en.wikipedia.org/wiki/Shunting-yard_algorithm
鉴于该问题的难度与工作量,我将该问题拆分成3个小阶段进行实现:
1:复合四则运算的求值
2:随机生成复合四则运算
3:增加对真分数和假分数的支持
分析:1.对于复合四则运算的求值,可以根据堆栈的特性,利用算数符合的优先级比较,对复合四则运算求值,详细的算法过程将在下文进行介绍。
2.随机生成复合四则运算是本题目的一个难点,在进行思考过后,我觉得可以采用多次随机过程,生成四则运算表达式。第一次,随机参与计算的数字个数,第二次,随机数字的数值,第三次,随机数字间的四则运算符,第四次,随机括号的添加。注意,由于可能存在除0运算,所以要对这种错误情况进行排除。由于第三次和第四次随机过程的特殊性,即使在第三步出现例如:3 / 0 + 1 的运算表达式,但是如果第四次随机过程在算式 0 + 1 外生成括号,造成 3 / ( 0 + 1 )的结果,这种算式也是正确的。因此,不能保证在随机生成复合四则运算的过程中进行除0的判断。
对于这个问题,我的个人思路是:在生成每一个复合四则运算后,进行复合运算求值,并在算法每一次求值过程中就行判断,如果出现除0错误,就抛出异常,标记当前生成的四则运算式子非法,进行重新生成。虽然除0的情况很多,这样会浪费大量的时间进行判断,但是由于问题的时间复杂度和空间复杂度都非常小,可以忽略不计。
3.在增加真分数和假分数运算时候,只需要对每一种四则运算进行一次条件判断,因此无较大的难度。
一、复合四则运算的求值
表达式求值的算法:
我采用的是“算符优先法”,在表达式中,优先级的顺序是:
1、括号的优先级最高,对括号内的各种运算符有:先乘除,后加减,同级运算从做至右
2、先括号内,后括号外,多层括号,由内向外。
操作数可以是常量、变量、常数。
运算符有算术运算符、关系运算符、逻辑运算符。
界符包括左右括号算式结束符。
运算符和界符统称为“算符”。
在算符集中,在每一个运算步,相邻的算符c1 和c2之间的关系是如下三种情况(c1出现在c2之前):
c1<c2,c1的优先级低于c2
c1=c2,c1的优先级等于c2
c1>c2,c1的优先级大于c2
下图描述的算符的优先级:
为实现算符优先算法,在这里用了两个工作栈。一个存放算符OPTR,另一个存放数据OPND。算法思想是:
(1)首先置数据栈为空栈,表达式起始符“#”为算符栈的栈底元素
(2)自左向右扫描表达式,读到操作数进OPND栈,读到运算符,则和OPTR栈顶元素比较(栈顶元素为c1,读到的算符为c2);
若c1<c2,则c2进栈继续扫描后面表达式;
若c1=c2,则(“=”),即括号内运算结束,将c1出栈,并且c2放弃,继并在操作数栈扫描后面表达式;
若c1>c2,则将c1出栈,并在操作数栈取出两个元素a和b按c1做运算,运算结果进OPND.
重复直到表达式求值完毕。
例如:表达式3*(7-2),求值过程如下表:
步骤 | OPTR栈 | OPND栈 | 输入字符 | 主要操作 |
1 | # | 3*(7-2)# | PUSH(OPND,‘3‘) | |
2 | # | 3 | *(7-2)# | PUSH(OPTR,‘*‘) |
3 | #* | 3 | (7-2)# | PUSH(OPTR,‘(‘) |
4 | #*( | 3 | 7-2)# | PUSH(OPND,‘7‘) |
5 | #*( | 3 7 | -2)# | PUSH(OPTR,‘-‘) |
6 | #*(- | 3 7 | 2)# | PUSH(OPND,‘2‘) |
7 | #*( | 3 7 2 | )# | operate(7-2) |
8 | #*( | 3 5 | )# | pop() |
9 | #* | 15 | # | operate(3*5) |
10 | # | 15 | # | PUSH(OPTR,‘#‘) |
为使两个算符比较方便,给算符设置优先级,如下表,其中c1为栈内元素,c2为栈外元素:
算符比较算法:
char Precede(char c1,char c2) {int c_temp1,c_temp2; switch(c1) { case ‘*’: case ‘/’:c_temp1=4;break; case ‘+’: case ‘-’:c_temp1=2;break; case ‘(’:c_temp1=0;break; case ‘)’:c_temp1=5;break; case ‘#’:c_temp1=-1; }
switch(c2) { case ‘*’: case ‘/’:c_temp2=3;break; case ‘+’: case ‘-’:c_temp2=1;break; case ‘(’:c_temp2=5;break; case ‘)’:c_temp2=0;break; case ‘#’:c_temp2=-1;} if(c_temp1<c_temp2) return(‘<‘); if(c_temp1=c_temp2) return(‘=‘); if(c_temp1>c_temp2) return(‘>‘); }
int express() { Initstack(OPTR);Push(OPTR,’#’); InitStack(OPND); w=getchar(); while(w!=‘#’||GetTop(OPTR)!=‘#’) {if(!In(w,OP)){Push(OPND,w);w=getchar();} else //OP是操作符集合 switch(Precede(GetTop(OPTR),w)) {case ‘<‘: Push(OPTR,w);w=getchar();break; case ‘=‘: Pop(OPTR);w=getchar();break; case ‘>‘: op=Pop(OPTR);b=Pop(OPND);a=Pop(OPND); push(OPND,Operate(a,op,b));break;}} return(Getop(OPND) );
算符优先算法求表达式值:
OperandType EvaluateExpression() { InitStack (OPTR); Push ( OPTR,’#’); InitStack (OPND); c=getchar(); while (c!=‘#’|| GetTop(OPTR)!=‘#’) { if(!In(c,OP)){Push(OPND,c); c=getchar();} else switch(Precede(GetTop(OPTR),c){ case ‘<‘://栈顶元素优先权低 Push(OPTR,c); c=getchar(); break; case ‘=‘://脱括号 Pop(OPTR,x); c=getchar(); break; case ‘>’://退栈并计算 Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND, Operate(a,theta,b)); break; }//switch }//while return GetTop(OPND); }//EvaluateExpression
现代软件工程第一章概论第9题——邓琨
我采访了一只开发了天津8890便民服务网站系统的团队。 -当时的项目有多少用户,给用户多少价值?现在还有人用吗?答:当时项目有近万用户,为天津市民提供便民服务平台,例如联系修理家电、水电气、咨询服务、中... 查看详情
现代软件工程第一章概论习题第1题李艳薇
实现自动出题功能:程序并没有实现全部要求,后续将会继续改进。 实现结果:程序代码:#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<time.h>usingnamespacestd;#defineN100boolcreateP 查看详情
现代软件工程第一章概论第4题——张功
第4题:Dijkstra曾经提到:“Softwareengineering,ofcourse,presentsitselfasanotherworthycause,butthatiseyewash:ifyoucarefullyreaditsliteratureandanalysewhatitsdevoteesactuallydo,youwilldiscoverthatsoftwaree 查看详情
现代软件工程第一章概论第1题——孙雪莹张功
第一步:像阿超那样,花二十分钟写一个能自动生成小学四则运算题目的命令行“软件”,分别满足下面的各种需求。下面这些需求都可以用命令行参数的形式来指定: a)除了整数以外,还要支持真分数的四... 查看详情
现代软件工程第一章概论第10题——张功
10.Software, SoftwareEngineering,waterfall(瀑布模型),CodeComplete,...等名词的来源http://en.wikipedia.org/wiki/John_Tukey请问“软件”,“软件工程”,瀑布模型,CodeComplete,AgileMethodology这些词汇是如何出现的-何时 查看详情
现代软件工程第一章概论第12题——原旭莹
12.我们不是在真空里谈软件工程,软件要运行在硬件芯片上面,下面看看一个计算机芯片的发展历史http://perspectives.mvdirona.com/2014/09/august-21-2014-computer-history-museum-presentation/http://mvdirona.com/jrh/TalksAndPapers/DileepBhandarkarAmazin 查看详情
现代软件工程第一章概论第10题——孙雪莹
10.2:现代软件工程这门课已经上了好几年了,以前有很多学生做过团队项目(说不定包括本校的学生),请你们找一个以前的团队采访一下: -当时的项目... 查看详情
现代软件工程第一章概论第11-15题(白文俊)
...oftwareEngineering等名词的来源,请问“软件”和“软件工程”这些词汇是如何出现的-何时、何地、何人在看过给的链接原文之后我得出这样的结论:”software”即“软件”这一名词的使用最早是在1953年8月... 查看详情
现代软件工程第一章概论第6题——原旭莹
...火车票。这些软件合法么?符合道德规范么?是在“软件工程”的研究范围么?请大家讨论。 我认为这些软件的合法性是存在一定问题的,也并不符合道 查看详情
现代软件工程第一章概论第3题——张晓丽
第3题目前流行的源程序版本管理软件和项目管理软件都有哪些,各有什么优缺点?参照http://www.cnblogs.com/WJ1234/p/5285595.html http://www.360doc.com/content/12/0712/11/4565_223745448.shtml1、Microsoft TFS的优缺点:优点:是对敏捷,m... 查看详情
现代软件工程第一章概论第13题——张功
13.这么多作业,似乎压力很大啊!请看TED的演讲,谈谈你对压力的看法,以及怎么和别人合作,帮助别人,把压力转化为动力,在互相帮助的环境中成长。 我们可以将压力看作生命的一部分,我们接受来自... 查看详情
现代软件工程第一章概论第2题——孙雪莹(还未完成)
2. 软件有很多种,也有各种分类办法: ShrinkWrap(在包装盒子里面的软件,软件在软盘/CD/DVD上); WebAPP(基于网页的软件); InternalSoftware(企业或学校或某组织内部的软件); &n... 查看详情
现代软件工程第一章概论第14题——张晓丽
14、开发软件有很多种方式,从软件运行的平台来看,可以在下面的平台运行:网页(只要有浏览器就可以访问软件或服务)Windows平台(例如最新的Windows10支持PC,Surface,Mobile,甚至Xbox运行)安卓平台iOS平台(Mac和iPhone)请找一... 查看详情
现代软件工程第一章概论第7题——张星星
综合多方面考虑,我认为,”中文编程”并不是一个”银弹”,并不能提高中国程序员的编程效率。 首先,中文编程指的是使用中文书写关键字,如类名、函数名、变量名、常量名等。对编程语言来说,语... 查看详情
现代软件工程第一章概论练习与讨论——范鹏宸(371113)
第三题问题描述: 上网调查一下目前流行的源程序版本管理软件和项目管理软件都有哪些,各有什么优缺点?答:目前流行的原程序版本管理软件和项目管理软件有MicrosoftTFS、GitHub、Trac、Bugzilla、Rationale,AppleXCode这几种比... 查看详情
现代软件工程第一章概论练习与讨论
题目1解答:开发环境选择的是c++,开发工具使用的是Visualc++6.0。首先,先完成一个最简单的工能,随机产生一个只有两个操作数一个运算符的式子,接受输入并判断输入答案是否正确:代码如下:#include<iostream.h>#include<std... 查看详情
现代软件工程第一章概论练习与讨论
1、像阿超那样,花二十分钟写一个能自动生成小学四则运算题目的“软件”,和同学们比较一下各自程序的功能、实现方法的异同等等。(苏志华)7、有人认为,"中文编程",是解决中国程序员编程效率一个秘密武器,请... 查看详情
现代软件工程第一章概论练习与讨论第6题邓杰
...火车票。这些软件合法么?符合道德规范么?是在“软件工程”的研究范围么?请大家讨论。 首先说说类似于抢票软件的合法性,在目前来看,国家政府并没有采取强硬的手段和法律措施来制止这种行为,抢票软件也... 查看详情