模拟计算器学生姓名：**** 指导老师：****摘要本课程设计的课题是设计一个模拟计算器的程序，能够进行表达式的计算，并且表达式中可以包含Abs()和Sqrt()运算。
在课程设计中，系统开发平台为Windows ，程序设计设计语言采用C++，程序运行平台为Windows 或*nix。
本程序的关键就是表达式的分离和处理，在程序设计中，采用了将输入的中缀表达式转化为后缀表达式的方法，具有可靠的运行效率。
本程序做到了对输入的表达式（表达式可以包含浮点数并且Abs()和Sqrt()中可以嵌套子表达式）进行判定表达式是否合法并且求出表达式的值的功能。
经过一系列的调试运行，程序实现了设计目标，可以正确的处理用户输入的表达式，对海量级数据都能够通过计算机运算快速解决。
关键词C++程序设计；数据结构；表达式运算；栈；中缀表达式；后缀表达式；字符串处理；表达式合法判定；目录1 引言 (3)1.1课程设计目的 (3)1.2课程设计内容 (3)2 设计思路与方案 (4)3 详细实现 (5)3.1 表达式的合法判定 (5)3.2 中缀表达式转化为后缀表达式 (5)3.3 处理后缀表达式 (7)3.4 表达式嵌套处理 (8)4 运行环境与结果 (9)4.1 运行环境 (9)4.2 运行结果 (9)5 结束语 (12)参考文献 (13)附录1：模拟计算器源程序清单 (14)1 引言本课程设计主要解决的是传统计算器中，不能对表达式进行运算的问题，通过制作该计算器模拟程序，可以做到快速的求解表达式的值，并且能够判定用户输入的表达式是否合法。
该模拟计算器的核心部分就在用户输入的中缀表达式的转化，程序中用到了“栈”的后进先出的基本性质。
利用两个“栈”，一个“数据栈”，一个“运算符栈”来把中缀表达式转换成后缀表达式。
最后利用后缀表达式来求解表达式的值。
该算法的复杂度为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<s.length();i++){ //检验括号是否合法，以及是否存在非法字符if(!IsNum(s[i]) && !IsSign(s[i]) && s[i]!='('&& s[i]!=')' && s[i]!='A' && s[i]!='S' && s[i]!='.')return false; if(s[i]=='(')sum+=1;else if(s[i]==')')sum-=1;if(sum<0)return false; //括号匹配不合法}运算符判断是否合法，也是遍历一遍表达式，遇到“/”，看其后面的除数是否为零。
这里要考虑表达式中出现负数的情况，因此特殊考虑“-”号，判断它的前面是“(”还是没有字符了，那么就是负数。
3.2 中缀表达式转化为后缀表达式中缀表达式转化为后缀表达式，利用两个“栈”，一个“数据栈”，一个“运算符栈”来把中缀表达式转换成后缀表达式。
最后利用后缀表达式来求解表达式的值。
设一个stack存后缀数据，一个rout栈存运算符。
算法流程如下：（1）从右向左依次取得数据ch。
（2）如果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<pair<double,int> > sta1,sta2;for(i=0;i<k;i++){if(!num[i].second)sta1.push(num[i]); //为数据,直接放入sta1else if(num[i].second==4)sta2.push(num[i]); //为'(',直接放入sta2 /* 为')',从sta2中取出运算符,push到sta1中,直到遇到')' */else if(num[i].second==5){while(sta2.top().second!=4){sta1.push(sta2.top());sta2.pop();}sta2.pop(); //取出'('括号}/*为'+','-','*'或者'/'运算符,取出sta2中的运算符,push到sta1中,直到比sta2栈顶中的优先级大*/else {while(!sta2.empty() && sta2.top().second>=num[i].second && sta2.top().second!=4){sta1.push(sta2.top());sta2.pop();}sta2.push(num[i]); //放入当前运算符}}最后，后缀表达式就存放在sta1栈中，把sta1栈中的结果存放到SufExp 中就得到了后缀表达式。
3.3 处理后缀表达式这里也是运用“栈”来处理，运用栈模板在求值过程顺序扫描后缀表达式，每次遇到操作数便将它压入堆栈；遇到运算符，则从栈中弹出两个操作数进行计算，然后再把结果压入堆栈，等到扫描结束时，则表达式的结果就求出来了。
算图 3.3 处理后缀表达式流程核心代码如下：double Expression::GetAns(){int i;double temp,num1,num2; //num1和num2为运算符两遍的操作数stack<double> sta; //数据栈for(i=0;i<Size;i++){if(!SufExp[i].second){ //为数据sta.push(SufExp[i].first);}else { //为运算符num1=sta.top(); //取出第一个操作数sta.pop();num2=sta.top(); //取出第二个操作数sta.pop();temp=Cal((char)SufExp[i].first,num2,num1);sta.push(temp); //放入操作数结果}}Ans=sta.top();return Ans; //返回最终结果}3.4 表达式嵌套处理如果遇到A()和S()中含有表达式，而不是单纯的数字，例如A(1.1+3.4*S(2.5)),那么就需要对其字表达式“1.1+3.4*S(2.5)”进行递归处理,这个子表达式中还含有子表达式“2.5”,然后再递归处理,依次类推下去。