模拟计算器学生姓名：**** 指导老师：****摘 要 本课程设计的课题是设计一个模拟计算器的程序，能够进行表达式的计算，并且表达式中可以包含Abs()和Sqrt()运算在课程设计中，系统开发平台为Windows ，程序设计设计语言采用C++，程序运行平台为Windows 或 *nix本程序的关键就是表达式的分离和处理，在程序设计中，采用了将输入的中缀表达式转化为后缀表达式的方法，具有可靠的运行效率本程序做到了对输入的表达式（表达式可以包含浮点数并且Abs()和Sqrt()中可以嵌套子表达式）进行判定表达式是否合法并且求出表达式的值的功能经过一系列的调试运行，程序实现了设计目标，可以正确的处理用户输入的表达式，对海量级数据都能够通过计算机运算快速解决关键词 C++程序设计；数据结构；表达式运算；栈；中缀表达式；后缀表达式；字符串处理；表达式合法判定；目 录1 引 言 21.1课程设计目的 31.2课程设计内容 32 设计思路与方案 33 详细实现 43.1 表达式的合法判定 43.2 中缀表达式转化为后缀表达式 53.3 处理后缀表达式 73.4 表达式嵌套处理 84 运行环境与结果 84.1 运行环境 84.2 运行结果 85 结束语 11参考文献 12附录1：模拟计算器源程序清单 141 引 言本课程设计主要解决的是传统计算器中，不能对表达式进行运算的问题，通过制作该计算器模拟程序，可以做到快速的求解表达式的值，并且能够判定用户输入的表达式是否合法。
该模拟计算器的核心部分就在用户输入的中缀表达式的转化，程序中用到了“栈”的后进先出的基本性质利用两个“栈”，一个“数据栈”，一个“运算符栈”来把中缀表达式转换成后缀表达式最后利用后缀表达式来求解表达式的值该算法的复杂度为O(n)，能够高效、快速地求解表达式的值，提高用户的效率1.1课程设计目的 数据结构主要是研究计算机存储，组织数据，非数值计算程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域学习数据结构是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高模拟计算器程序主要利用了“栈”这种数据结构来把中缀表达式转化为后缀表达式，并且运用了递归的思想来解决Abs()和Sqrt()中嵌套表达式的问题，其中还有一些统计的思想来判定表达式是否合法的算法1.2课程设计内容本次课程设计为计算器模拟程序，主要解决表达式计算的问题，实现分别按表达式处理的过程分解为几个子过程，详细的求解过程如下：1 用户输入表达式。
2 判定表达式是否合法3 把中缀表达式转化为后缀表达式4 求出后缀表达式的结果5 输出表达式的结果通过设计该程序，从而做到方便的求出一个表达式的值，而不需要一步一步进行运算2 设计思路与方案本课程设计需要考虑许多的问题，首先是表达式的合法判断，然后是字符串表达式提取分离的问题，核心部分就是中缀表达式转化为后缀表达式对于第一个问题，我是分步来判断，首先表达式中是否含有其它非法字符，然后判断括号是否合法，接着判断运算法两边是否合法，比如除法时，除数不能为零对于第二个问题，我是直接转换的，从左到右遍历中缀表达式，把数据全部取出来对于核心问题，利用了“栈”这种“后进先出”的数据结构，利用两个“栈”，一个“数据栈”，一个“运算符栈”来把中缀表达式转换成后缀表达式最后利用后缀表达式来求解表达式的值 上面是数据处理的算法部分本程序用户界面总共分为3个模块，分别是操作提示，数据输入，数据输出如图2.1所示图2.1 用户界面除了实现基本的功能外，我还增加了其它一些功能，比如支持输入数据为浮点数，更重要的是本程序还支持表达式的嵌套运算，例如：A(1+2*S(2))我的实现方法是利用函数的递归调用来解决此问题，即把1+2*S(2)看成一个子表达式，这个子表达式中2也看成子表达式。
这样使得程序的适用范围更加的广泛，适应性更强，能支持更复杂的表达式的运算这也是本程序的优点之一3 详细实现3.1 表达式的合法判定表达式的合法判定过程如图3.1所示是否存在其它字符括号是否合法运算符是否合法 图3.1 表达式的合法判定过程首先是其它字符的判定，从左到右遍历中缀表达式，看是否存在其它非法的然后是判定括号是否的匹配是否和合法，首先把“(”对应为1，相应的“)”对应为-1从左到右遍历表达式，如果遇到括号就加上其对应的值，用sum来保存其累加值如果在中途出现sum小于零的情况，即出现“..... )” 那么的情况，即非法在遍历的最后，还要判断sum的值是否为零，如果为零就是合法，否则就是非法代码如下： for(i=0;i
这里要考虑表达式中出现负数的情况，因此特殊考虑“-”号，判断它的前面是“(”还是没有字符了，那么就是负数3.2 中缀表达式转化为后缀表达式中缀表达式转化为后缀表达式，利用两个“栈”，一个“数据栈”，一个“运算符栈”来把中缀表达式转换成后缀表达式最后利用后缀表达式来求解表达式的值设一个stack存后缀数据，一个rout栈存运算符算法流程如下：（1）从右向左依次取得数据ch2）如果ch是操作数，直接加进stack中3）如果ch是运算符（含左右括号），则： a：如果ch = '('，放入堆栈rout中 b：如果ch = ')'，依次输出堆栈rout中的运算符，直到遇到'('为止 c：如果ch不是')'或者'('，那么就和堆栈rout顶点位置的运算符top做优先级比较 1：如果ch优先级比rtop高，那么将ch放入堆栈rout 2：如果ch优先级低于或者等于rtop，那么输出top到stack中（直到！top或者满足 1），然后将ch放入堆栈rout 可以看出算法复杂度是O(n）的，因此效率是比较高的，能够在1s内处理百万级别长度的表达式。
算法的主要思想是利用“栈”的后进先出的特性，以及运算符的优先级，这里我们定义运算符的优先级；代码如下：int GetKey(char c){ //定义运算符的关键字 int key; switch(c){ case '+':key=1;break; case '-':key=1;break; case '*':key=2;break; case '/':key=2;break; case '(':key=4;break; case ')':key=5;break; } return key;}中缀转化为后缀处理的核心代码如下： /* 双栈,sta1存放后缀表达式,sta2存放运算符符号*/ stack > sta1,sta2; for(i=0;i=num[i].second && sta2.top().second!=4){ sta1.push(sta2.top()); sta2.pop(); } sta2.push(num[i]); //放入当前运算符 } }最后，后缀表达式就存放在sta1栈中，把sta1栈中的结果存放到SufExp中就得到了后缀表达式。
3.3 处理后缀表达式这里也是运用“栈”来处理，运用栈模板在求值过程顺序扫描后缀表达式，每次遇到操作数便将它压入堆栈；遇到运算符，则从栈中弹出两个操作数进行计算，然后再把结果压入堆栈，等到扫描结束时，则表达式的结果就求出来了算法流程如图3.3所示： 后缀表达式 扫描并判定数据类型 从栈中取出数字进行运算 数字压入栈中 栈 结果压入栈中 输出最终结果图 3.3 处理后缀表达式流程核心代码如下：double Expression::GetAns(){ int i; double temp,num1,num2; //num1和num2为运算符两遍的操作数 stack sta; //数据栈 for(i=0;i
其核心代码如下： if(s[i]=='A' || s[i]=='S'){ //遇到Abs()或者Sqrt()递归处理子表达式 Expression temp; //创建子表达式 temp.Init(); for(j=0;i+j+2
一个好的程序应该是一个所占空间小、运行时间短、其他性能也好的程序而要做出一个好的程序则应该通过对算法与其数据结构的时间复杂度和空间复杂度进行实现与改进然而，实际上很难做到十全十美，原因是各要求有时相互抵触，要节约算法的执行时间往往要以牺牲更多的存储空间为代价：而为了节省存储空间又可能要以更多的时间为代价因此，只能根据具体情况有所侧重：如果程序的使用次数较少，则应该力求算法简明易懂，而易于转换为上机程序；如果程序反复多次使用，则应该尽可能选用快速算法；如果解决问题的数据量极大，机器的内存空间较小，则在编写算法时应该考虑如何节省空间本次课程设计培养了了我们独立思考的能力，提高了我们的动手操作水平在具体设计操作中，我们巩固了本学期所学的数据结构与算法的理论知识，进一步提高了自己的编程能力这也是课程设计的最终目的所在通过实际操作，开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力但在程序设计的过程中我也深刻的感受到自己实力的不足，无法灵活的运用各种工具和函数，对于课程所讲的东西也无法在脱离课本的情况中完成，我意识到自己在今后的学习生活中，一定要勤于思考，扎实掌握理论知识，灵活运用课上所学的东西，做一个优秀的程序员。
参考文献[1] Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest. 北京. 算法导论(第三版)[M]. 机械工业出版社:Thomas H.Cormen, 2013[2] 刘汝佳, 黄亮. 北京. 清华大学出版社. 算法艺术与信息学竞赛.[3] 王晓东. 北京. 清华大学出版社. 算法设计与分析（第二版）.附录1：模拟计算器源程序清单// 程序名称：Calculator.cpp// 程序功能：模拟计算器// 程序作者：****// 学号: ****// 最后修改日期：2013-7-5/*课题4：设计一个模拟计算器的程序，要求能对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解 要求：要检查有关运算的条件，并对错误的条件产生报警我的代码在此基础上增加了几个功能：1. 不仅支持整数运算，还支持浮点数运算2. 可支持表达式的嵌套，Ex：A(1+2*S(3)）*/#include #include #include #include #include #include #include using namespace std;#define mem(a,b) memset(a,b,sizeof(a))const int MaxLength=1010; //数组的最大存储空间bool IsNum(char c) //判断是否是数字{ if(c>='0' && c<='9')return true; return false;}bool IsSign(char c) //判断是否是运算符号{ if(c=='+' || c=='-' || c=='*' || c=='/')return true; return false;}int GetKey(char c) //定义运算符的关键字{ int key; switch(c) { case '+':key=1;break; case '-':key=1;break; case '*':key=2;break; case '/':key=2;break; case '(':key=4;break; case ')':key=5;break; } return key;}double Cal(char c,double a,double b) //根据运算符来计算运算结果{ switch(c) { case '+':return a+b; case '-':return a-b; case '*':return a*b; case '/':return a/b; } return 0;}class Graph //图形界面类{public: void Window(); //图形窗口函数};void Graph::Window(){ cout<<" |===============欢迎使用本计算器===============|"< SufExp[MaxLength]; //后缀表达式存储 int Pos[MaxLength]; //中缀表达式中'('对应的')'数组下标位置};void Expression::Input() //表达式输入{ cout<<"请输入您的表达式: "; cin>>s;}void Expression::Init() //表达式数据初始化{ HaveAns=false; mem(Pos,-1);}bool Expression::SloveExp(){ if((HaveAns=CheckExp())==0)return HaveAns=false; //表达式不合法，退出 GetSuffix(); //得到后缀表达式 GetAns(); //根据后缀表达式来得到结果 return true;}bool Expression::CheckExp() //检查表达式是否合法{ int i,j,cnt; int sum=0; for(i=0;i=0;j--){ //遇到')'括号 if(s[j]==')')sum+=1; else if(s[j]=='(')sum-=1; if(sum==0){ //如果sum的值为0,那么找到')'的匹配括号 Pos[j]=i; break; } } } return true; //表达式正确}void Expression::GetSuffix() //得到后缀表达式{ int i,j,w,k=0; char st[MaxLength]; pair num[MaxLength]; //保存后缀表达式，double为数据，int标记符号 for(i=0;i > sta1,sta2; for(i=0;i=num[i].second && sta2.top().second!=4){ sta1.push(sta2.top()); sta2.pop(); } sta2.push(num[i]); //放入当前运算符 } } while(!sta2.empty()){ //如果栈sta2非空,则继续取出sta2中的数据到sta中 sta1.push(sta2.top()); sta2.pop(); } Size=sta1.size(); //后缀表达式长度 for(i=Size-1;!sta1.empty();i--){ //后缀表达式传递给SufExp数组 SufExp[i]=sta1.top(); sta1.pop(); }}double Expression::GetAns(){ int i; double temp,num1,num2; //num1和num2为运算符两遍的操作数 stack sta; //数据栈 for(i=0;i>IsContinue; }while(IsContinue[0]=='y' || IsContinue[0]=='y'); cout<<"欢迎使用"<