小型计算器

实 验 报 告课程名称 算法与数据结构 姓 名 何 劼 专 业 计算机科学与技术 部 别 指导教员 日 期 年 月 日 2实验项目列表序号 实验项目名称 成绩01 稀疏多项式02 小型计算器0304050607080910111213141516总评成绩： 教员签字：3实验报告姓名：何劼学号：专业：计算机科学与技术 部别： 实验地点： 实验时间： 2012、3、20 设备编号： 同组人员： 指导教员签字： 成绩：教员评语：一、实验名称编写模拟小型计算器功能的程序。二、实验目的1.掌握栈的应用。2.掌握“拼数”技术。3.掌握字符串处理方法。4三、实验内容和要求（1） 完成对正整数的加减乘除运算，不进行错误检查。输入一个数，一个运算符和另一个数，按=键和 Enter键。输出计算结果。例如，输入：123+305=按 Enter键后，输出计算结果。（2）完成正整数的混合四则运算，要考虑优先级，但算式中不带括号，程序不作错误检查。例如，输入：12+34*54-21/3=按 Enter键后，输出计算结果。（3）完成实数的混合四则运算，不作错误检查。（4）完成带括号的混合四则运算，不作错误检查。例如，输入：12*(2+4)/5=按 Enter键后，输出计算结果。（5）完成带负数，带数学函数的混合四则运算。例如，输入：-12.3+sin（0.12）=按 Enter键后，输出计算结果。这一层主要练习如何处理负数和函数等“一目”运算。（6）完成带错误检查的用于任一数学表达式的计算。当检查到错误时最好指明错误的 位置和出错原因。5例如，在第 5个字符处少右括号、或少运算符、多运算符、数值中出现字母等非数值字符。四、实验环境1硬件环境：PC 机2软件环境：Windows 操作系统，VC+集成开发环境五、算法设计思想题目的第一级即一个简单的整数拼数函数，所以程序主要问题是从第二级开始的。模拟人脑的进行正整数四则运算的过程，设计者发现，运算符的运算优先次序与栈的“后进先出”特点是相切合的，所以整个程序是建立在栈结构的基础之上的。但是，运算式是由数字和和运算符构成的，所以建立了一个数栈（num）一个符号栈（symb） 。当扫描指针扫描到数时，调用拼数函数，然后将得到的数字进入数栈；反之扫描到符号时，则需调用优先级比较函数（judge） ，比较符号栈顶的符号和扫描到的符号的优先级。若后者优先级大于前者，则扫描到的运算符入栈，扫描指针后移；如果栈顶元素优先级高于扫描到的函数，则调用计算函数（count）进行计算。Count函数将弹出符号栈中的栈顶元素和数栈的两个元素，然后两者6进行弹出的运算符所对应的计算。得到的结果存入数栈，然后扫描指针后移。当符号栈中的元素为空并且扫描指针指向“=”号时，输出结果。第二级运算实现。第三级只是将前一级中的拼数函数进行了补充修改，用以实现实数的拼数问题。这里就不加赘述了。第四级是要求完成带括号的运算。设计者对括号进行了以下条件限制：左括号直接入栈；左、右括号优先级均比一般运算符（+、-、*、/、）低；扫描指针为右括号并且符号栈栈顶元素为左括号时，左括号出栈，扫描指针后移。通过这三条即可使得括号里面的内容先进行计算。第五级要求实现负数、sin（）等一目运算。当扫描到字母时，调用转换函数（change2） ，将输入的字母字符串和负号转换为对应的单个字符运算符（这样便于 judge函数的判断和 count函数的计算） 。然后根据具体运算先后次序补充 judge函数优先级，补充 count函数。即实现了一目运算。六、主要问题与解决方法（一）当程序刚调试完成时，整个程序代码很混乱，if 语句的嵌套过多。7其中单单求解函数（result）长度就多达 130行，使人阅读起来非常的不方便。于是，设计者根据需要，将拼数函数、字符串转换函数、优先级比较函数和计算函数单独提取了出来，并且加上了一些必要的备注，增加了程序的可读性，便于日后查看修改。（二）实现第二级时，当第一个符号入栈时，符号栈为空，无法做优先级比较。所以设计者一开始便在符号栈的栈底填入了一个“#” ，其优先级最低。（三）当扫描指针读取到 sin的时候，实际上是读到的 s、i、n 单个字符，于是编写了 change2函数，以实现类似于拼数函数的功能。一开始设计者考虑的是用字符数组的结构，通过指针扫描的方式实现，但在实际编写过程中发现这样做过于复杂且问题太多，考虑到数学函数名较短的特点，便直接采用了条件结构 if加/栈的初始长度unsigned delta=10;/栈的追加长度typedef char eletype1;typedef eletype1 *eptr1;typedef double eletype2;typedef eletype2 *eptr2;eptr1 p1;eptr2 p2;void numpush(eptr2 p2=(eptr2)realloc(p2,m*sizeof(eletype2);top2=p2+m-delta;top2+;*top2=x;11int numpop(eptr2 x=*top2;top2-;return SUCC;void symbpush(eptr1 p1=(eptr1)realloc(p1,m*sizeof(eletype1);top1=p1+m-delta;+top1;*top1=x;int symbpop(eptr1 x=*top1;top1-;return SUCC;int judge(char p,char a)/存优先级表以及做优先级比较的函数eletype1 symb=+,-,j,s,c,t,*,/,=,#,(,);int first=2,2,3,4,4,4,5,5,6,0,-1,1,1;int i=0,j=0;while(a!=symbi)i+;while(p!=symbj)j+;if(firstifirstj)return(SUCC);else return(FAIL);void change(eletype1 a,int q=0;while(ai=0return 0;return 1;eletype2 count(eptr1 eletype2 y,z;symbpop(p1,top1,w);switch(w)case +:numpop(p2,top2,z);numpop(p2,top2,y);z=y+z;break;case -:numpop(p2,top2,z);numpop(p2,top2,y);z=y-z;break;case *:numpop(p2,top2,z);numpop(p2,top2,y);z=y*z;break;case /:numpop(p2,top2,z);numpop(p2,top2,y);z=y/z;break;case :numpop(p2,top2,z);numpop(p2,top2,y);z=pow(y,z);break;case j:numpop(p2,top2,z);z=-z;break;15case s:numpop(p2,top2,z);z=sin(z);break;case t:numpop(p2,top2,z);z=tan(z);break;case c:numpop(p2,top2,z);z=cos(z);break;default:printf(“error!n“);break;return(z);void result(eletype1 a)eptr1 p1,top1;eptr2 p2,top2;int i=0;eletype1 w;eletype2 z=0,q;top1=p1=(eptr1)malloc(m*sizeof(eletype1);top2=p2=(eptr2)malloc(m*sizeof(eletype2);*top1=#;*top2=NULL;while(ai)/*数字的处理*/if(ai=0symbpush(p1,top1,w);else if(*top1=(i+;else if(ai=()/左括号直接进栈symbpush(p1,top1,ai);i+;else if(judge(*top1,ai)/判断优先级，比栈顶元素大进栈，反之栈顶出栈symbpush(p1,top1,ai);i+;/*/else z=count(p1,top1,p2,top2);numpush(p2,top2,z); void main()int i,a;eletype1 strN;printf(“本计算器可执行包括+，-，*，/，sin（） ，cos（） ，17tan（）的多