数据结构 模拟乘法器

1、课程设计题 目 名 称 设计一个模拟计算器 课 程 名 称 数 据 结 构 学 生 姓 名 学 号 专 业 电子信息科学与技术 指 导 教 师 2015年 12 月 30 日一：问题分析和任务定义本程序写的是模拟计算器。要求设计一个模拟计算器的程序，要求对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解。这里可以做一个扩展，比如实现求某数的次方，求模，一些常用的三角函数等。这个程序实际上就是对一个表达式进行计算。而一个算术表达式中包含各种运算符，每个运算符的等级可能会不同，这就成了本程序需要解决的一个主要的问题之一了。另外计算器中需要有各种数学函数，比如：abs sq

2、rt sin cos tan等，如何对这些函数进行处理，也是本程序能成功的一个关键。还有一个问题就是如何处理操作符和操作数之间的关系也是一个要点。例如：1+2*(3-2/1)，经过怎么样的变换和处理能得出结果。数据的输入这里应该要用字符，然后通过字符和整形之间的关系进行转换即可，这样处理的话，就方便很多了。二：概要设计和数据结构选择输入的时候将一个算术表达式用一个字符数组来接收，故需要对这个数组进行处理，让操作数和操作符分开，这里我想把开始的算术表达式转换成一个后缀表达式，这样在进行计算的时候就简单多了。而在转换的过程中，对运算符的处理极为重要，这里运用堆栈，用堆栈的先进后出的特点，来处理运算

3、符优先级的问题，让其成功转换成后缀表达式。而在对后缀表达式进行处理的时候，又需要一个堆栈，这个堆栈存放操作数的。并将运算结果存入该栈中。两个堆栈的数据结构如下：struct char dataMaxlen;int top;optr; /定义运算符栈struct double dataMaxlen;int top;opnd; /定义操作数栈这里定义了类型，并且一起定义了两者类型的对象optr,opnd。在将算术表达式转换成后缀表达式，定义change函数；在对后缀表达式进行处理时，定义jisuan函数，另外本程序有个欢迎界面，由meun函数实现。因此主函数于各函数之间的关系为： meun() j

4、isuan()本程序实现的流程：三：详细设计和编码首先定义两个数组，p400用来存放算术表达式，q400用来存放后缀表达式。由前面的数据结构定义两个对象，。当输入一个表达式后，定义i作为q的下标，定义dh=1表示是负号，初始化运算符栈optr.top=-1;让后对进行扫描，当指向的为数字字符，则将此字符如，后在往中输入，具体为： while (*p>='0' && *p<='9')qi=*p;i+; p+; if (*p='.') qi='.' i+; p+;while (*p>='0&#

5、39; && *p<='9')qi=*p;i+; p+;qi='#' i+; dh=0;p后移，继续扫描，当遇到或时，执行 if (dh=1) if (*p='-')optr.top+;optr.dataoptr.top='' p+; break; while (optr.top!=-1 && optr.dataoptr.top!='(') qi=optr.dataoptr.top;optr.top-; i+;optr.top+;optr.dataoptr.top=*p; p+

6、; dh=0; break;当遇到*或/时，先查看操作符栈中是否有优秀级比它大的或者一样大的运算符，有的话就将其他的出栈，最后自己入栈。执行：while (optr.dataoptr.top='*' | optr.dataoptr.top='/'| optr.dataoptr.top='s') qi=optr.dataoptr.top;optr.top-; i+; optr.top+;optr.dataoptr.top=*p; p+; dh=0; break;当遇到（时，此时不需要别的其他的操作，只需将其入操作符栈，并将dh=0;当遇到）时，此时

7、需要将（之前的操作符全部出栈，具体操作如下：while (optr.dataoptr.top!='(') qi=optr.dataoptr.top;optr.top-; i+;optr.top-; p+; dh=0; break;当遇到时，根据运算符的优先级，执行：while (optr.dataoptr.top='') qi=optr.dataoptr.top;optr.top-;i+;optr.top+;optr.dataoptr.top=*p;p+;dh=0;break;遇到时的操作和差不多，这里就不做介绍了。当遇到数学函数的相关符号时，这里以sin 为例

8、，当扫描时，还需要扫描后面的两个字符，当它们是in时，说明就是sin函数的符号，此时将此函数的标志入操作符栈，当其为qrt时，说明是sqrt函数，此时将sqrt函数的标志入栈，这里的标志是自己定的。如果都不是上面两种情况，说明输入有误，跳回。具体的程序如下：if(*(p+1)='i' | *(p+1)='I')&&(*(p+2)='n' | *(p+2)='N') optr.top+;optr.dataoptr.top='s'p+=3; dh=0;break; elseif(*(p+1)='

9、q'| *(p+1)='Q')&&(*(p+2)='r' | *(p+2)='R')&&(*(p+3)='t' | *(p+3)='T') optr.top+;optr.dataoptr.top='q'p+=4;dh=0;break;else cout<<endl<<"有错误符号"<<endl; return error; 其他的数学函数的操作都是类似的，这里就不一一说明了。这里值得注意的是，当将扫描完时

10、，操作符栈并未一定为空，故需要将操作符栈里的数据全部出栈：while (optr.top!=-1) qi=optr.dataoptr.top;i+; optr.top-; 以上是将算术表达式转换成后缀表达式。还要对后缀表达式进行计算，才能得到结果。首先还是对表达式进行扫描，遇到数字符时，先将其转换成整形后，再判断是否有小数点存在，继续扫描直到遇到运算符，让后通过运算，将次数转换成小数，最后入栈。 具体程序实现：d=0; while (*q>='0' && *q<='9') d=10*d+(*q-'0'); q+; x=

11、0.1;if (*q='.')q+;while (*q>='0' && *q<='9') d=d+x*(*q-'0');x*=0.1; q+; 当遇到操作符时，为双目运算符时，只需要将操作数栈的栈顶和次栈顶数拿出来进行相应的计算，并将其压入次栈顶。为单目运算符时，只需将操作数栈顶元素进行运算即可，并将运算符压入栈即可。这里以 / 和为例。 其余的均和此类似。if (opnd.dataopnd.top!=0)opnd.dataopnd.top-1=opnd.dataopnd.top-1/opnd.data

12、opnd.top;else cout<<endl<<"除数不能为零!"<<endl;return error; 和opnd.top-;break;opnd.dataopnd.top=sin(opnd.dataopnd.top);当q都扫描完时， 返回操作数栈顶元素就是计算的结果。四：上机调试在语法上的错误，出现过很多，比如少了一个括号，少了个分号，这些问题都是日常写程序中经常出现的问题，想要避免有点难，不过这些错误根据编译器的提示和警告，就能很快的该出来。就图1中出现的问题，这个问题是在#define error 1234567时出现的，

13、这个问题我一直想不同，我定义123456789时可以通过编译，而变成1234567就不行了，通过向老师请教，发现这里的error和编译器里的定义重合了，故不能通过。解决办法是将这里的error改成derror，这样在函数中error相应的也要该。在逻辑上的错误，主要就是算法中出现的问题，本程序中的算法有点复杂，在表达式转换成后缀表达式的过程中就出现了很多的错误。这里举出一个简单的错误，由于本程序在写的时候，定义了derror=1234567在程序中就不能出现这个计算结果，虽然它超过了本程序的能处理的范围，可是其结果还是1234567，故返回主函数时，在if (change(p,q)=1) k=

14、jisuan(q);if(k=derror)cout<<""elsecout<<"计算结果为："<<k<<endl;这里就会出错。导致图中的错误。解决办法，这里我对这中情况没有做特殊的处理。应为在实际的运算过程中，很少有1234567这个结果出现，几乎是不出现的。如何去定义这个数，一直是个问题。本程序的，在定义的时用了两个数组，故其空间复杂度是n，在算法上，这里我用了一个死循环，当输入不为0时，会一直运行。所以只讨论运行一次的时间复杂度。在转换的函数中，有个while()循环，这里的复杂度是n，而在这个循环

15、里，还存在while()循环，故其时间复杂度是n的平方。在计算函数中，其复杂度也是n的平方。故可知本程序的时间复杂度是n平方。 五.经验和体会 这个程序我一直是很简单的，因为我很久之前就在一直考虑这个问题，但是没有去实现过，以为很简单，可是当真正写起来的时候，发现有点困难。开始的时候用书山的那种方法，可是发现那种方法不适合我，不是有多难，就是我的大脑反应不过来。后来想到用后缀表达式，这样处理起来就方便多了，思路也清晰了很多。在不断的错误中改错，在调试中发现程序中的逻辑错误并改正错误。终于这个程序完成了，心中不免有中自豪感。本程序用编的，在界面下运行的。运行时，程序有个欢迎的界面，并提示输入表达

16、式，在输入时要注意的是，本程序能处理的数据长度最长为位。另外，输入时，结束本程序；如输入的表达式有错误的符号时，程序提示输入错误；当输入正确时，按回车键，即可得到计算结果。六：测试结果经过人工计算，可知以上结果是正确的。参考文献：1 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。2 郑莉 ，董渊，张瑞丰 c+语言程序设计 北京：清华大学出版社，2004七：附录（源程序代码）#include "iostream"#include "math.h"#include "string"#include "s

17、tdlib.h"#include "windows.h"#define derror 1234567#define Maxlen 400using namespace std;struct char dataMaxlen;int top;optr; /定义运算符栈，并定义全局变量struct double dataMaxlen;int top;opnd; /定义操作数栈，并定义全局变量void main() char p400,q400;double k;void meun(); /声明菜单函数int change(char *p, char q); /声明转换函

18、数double jisuan(char *q); /声明计算函数meun();for(;) /循环执行 cout <<"请输入:"cin>>p;if (strcmp(p,"0")=0)return;if (change(p,q)=1) k=jisuan(q);if(k=derror)cout<<""elsecout<<"计算结果为："<<k<<endl;system("pause"); /控制输出格式system("

19、;cls");meun();system("color 0a");cout<<"tt *"<<endl;cout<<" 欢迎使用本计算器"<<endl;cout<<"tt *"<<endl;cout<<endl;cout<<"按0结束本程序"<<endl;int change(char *p, char q) /将算术表达式p转换成表达式后缀表达式q int i=0; /i作为q

20、的下标int dh=1; /dh=1表示是负号optr.top=-1; /初始化运算符栈while (*p!='0') /p表达式未扫描完时循环 switch(*p) /判断各种情况,并做相应的处理case '(': optr.top+;optr.dataoptr.top=*p; dh=1;p+;break;case ')': while (optr.dataoptr.top!='(') qi=optr.dataoptr.top;optr.top-; i+;optr.top-; p+; dh=0; break;case '

21、+':case '-': if (dh=1) / +,-是正负号 if (*p='-')optr.top+;optr.dataoptr.top=''p+; break;while (optr.top!=-1 && optr.dataoptr.top!='(') qi=optr.dataoptr.top;optr.top-; i+;optr.top+;optr.dataoptr.top=*p; p+; dh=0; break;case '*':case '/': while (

22、optr.dataoptr.top='*' | optr.dataoptr.top='/'| optr.dataoptr.top='s') qi=optr.dataoptr.top;optr.top-; i+;optr.top+;optr.dataoptr.top=*p; p+; dh=0; break;case '': while (optr.dataoptr.top='') qi=optr.dataoptr.top;optr.top-;i+;optr.top+;optr.dataoptr.top=*p;p+;d

23、h=0;break;case '%': while (optr.dataoptr.top='%') qi=optr.dataoptr.top;optr.top-;i+;optr.top+;optr.dataoptr.top=*p;p+;dh=0;break;case ' ': p+; break; /消除空格case 's':case 'S': if(*(p+1)='i' | *(p+1)='I')&&(*(p+2)='n' | *(p+2)='

24、;N') optr.top+;optr.dataoptr.top='s'p+=3; dh=0;break;elseif(*(p+1)='q'|*(p+1)='Q')&&(*(p+2)='r'| *(p+2)='R')&&(*(p+3)='t' | *(p+3)='T') optr.top+;optr.dataoptr.top='q'p+=4;dh=0;break;else cout<<endl<<&quo

25、t;有错误符号"<<endl; return derror; case 'c':case 'C': if(*(p+1)='o' | *(p+1)='O')&&(*(p+2)='s' | *(p+2)='S') optr.top+;optr.dataoptr.top='c'p+=3; dh=0;break;else cout<<endl<<"有错误符号"<<endl; return derro

26、r; case 'T':case 't':if(*(p+1)='a'| *(p+1)='A')&&(*(p+2)='n' | *(p+2)='N') optr.top+;optr.dataoptr.top='t'p+=3;dh=0;break;else cout<<endl<<"有错误符号"<<endl; return derror; case 'e':case 'E':if(*(

27、p+1)='x'| *(p+1)='X')&&(*(p+2)='p' | *(p+2)='P') optr.top+;optr.dataoptr.top='e'p+=3;dh=0;break;else cout<<endl<<"有错误符号"<<endl; return derror; case 'a':case 'A': if(*(p+1)='b'| *(p+1)='B')&

28、;&(*(p+2)='s' | *(p+2)='S') optr.top+;optr.dataoptr.top='a'p+=3;dh=0;break;else cout<<endl<<"有错误符号"<<endl; return derror; default:while (*p>='0' && *p<='9') /判断是否为数字qi=*p;i+;p+;if (*p='.') qi='.' i+

29、; p+;while (*p>='0' && *p<='9') qi=*p;i+;p+;qi='#' i+; dh=0;/用#标识一个数值串结束while (optr.top!=-1) /此时p扫描完毕,栈不空时循环 qi=optr.dataoptr.top;i+; optr.top-;qi='0' /给q表达式添加结束标识return 1;double jisuan(char *q) /计算后缀表达式的值 double d,x;opnd.top=-1; /初始化操作数栈while (*q!='

30、0') /q字符串未扫描完时循环 switch (*q) /判断各种情况，并做相应的运算,并入栈case '+':opnd.dataopnd.top-1=opnd.dataopnd.top-1+opnd.dataopnd.top; opnd.top-;break;case '-':opnd.dataopnd.top-1=opnd.dataopnd.top-1-opnd.dataopnd.top; opnd.top-;break;case '*':opnd.dataopnd.top-1=opnd.dataopnd.top-1*opnd.dataopnd.top; opnd.top-;break;case '/': if (opnd.dataopnd.top!=0)opnd.dataopnd.top-1=opnd.dataopnd.top-1/opnd.dataopnd.top;else cout<<endl<<"除数不能为零!"<<endl;return derror;opnd.top-;break;case '':opnd.dataopnd.top-1=pow(opnd.datao