版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
数据结构课程设计报告实验一:计算器设计要求1、问题描述:设计一个计算器,可以实现计算器的简单运算,输出并检验结果的正确性,以及检验运算表达式的正确性。2、输入:不含变量的数学表达式的中缀形式,可以接受的操作符包括 +、-、*、/、%、(、)。具体事例如下:3、输出:如果表达式正确,则输出表达式的正确结果;如果表达式非法,则输出错误信息。具体事例如下:知识点:堆栈、队列实际输入输出情况:正确的表达式对负数的处理表达式括号不匹配表达式出现非法字符表达式中操作符位置错误求余操作符左右出现非整数其他输入错误数据结构与算法描述解决问题的整体思路:将用户输入的中缀表达式转换成后缀表达式,再利用转换后的后缀表达式进行计算得出结果。解决本问题所需要的数据结构与算法:用到的数据结构是堆栈。主要算法描述如下:.将中缀表达式转换为后缀表达式:将中缀表达式从头逐个字符扫描,在此过程中,遇到的字符有以下几种情况:1)数字2)小数点3)合法操作符 +-*/%4)左括号5)右括号6)非法字符2.首先为操作符初始化一个 map<std::string,int> priority,用于保存各个操作符的优先级,其中 +-为0,*/%为1对于输入的字符串from和输出的字符串to,采用以下过程:初始化遍历器 std::string::iteratorit=infix.begin()在当it!=from.end() ,执行如下操作遇到数字或小数点时将其加入到后缀表达式:'8'
case:case'9'{
'1':case:case '0'
'2':case
:case'.':
'3'
:case'4'
:case
'5'
:case
'6'
:case'7'
:caseto=to+*it;break;}遇到操作符(+,-,*,/,%)时,如果此时栈顶操作符的优先级比此时的操作符优先级低,则将其入栈,否则将栈中的操作符从栈顶逐个加入到后缀表达式,直到栈空或者遇到左括号,并将此时的操作符加入到栈中,在此过程中需判断表达式中是否出现输入错误:case'+' :case'-' :case '*' :case '/' :case '%':{if((it+1)==from.end()){cout<<"输入错误:运算符号右边缺少运算数 "<<endl;return false ;}if((*it== '*' ||*it== '/' )&&it==from.begin()){cout<<"输入错误:运算符号左边缺少运算数 "<<endl;return false ;}if((it+1)!=from.end()&&(*(it+1)==
'+'
||*(it+1)==
'-'
||*(it+1)==
'*'
||*(it+1)==
'/'||*(it+1)== '%')){cout<<return
"输入错误:运算符号连续出现false ;
"<<endl;}to=to+
""
;if(sym.empty()){sym.push(*it);break;}tem=sym.top();while(pri[*it]<=pri[tem]&&!sym.empty()&&tem!= '(' ){to=to+tem+"" ;sym.pop();if(sym.empty()) break;tem=sym.top();}sym.push(*it);break;}遇到“(”时,直接将其加入操作符栈,并且检测输入错误,并且当括号后的第一个符号为 -时,说明用户试图输入负号,这种情况我们向目标表达式输出一个 0,以达到处理负号的目的:case '(' :{if((it+1)==from.end()){cout<<"输入错误:表达式以左括号结尾 "<<endl;returnfalse;}//若以+或者-开头,则按照正负号看待,向目标表达式中加入一个0if(*(it+1)=='-'||*(it+1)=='+'){to=to+'0';}if((it+1)!=from.end()&&((*(it+1)== '*' ||*(it+1)== '/' ||*(it+1)== '%'||*(it+1)== ')' ))){cout<<"输入错误:左括号右边不能为运算符号或右括号 "<<endl;return false ;}if(it!=from.begin()&&(*(it-1)!= '+' &&*(it-1)!= '-' &&*(it-1)!= '*' &&*(it-1)!= '/' &&*(it-1)!='%'&&*(it-1)!=
'('{
))cout<<"输入错误:左括号左边不能为运算数或右括号 "<<endl;return false ;}sym.push(*it);break;}遇到“)”时,将栈中的操作符从栈顶逐个弹出并放入后缀表达式中,直到在栈中遇到“(”,并将“(”从栈中弹出:case ')' :{if((it+1)!=from.end()&&*(it+1)!=+1)!='%'&&*(it+1)!= ')' )
'+'
&&*(it+1)!=
'-'
&&*(it+1)!=
'*'
&&*(it+1)!=
'/'
&&*(it{cout<<"输入错误:右括号右边不能为运算数 "<<endl;return false ;}if(it!=from.begin()&&(*(it-1)==
'+'
||*(it-1)==
'-'
||*(it-1)==
'*'
||*(it-1)==
'/'
||*(it-1)=='%' )){cout<<"输入错误:右括号左边不能为运算符号 "<<endl;return false ;}to=to+"" ;if(sym.empty()){cout<<"输入错误:表达式以右括号开始 "<<endl;return false;}tem=sym.top();while(tem!='(' ){to=to+tem+"" ;sym.pop();if(sym.empty()){cout<<"输入错误:括号匹配有误 "<<endl;return false;}tem=sym.top();}sym.pop();break;}.计算后缀表达式的主要思想:逐个字符的扫描后缀表达式, 遇到单个数字或小数点时则先将其将其存到一个字符串中,当遇到后缀表达式中的分隔符(这里使用空格)时,则将这个字符串转化为数字放到堆栈 numstack中;'8'
case:case'9'{
'1':case:case '0'
'2':case
:case'.':
'3'
:case'4'
:case
'5'
:case
'6'
:case'7'
:casenumtemp+=*it;break;}case'' :{if(numtemp!="" ){if(numtemp.find( '.' )&&numtemp.find( '.' ,(numtemp.find( '.' )+1))!= string ::npos){cout<<"输入错误:小数点数目超出: "+numtemp<<endl;return false;}strm.str(numtemp);strm>>d;numstack.push(d);numtemp="";strm.str( "");strm.clear();break;}break;}遇到操作符+,-,*,/,%时,将堆栈numstack中的栈顶的两个数取出来,进行相应操作的运算,并将结果加入到堆栈 numstack中;case'+' :{d2=numstack.top();numstack.pop();d1=numstack.top();numstack.pop();numstack.push(d1+d2);break;}case'-' :{d2=numstack.top();numstack.pop();d1=numstack.top();numstack.pop();numstack.push(d1-d2);break;}case'*' :{d2=numstack.top();numstack.pop();d1=numstack.top();numstack.pop();numstack.push(d1*d2);break;}case'/' :{d2=numstack.top();numstack.pop();if(fabs(d2)<0.0000001){cout<<"输入错误:除数不能为 0"<<endl;return false ;}d1=numstack.top();numstack.pop();numstack.push(d1/d2);break;}case'%':{d2=numstack.top();numstack.pop();d1=numstack.top();numstack.pop();if((fabs(d2-( int{
)d2))<0.0000001&&(fabs(d1-(
int)d1))<0.0000001)int n1=(int )d1;int n2=(int )d2;numstack.push(( double)(n1%n2));break;}else{cerr<<"输入错误:求模操作只能作用于整数 "<<endl;return false ;}}3.直到后缀表达式扫描完并且堆栈 numstack 中只有一个数值,则此数值为计算的最终结果,否则说明输入有误 。分析与探讨:1、测试结果分析:测试结果见本篇开始的实际输入输出结果。该计算器几乎实现了所有相关功能,包括简单计算、负数小数处理,容错,并且健壮性好,对于错误的表达式可以给出适当提示,不会导致程序崩溃。2、算法分析1、对于中缀表达式转换成后缀表达式: 时间复杂性为O(n)2、对于后缀表达式的计算:时间复杂性为 O(n)综上,该程序算法的时间复杂度为 O(n)3、算法改进该程序存在的主要问题是命令行式的用户界面不够友好。Windows 下的用户图形界面需要 MFC方面的知识,因为时间关系没有进行这方面的深入学习。附录:源代码文件一.ExpressionHandler.h#include<string>#include<map>#include<stack>#include<iostream>#include<sstream>usingnamespacestd;classExpressionHandler{public:ExpressionHandler( string exp){this->exp=exp;}boolinfixtoprofix( string &exp);booldoprofix( string profix, double &result);private :string exp;};文件二.ExpressionHandler.cpp//CodedByCS_Zhanglin#include "ExpressionHandler.h"bool ExpressionHandler ::infixtoprofix(string from=this->exp;string to="";stack<char>sym;map<char,int >pri;chartem;pri[ '+']=1;pri[ '-' ]=1;pri[ '*' ]=2;pri[ '/' ]=2;pri[ '%']=2;string ::iterator it=from.begin();if(*it== '+' ||*it== '-' )to+='0' ;while(it!=from.end()){//cout<<1<<endl;switch(*it){case '1':case '2' :case'8' :case'9' :case '0' :case '.' :{
string'3'
&exp){:case'4'
:case
'5'
:case
'6'
:case'7'
:caseto=to+*it;break;case
}'+'{
:case
'-'
:case
'*'
:case
'/'
:case
'%':if((it+1)==from.end()){cout<<"输入错误:运算符号右边缺少运算数 "<<endl;return false ;}if((*it== '*' ||*it== '/' )&&it==from.begin()){cout<<"输入错误:运算符号左边缺少运算数 "<<endl;return false ;}if((it+1)!=from.end()&&(*(it+1)==
'+'
||*(it+1)==
'-'
||*(it+1)==
'*'
||*(it+1)==
'/'
||*(it+1)=='%')){cout<<"输入错误:运算符号连续出现 "<<endl;return false ;}to=to+"" ;if(sym.empty()){sym.push(*it);break;}tem=sym.top();while(pri[*it]<=pri[tem]&&!sym.empty()&&tem!= '(' ){to=to+tem+"" ;sym.pop();if(sym.empty()) break;tem=sym.top();}sym.push(*it);break;}case'(' :{if((it+1)==from.end()){cout<<"输入错误:表达式以左括号结尾 "<<endl;return false ;}if(*(it+1)==
'-'
||*(it+1)==
'+'){to=to+'0'
;}if((it+1)!=from.end()&&((*(it+1)==
'*'
||*(it+1)==
'/'
||*(it+1)==
'%'||*(it+1)==
')'
))){cout<<"输入错误:左括号右边不能为运算符号或右括号return false ;
"<<endl;}if(it!=from.begin()&&(*(it-1)!=
'+'
&&*(it-1)!=
'-'
&&*(it-1)!=
'*'
&&*(it-1)!=
'/'
&&*(it-1)!='%'&&*(it-1)!= '(' )){cout<<"输入错误:左括号左边不能为运算数或右括号return false ;
"<<endl;}sym.push(*it);break;}case')' :{if((it+1)!=from.end()&&*(it+1)!=+1)!='%'&&*(it+1)!= ')' )
'+'
&&*(it+1)!=
'-'
&&*(it+1)!=
'*'
&&*(it+1)!=
'/'
&&*(it{cout<<"输入错误:右括号右边不能为运算数 "<<endl;return false ;}if(it!=from.begin()&&(*(it-1)==
'+'
||*(it-1)==
'-'
||*(it-1)==
'*'
||*(it-1)==
'/'
||*(it-1)=='%' )){cout<<"输入错误:右括号左边不能为运算符号 "<<endl;return false ;}to=to+"" ;if(sym.empty()){cout<<"输入错误:表达式以右括号开始 "<<endl;return false;}tem=sym.top();while(tem!='(' ){to=to+tem+"" ;sym.pop();if(sym.empty()){cout<<"输入错误:括号匹配有误 "<<endl;return false;}tem=sym.top();}sym.pop();break;}default :{cout<<"输入错误:未知符号 "<<endl;return false ;}}++it;}if(!sym.empty()){to=to+"" ;tem=sym.top();while(!sym.empty()){if(tem=='(' ){cout<<"输入错误:括号匹配有误 "<<endl;return false ;}to=to+tem+ "" ;sym.pop();if(sym.empty()) break;tem=sym.top();}}exp=to;return true;}bool ExpressionHandler ::doprofix( string profix ,double&result ){string numtemp;stack<double>numstack;stringstream strm;double d,d1,d2;for(string ::iterator it= profix .begin();it!= profix .end();++it){switch (*it){case '1':case '2' :case '3' :case'4' :case '5' :case '6' :case'7':case'8' :case'9' :case '0' :case '.' :{numtemp+=*it;break;}case'' :{if(numtemp!="" ){if(numtemp.find( '.' )&&numtemp.find( '.' ,(numtemp.find( '.' )+1))!= string ::npos){cout<<"输入错误:小数点数目超出: "+numtemp<<endl;return false;}strm.str(numtemp);strm>>d;numstack.push(d);numtemp="";strm.str( "");strm.clear();break;}break;}case '+':{d2=numstack.top();numstack.pop();d1=numstack.top();numstack.pop();numstack.push(d1+d2);break;}case '-' :{d2=numstack.top();numstack.pop();d1=numstack.top();numstack.pop();numstack.push(d1-d2);break;}case '*' :{d2=numstack.top();numstack.pop();d1=numstack.top();numstack.pop();numstack.push(d1*d2);break;}case '/' :{d2=numstack.top();numstack.pop();if(fabs(d2)<0.0000001){cout<<"输入错误:除数不能为 0"<<endl;return false;}d1=numstack.top();numstack.pop();numstack.push(d1/d2);break;}case '%':{d2=numstac
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 电锁项目营销计划书
- 企业容灾演练服务行业营销策略方案
- 电子管项目运营指导方案
- 窑具支架商业机会挖掘与战略布局策略研究报告
- 乐器用电子练习弱音器产品供应链分析
- 塑料杯盖产品供应链分析
- 2.1《网络改变世界》 课件 -2024-2025学年统编版道德与法治八年级上册
- 儿童雨靴产品供应链分析
- 药用植物根项目营销计划书
- 管理飞机控制装置用计算机商业机会挖掘与战略布局策略研究报告
- A3报告培训教材
- 健康教育与健康促进试题及参考答案
- 送别怀人诗鉴赏公开课一等奖市赛课一等奖课件
- 大学教师年度师德考核表
- 秋冬季安全检查表
- 应用文写作通知试题4篇范文
- 保利发展控股集团-2022-2023年房地产行业白皮书
- 土力学(二)-课件清华大学-张丙印
- 小区日常清洁服务项目投标书
- 第三章人本心理治疗
- 孔融让梨(故事PPT)
评论
0/150
提交评论