版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
数据结构课程设计报告实验一:计算器设计要求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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 乡下家人课件
- 税收补充习题
- 小儿先天性心脏病
- 《粉末冶金》课件
- 中学规划设计
- 几百几十数乘以一位数质量测验口算题
- 2024应急预案编制导则
- 血液制品的种类成分和作用全血成分血血制品
- 重庆2022-2023高二上期学情调研化学试题卷
- 新媒体创新与运用
- 八年级足球“局部对抗情境下攻防技战术运用”主题大单元教学设计
- 国有企业员工违纪违规行为处分规定-职工违纪违规处分规定
- 园艺与健康智慧树知到期末考试答案2024年
- 第10课时-小人物-大情怀-单元总结-七年级语文下册(部编版)
- 电子烟市场调研报告总结与反思
- 厂务动力系统培训课件
- 日本国家概况历年试题及答案
- 数值分析智慧树知到期末考试答案2024年
- 《红楼梦》第一回
- 网站推广引流优化方案
- 人教版小学数学计算去括号练习100题及答案
评论
0/150
提交评论