数据结构课程设计-计算器

1、数据结构课程设计报告实验一：计算器设计要求1、问题描述：设计一个计算器，可以实现计算器的简 单运算，输由并检验结果的正确性，以及检验运算表达式的 正确性。2、输入：不含变量的数学表达式的中缀形式，可以接 受的操作符包括+、-、*、/、（、）。具体事例如下：3、输由：如果表达式正确，则输由表达式的正确结果; 如果表达式非法，则输由错误信息。具体事例如下：知识点：堆栈、队列 实际输入输生情况:正确的表达式对负数的处理表达式括号不匹配dadocumentsvisuai studio 2012ptqec(sprqjeaidetugproject 1 xxe表达式由现非法字符表达式中操作符位置错误w运算

2、符号连续出现意挺继续除或本模认真的表达式，申可不能有空格求余操作符左右由现非整数其他输入错误 数据结构与算法描述解决问题的整体思路：将用户输入的中缀表达式转换成后缀表达式，再利用转换后的后缀表达式进行计算得出结果。解决本问题所需要的数据结构与算法：用到的数据结构是堆栈。主要算法描述如下：a.将中缀表达式转换为后缀表达式：1.将中缀表达式从头逐个字符扫描，在此过程中，遇到的字符有以下几种情况：1）数字2）小数点3）合法操作符+ - * / %4）左括号5）右括号6）非法字符2 .首先为操作符初始化一个 map priority ,用于 保存各个操作符的优先级，其中+ -为0, * / %为13

3、.对于输入的字符串from和输出的字符串to,采用以下过程：初始化遍历器 std:string:iterator it=infix.begin()在当it!=from.end(),执行如下操作4 .遇到数字或小数点时将其加入到后缀表达式：case 1 : case 2 : case 3 : case4 : case 5 : case 6 : case 7 : case 8 : case9 : case 0 : case .:to=to+*it; break;5 .遇到操作符(+,-,*,/, %)时，如果此时栈顶操作符的优 先级比此时的操作符优先级低，则将其入栈，否则将栈中的操作符从 栈顶逐个

4、加入到后缀表达式，直到栈空或者遇到左括号，并将此时的 操作符加入到栈中，在此过程中需判断表达式中是否出现输入错误：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)=/|

5、*(it+1)=%)cout输入错误：运算符号连续出现endl;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(); |sym.push(*it); break;6 .遇到“(”时，直接将其加入操作符栈，并且检测输入错误，并且当括号后的第一个符号为-时，说明用户试图输入负号，这种情况我们向目标表达式输

6、出一个0,以达到处理负号的目的：case (:if (it+1)=from.end() cout输入错误：表达式以左括号结尾endl;return false ;/若以+或者-开头，则按照正负号看待，向目标表达式中加入一个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)!=

7、- &*(it-1)!=&*(it-1)!=/ &*(it-1)!= % &*(it-1)!=()cout输入错误：左括号左边不能为运算数或右括号endl;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)!=)cout输入错误：右括号右边不能为运算数endl;return

8、false ;iif (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()

9、;sym.pop();break; b.计算后缀表达式的主要思想：逐个字符的扫描后缀表达式，遇到单个数字或小数点时则先将 其将其存到一个字符串中，当遇到后缀表达式中的分隔符(这里 使用空格)时，则将这个字符串转化为数字放到堆栈numstack中；case 1 : case 2 : case 3 : case4 : case 5 : case 6 : case 7 : case 8 : case9 : case 0 : case .:numtemp+=*it;break;case : if (numtemp!=) if (numtemp.find( . )&numtemp.find( . ,(n

10、umtemp.find( . )+1)!= string 二npos) cout输入错误：小数点数目超出：+numtempd;numstack.push(d);numtemp=;strm.str();strm.clear();break;break;2.遇到操作符+numstack,*, /, %时，将堆栈numstack中的栈顶的两个数取出来，进行相应操作的运算，并将结果加入到堆栈中；case +:二d2=numstack.top();numstack.pop();d1=numstack.top();numstack.pop();numstack.push(d1+d2); break;cas

11、e -d2=numstack.top();numstack.pop();d1=numstack.top();numstack.pop();numstack.push(d1-d2); break; case *d2=numstack.top(); numstack.pop(); i d1=numstack.top(); numstack.pop();numstack.push(d1*d2); break;case /d2=numstack.top(); numstack.pop();if (fabs(d2)0.0000001) cout输入错误：除数不能为0endl;return false ;

12、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;elsecerr 输入错误：求模操作只能作用于整数endl;re

13、turn false ; 3.直到后缀表达式扫描完并且堆栈numstack中只有一个数值,则此数值为计算的最终结果，否则说明输入有误。分析与探讨：1、测试结果分析：测试结果见本篇开始的实际输入输出结果。该计算器几乎实现了所有相关功能，包括简单计算、负数小数处 理，容错，并且健壮性好，对于错误的表达式可以给出适当提示，不 会导致程序崩溃。2、算法分析1、对于中缀表达式转换成后缀表达式：时间复杂性为o(n)2、对于后缀表达式的计算：时间复杂性为o(n)综上，该程序算法的时间复杂度为o(n)3、算法改进该程序存在的主要问题是命令行式的用户界面不够友好。windows下的用户图形界面需要 mfc方面的

14、知识，因为时 间关系没有进行这方面的深入学习。附录：源代码文件一 .expressionhandler.h#includestring，#include #include #include #include using namespacestd;class expressionhandler public :expressionhandler( string exp) this -exp=exp;bool infixtoprofix( string & exp);bool doprofix( string profix, double &result); private :string exp

15、;；文件二.expressionhandler.cpp/coded by cs_zhanglin#include expressionhandler.hbool expressionhandler 二infixtoprofix( string & exp)string from= this -exp;string to=;stack sym;map：char,int pri;char tem;pri + =1;pri - =1;pri * =2;pri / =2;pri % =2;string 二 iterator it=from.begin();if (*it= + |*it= - )to+

16、= 0;while (it!=from.end()/cout1endl;switch (*it) case 1 : case 2 : case 3 : case4 : case 5 : case 6 : case 7 : case8 : case9 : case 0 : case .:to=to+*it;break; case + : case - : case * : case / : case %:if (it+1)=from.end() cout输入错误：运算符号右边缺少运算数endl;return false ;if (*it= * |*it= / )&it=from.begin()c

17、out输入错误：运算符号左边缺少运算数endl;return false ;iif (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=pritem&!sym.empty()&tem!= () to=to+tem+ ; sym.pop();if (sym.empty() br

18、eak; 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输入错误：左括号右边不能为运算符号或右括号endl;return false ;if (it!=from.begin()&(*(it-1)!=+ &*(it-1)!= - &*(

19、it-1)!=* &*(it-1)!=/ &*(it-1)!= % &*(it-1)!=()cout输入错误：左括号左边不能为运算数或右括号endl;return false ; sym.push(*it); break; case )if (it+1)!=from.end()&*(it+1)!=+ &*(it+1)!= - &*(it+1)!= * &*(it+1)!= / &*(it+1)!= % &*(it+1)!=) cout输入错误：右括号右边不能为运算数endl;return false ;iif (it!=from.begin()&(*(it-1)=+ |*(it-1)=- |*

20、(it-1)=* |*(it-1)=/ |*(it-1)=%) cout输入错误：右括号左边不能为运算符号endl;return false ; to=to+ ; if (sym.empty() cout输入错误：表达式以右括号开始endl; return false ;1 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输入错误：未

21、知符号endl; return false ;+it;if (!sym.empty()to=to+ ;tem=sym.top();while (!sym.empty() if (tem=()cout输入错误：括号匹配有误 numstack;stringstream strm;double d,d1,d2;for (string 二 iterator it= profix .begin();it!= profix .end();+it) :caseswitch (*it) case 1 : case 2 : case 3 : case4 : case 5 : case 6 : case 78 :

22、 case9 : case 0 : case .:numtemp+=*it;break; case :if (numtemp!=)if (numtemp.find( . )&numtemp.find( . ,(numtemp.find( . )+1)!= string :npos)cout输入错误：小数点数目超出:+numtempd; | numstack.push(d); numtemp=;strm.str();strm.clear(); break;break;case +:d2=numstack.top(); numstack.pop();d1=numstack.top();numsta

23、ck.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输入错误：除数不能为0endl;return false ;d1=numstack.top();numstack.pop();numstack.p