《数据结构课程设计计算器》由会员分享，可在线阅读，更多相关《数据结构课程设计计算器（24页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告计算器设计要求1、问题描述：设计一个计算器，可以实现计算器的简单运 算，输出并检验结果的正确性，以及检验运算表达式的正确性。2、输入：不含变量的数学表达式的中缀形式，可以接受的 操作符包括+、-、*、/、（、）。具体事例如下：3、输出：如果表达式正确，则输出表达式的正确结果；如 果表达式非法，则输出错误信息。具体事例如下：知识点：堆栈、队列实际输入输出情况：正确的表达式对负数的处理表达式括号不匹配 表达式出现非法字符表达式中操作符位置错误求余操作符左右出现非整数其他输入错误数据结构与算法描述解决问题的整体思路：将用户输入的中缀表达式转换成后缀表达式， 再利用转换后的后缀表达
2、式进行计算得出结果。解决本问题所需要 的数据结构与算法：用到的数据结构是堆栈。主要算法描述如下：A .将中缀表达式转换为后缀表达式：1. 将中缀表达式从头逐个字符扫描，在此过程中，遇到的字符有以下几种情况：1）数字2）小数点3）合法操作符+ - * / %4）左括号5）右括号6) 非法字符2. 首先为操作符初始化一个map priority，用于保存各个操作符的优先级，其中+ -为0, */%为13. 对于输入的字符串from和输出的字符串to,采用以下过程：初始化遍历器 std:string:iterator it=infix.begin()在当it!二from.end()，执行如下操作4.
3、 遇到数字或小数点时将其加入到后缀表达式：case 1 : case 2 : case 3 : case4 : case 5 : case 6 : case 7 : case8 : case9 : case 0 : case .:(to=to+*it;break;5. 遇到操作符(+ ,-,*,/, %)时，如果此时栈顶操作符的优 先级比 此时的操作符优先级低，则将其入栈，否则将栈中的操作符从栈顶逐个 加入到后缀表达式，直到栈空或者遇到左括号，并将此时的操作符加入 到栈中，在此过程中需判断表达式中是否出现输入错误：case + : case - : case * : case / : case
4、 %: (if (it+1)=from.end()(cout输入错误：运算符号右边缺少运算数e ndl;return false ;if (*it= * |*it=/ )&it=from.begin()coutvv输入错误：运算符号左边缺少运算数e ndl;return false ;if (it+1) !=from.end()&(*(it+1)=+ |*(it+1)=- |*(it+1)=* |*(it+1)=/(ll*(it+1)=%)( coutvv输入错误：运算符号连续出现e ndl; return false ; to=to+ ; | if (sym.empty() ( sym.pu
5、sh(*it); break;tem=sym.top();while (pri*it=pritem&!sym.empty()&tem!= ()(to=to+tem+ ;sym.pop();if (sym.empty() break;tem=sym.top();sym.push(*it);break; 6. 遇到“(”时，直接将其加入操作符栈，并且检测输入错误，并且当括号后的第一个符号为-时，说明用户试图输 入负号，这种情 况我们向目标表达式输出一个0,以达到处理负号的目 的：case (:(if (it+1)=from.end()(coutvv输入错误：表达式以左括号结尾e ndl;retur
6、n false ; /若以+或者-开头，则按照正负号看待，向目标表达式中加入一个0if (*(it+1)=- |*(it+1)=+)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)!=* &*(it-1)!=/ &*(it-1)!= % &*(it-1)!=()(cout输入错误：左括号左边不能为运
7、算数或右括号e ndl;return false ;sym.push(*it);break;5.遇到“)”时，将栈中的操作符从栈顶逐个弹出并放入后缀表达式中，直到在栈中遇到“(”，并将“(”从栈中弹出：case ):(if (it+1)!=from.end()&*(it+1)!=+ &*(it+1)!= - &*(it+1)!=* &*(it+1)!= / &*(it+1)!= % &*(it+1)!=)( coutvv输入错误：右括号右边不能为运算数e ndl; |return false ; Iif (it 匚 from.begin()&(*(it-1)=+ |*(it-1)=- |*(i
8、t-1)=* |*(it-1)=/ |*(it-1)=%)(coutvv输入错误：右括号左边不能为运算符号endl;return false ;)to=to+ ;if (sym.empty()(coutvv输入错误：表达式以右括号开始e ndl;return false ;tem=sym.top();while (tem!=()(to=to+tem+ ;sym.pop(); | if (sym.empty() (coutvv输入错误：括号匹配有误endl; return false ;tem=sym.top();sym.pop();break;B .计算后缀表达式的主要思想：逐个字符的扫描后缀
9、表达式，遇到单个数字或小数点时则先将 其将其存到一个字符串中，当遇到后缀表达式中的分隔符(这里 使用空格)时，则将这个字符串转化为数字放到堆栈 n umstack 中；case 1 : case 2 : case 3 : case4 : case 5 : case 6 : case 7 : case 8 : case9 : case 0: case .:(n umtemp+=*it;break;case :(if (numtemp!=)(if (numtemp.find( . )&numtemp.find( . ,(numtemp.find( . )+1)!= string :npos)(co
10、ut输入错误：小数点数目超出：+n umtempvve ndl;return false ;strm.str( numtemp); strmd;n umstack.push(d); numtemp=; strm.str(); strm.clear();break;break;2.遇到操作符+, -,*,/, %时，将堆栈numstack中的栈顶的两个数取出来，进行相应操作的运算，并将结果加入到堆栈n umstack中；case +:(d2=n umstack.top();n umstack.pop();d1= numstack.top();n umstack.pop();n umstack.p
11、ush(d1+d2);break;cased2=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 7(d2=n umstack.top();n umstack.pop();if (fabs(d2)0.0000001)cout输入错误：除数不能为
12、0e ndl; return false ;d1= numstack.top();n umstack.pop();n umstack.push(d1/d2); break;case T%f :d2=n umstack.top();n umstack.pop();d1= numstack.top();n umstack.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;
13、else(cerr 输入错误：求模操作只能作用于整数endl;return false ;3直到后缀表达式扫描完并且堆栈numstack中只有一个数值,则此数值为计算的最终结果，否则说明输入有误分析与探讨:1、测试结果分析：测试结果见本篇开始的实际输入输出结果。该计算器几乎实现了所有相关功能，包括简单计算、负数小数处 理，容错，并且健壮性好，对于错误的表达式可以给出适当提示，不 会导致程序崩溃。2、算法分析1、 对于中缀表达式转换成后缀表达式：时间复杂性为0(n)2、 对于后缀表达式的计算：时间复杂性为0(n)综上，该程序算法的时间复杂度为0(n)3、算法改进该程序存在的主要问题是命令行式的用户界面不够友好。Windows下的用户图形界面需要MFC方面的知识，因为时间 关系没有进行这方面的深入学习。附录：源代码文件一 .ExpressionHandler.h#include #include #include #include #include using namespacestd;class ExpressionHandler (public :ExpressionHandler( string exp)( this -exp=exp;b
