数据结构课程设计

1、数据结构课程设计报告实验一：计算器设计要求1、问题描述：设计一个计算器，可以实现计算器的简 单运算，输出并检验结果的正确性，以及检验运算表达式的 正确性。2、输入：不含变量的数学表达式的中缀形式，可以接 受的操作符包括+、-、*、/、%、（、）。具体事例如下：3、输出：如果表达式正确，则输出表达式的正确结果; 如果表达式非法，则输出错误信息。具体事例如下：知识点：堆栈、队列实际输入输出情况：正确的表达式对负数的处理表达式括号不匹配表达式出现非法字符表达式中操作符位置错误达式，W续 运继 M:诧止意掣算人第 覇»+云一俞IO汪圭冃求余操作符左右出现非整数其他输入错误数据结构与算法描述解

2、决问题的整体思路：将用户输入的中缀表达式转换成后缀表达式，再利用转换后的后缀表达式进行计算得出结果。解决本问题所需要的数据结构与算法：用到的数据结构是堆栈。主要算法描述如下：A .将中缀表达式转换为后缀表达式：1. 将中缀表达式从头逐个字符扫描，在此过程中，遇到的字符有以下几种情况：1）数字2）小数点3）合法操作符+ - * / %4）左括号5）右括号6）非法字符2. 首先为操作符初始化一个 map<std:string,int> priority，用于保存各个操作符的优先级，其中+ -为0, */%为13. 对于输入的字符串from和输出的字符串to，采用以下过程:初始化遍历器

3、std:string:iterator it=infix.begin()在当it!二from.end()，执行如下操作4. 遇到数字或小数点时将其加入到后缀表达式：case '1' : case '2' : case '3' : case'4' : case '5' : case '6' : case '7' : case'8' : case'9' : case '0' : case '.':to=to+*it;brea

4、k;5. 遇到操作符(+ ,-,*,/, %)时，如果此时栈顶操作符的优 先级比此时的操作符优先级低，则将其入栈，否则将栈中的操作符从 栈顶逐个加入到后缀表达式，直到栈空或者遇到左括号，并将此时的 操作符加入到栈中，在此过程中需判断表达式中是否出现输入错误：case '+' : case '-' : case '*' : case '/' : case '%':if (it+1)=from.end()cout«"输入错误：运算符号右边缺少运算数"<<e ndl;return

5、 false ;if(*it= '*' |*it='/' )&&it=from.begin()coutvv"输入错误：运算符号左边缺少运算数"<<e ndl;return false ;f (it+1)!=from.end()&&(*(it+1)='+' |*(it+1)='-' |*(it+1)='*' |*(it+1)='/'|*(it+1)='%')coutvv"输入错误：运算符号连续岀现"&l

6、t;<e ndl;return false ;to=to+ ""if (sym.empty()sym.push(*it);break;tem=sym.top();while (pri*it<=pritem&&!sym.empty()&&tem!='(')to=to+tem+ ""sym.pop();if (sym.empty() break;tem=sym.top();6. 遇到“(”时，直接将其加入操作符栈，并且检测输入错误,并且当括号后的第一个符号为-时，说明用户试图输入负号，这种情况我们向

7、目标表达式输出一个 0，以达到处理负号的目的:case '(':if (it+1)=from.end()if (it!=from.begin()&&(*(it-1)!='+' &&*(it-1)!='-' &&*(it-1)!='*'&&*(it-1)!='/' &&*(it-coutvv"输入错误：表达式以左括号结尾 "vve ndl;return false ;/若以+或者-开头，则按照正负号看待，向目标表达式中

8、加入一个0if (*(it+1)='-' |*(it+1)='+')to=to+ '0'if (it+1)!=from.end()&&(*(it+1)='*' |*(it+1)='/' |*(it+1)='%' |*(it+1)=')')coutvv"输入错误：左括号右边不能为运算符号或右括号“ <<endl;return false ;5.遇到“)”时，将栈中的操作符从栈顶逐个弹出并放入后缀表 达式中，直到在栈中遇到“(”，并将“(”从栈中弹出

9、：case ')':if (it+1)!=from.end()&&*(it+1)!='+' &&*(it+1)!= '-' &&*(it+1)!= '*' &&*(it+1)!='/' &&*(it+1)!= '%' &&*(it+1)!=')')coutvv"输入错误：右括号右边不能为运算数"<<e ndl;return false ;if (it匸fro

10、m.begin()&&(*(it-1)='+' |*(it-1)='-' |*(it-1)='*' |*(it-1)='/' |*(it-1)='%')coutvv"输入错误：右括号左边不能为运算符号"<<e ndl;return false ;to=to+ ""if (sym.empty()coutvv"输入错误：表达式以右括号开始"vve ndl; return false ;tem=sym.top();while (tem

11、!='(')to=to+tem+ ""sym.pop();if (sym.empty()coutvv"输入错误：括号匹配有误"vvendl;return false ;tem=sym.top();B.计算后缀表达式的主要思想:逐个字符的扫描后缀表达式，遇到单个数字或小数点时则先将 其将其存到一个字符串中，当遇到后缀表达式中的分隔符（这里 使用空格）时，则将这个字符串转化为数字放到堆栈n umstack中；case '1' : case 2 : case 3 : case'4' : case '5&#

12、39; : case '6' : case '7' : case8' : case'9' : case 'O' : case '.':n umtemp+=*it;break;case '':if (numtemp!="")if (numtemp.find('.')&&numtemp.find( '.' ,(numtemp.find('.')+1)!= string :npos)cout<<&quo

13、t;输入错误：小数点数目超岀："+n umtempvve ndl;return falsestrm.str( numtemp); strm»d;n umstack.push(d); numtemp=" strm.str(""); strm.clear();break;break;2. 遇到操作符+, -, *, /, %时，将堆栈numstack中的栈顶的两个数取出来，进行相应操作的运算，并将结果加入到堆栈n umstack中；case '+':d2=n umstack.top();n umstack.pop();d1= num

14、stack.top();n umstack.pop();n umstack.push(d1+d2);break;case '-':d2=n umstack.top();n umstack.pop();d1= numstack.top();n umstack.pop();n umstack.push(d1-d2);break;d2=n umstack.top();n umstack.pop();d1= numstack.top();n umstack.pop();n umstack.push(d1*d2);break;case '/':d2=n umstack.t

15、op();n umstack.pop();if (fabs(d2)<0.0000001)cout«"输入错误：除数不能为0"<<e ndl; return false ;d1= numstack.top();n umstack.pop();n umstack.push(d1/d2);break;case '%':d2=n umstack.top();n umstack.pop();d1= numstack.top();n umstack.pop();if (fabs(d2-( int )d2)<0.0000001 &

16、&(fabs(d1-(int )d1)<O.OOOOOO1)int n1=( int )d1;int n2=( int )d2;numstack.push( double )(n1%n2);break;elsecerr<< "输入错误：求模操作只能作用于整数"<<endl;return false ;3直到后缀表达式扫描完并且堆栈 numstack中只有一个数值, 则此数值为计算的最终结果，否则说明输入有误。分析与探讨：1、测试结果分析：测试结果见本篇开始的实际输入输出结果。该计算器几乎实现了所有相关功能，包括简单计算、负数小数处理，容

17、错，并且健壮性好，对于错误的表达式可以给出适当提示，不 会导致程序崩溃。2、算法分析1、对于中缀表达式转换成后缀表达式：时间复杂性为0(n)2、 对于后缀表达式的计算：时间复杂性为0(n)综上，该程序算法的时间复杂度为 0(n)3、算法改进该程序存在的主要问题是命令行式的用户界面不够友好。Windows下的用户图形界面需要 MFC方面的知识，因为时 间关系没有进行这方面的深入学习。附录：源代码文件一 .ExpressionHandler.h#inelude vstring>#inelude <map>#include <staek>#inelude <ios

18、tream>#include <sstream>using namespaeestd;class ExpressionHandler publie :ExpressionHandler( string exp)this ->exp=exp;bool infixtoprofix(string & exp);bool doprofix( string profix, double &result);private :stri ng exp;；文件二.ExpressionHandler.cpp/Coded By CS_Zha nglin#inelude &qu

19、ot;ExpressionHandler.h"bool ExpressionHandler :infixtoprofix(string & exp)string from= this ->exp;string to=""stack <char> sym;map：char, int > pri;char tem;pri '+' =1;pri '-' =1;pri '*' =2;pri '/' =2;pri '%' =2;string : iteratori

20、t=from.begin();if (*it= '+' |*it='-')to+= 'O'while (it!=from.end()coutv<1vve ndl;switch (*it)case '1' : case '2' : case 3 : case'4' : case '5' : case '6' : case '7' : case '8' : case'9' : case '0' : ca

21、se '.':to=to+*it;break;case '+' : case '-' : case '*' : case '/' : case '%':if (it+1)=from.end()cout«"输入错误：运算符号右边缺少运算数"<<e ndl;return false ;if(*it= '*' |*it='/' )&&it=from.begin()coutvv"输入错误：运算符号左边缺少运算

22、数"<<e ndl;return false ;if (it+1)!=from.end()&&(*(it+1)='+' |*(it+1)='-' |*(it+1)='*' |*(it+1)='/' |*(it+1)= '%')coutvv"输入错误：运算符号连续岀现"<<e ndl;return false ;to=to+ ""if (sym.empty()sym.push(*it);break;tem=sym.top();w

23、hile (pri*it<=pritem&&!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()coutvv"输入错误：表达式以左括号结尾 "<<e ndl;return false ;if(*(it+1)='-' |*(it+1)='+

24、9;)to=to+ 'O'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)!=&

25、#39;*' &&*(it-1)!='/' &&*(it-1)!= '%' &&*(it-1)!='(')coutvv"输入错误：左括号左边不能为运算数或右括号"vve ndl;return false ;sym.push(*it);break; case ')'if (it+1)!=from.end()&&*(it+1)!='+' &&*(it+1)!= '-' &&*(it

26、+1)!='*' &&*(it+1)!='/' &&*(it+1)!= '%' &&*(it+1)!=')coutvv"输入错误：右括号右边不能为运算数"vve ndl;return false ;if (it匸from.begin()&&(*(it-1)='+' |*(it-1)='-'|*(it-1)='*' |*(it-1)='/' |*(it-1)='%')coutvv

27、"输入错误：右括号左边不能为运算符号"<<endl;return false ;to=to+ ""if (sym.empty() |coutvv"输入错误：表达式以右括号开始"vve ndl;return false ; |tem=sym.top();while (tem!='(')to=to+tem+ ""sym.pop();if (sym.empty()sym.pop();break;default :coutvv"输入错误：未知符号"<<endl;

28、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 prof

29、ix , double & result )stri ng n umtemp;stack <double > numstack;stri ngstream 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

30、' : case '8' : case'9' : case '0' : case '.':n umtemp+=*it;break;case '':if (numtemp!="")if (numtemp.find( '.' )&&numtemp.find( '.' ,(numtemp.find( '.' )+1)!= string :npos)cout«"输入错误：小数点数目超岀："+n umte

31、mpvve ndl;return false strm.str( numtemp);strm»d;n umstack.push(d);numtemp="strm.str("");strm.clear();break;break;case '+':d2=n umstack.top(); n umstack.pop(); d1= numstack.top(); n umstack.pop();n umstack.push(d1+d2);d2=n umstack.top(); n umstack.pop();d1= numstack.top(); n umstack.pop();n umstack.push(d1-d2);break;case '*':d2=n umstack.top();n umstack.pop();d1= numstack.top();n umstack.pop();n umstack.push(d1*d2); break;case '/':d2=n umstack.top();n umstack.pop();if (fabs(d2)<0.0000001)n umstack.pop();n