《数据结构和算法设计》实验报告

完美WORD格式专业整理知识分享《数据结构与算法设计》实验报告——实验二一、实验目的完美WORD格式专业整理知识分享按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。二、实验内容简单计算器。请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求：①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。②输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。例如，输入：4+2*5=输出：14输入：(4+2)*(2-10)=输出：-48三、程序设计概要设计1、宏定义#defineTRUE1#defineFALSE0#defineOK1#defineERROR02、基本函数：（1）voidInitStack_char(SqStack*S)//char型栈初始化（2）voidInitStack_int(sqStack*S)//int型栈初始化（3）voidPush_char(SqStack*S,charch)//char型元素进栈（4）voidPush_int(sqStack*S,intnum)//int型元素进栈（5）charGetTop_char(SqStack*S)//取char型栈顶元素（6）intGetTop_int(sqStack*S)//取int型栈顶元素（7）StatusIn(charc)//判断是否为运算符，若是运算符则返回，否则返回（8）charPrecede(chara,charb)//判断两运算符的先后次序（9）StatusPop_char(SqStack*S,char&x)//char型栈出栈（10）StatusPop_int(sqStack*S,int&x)//int型栈出栈（11）intOperate(inta,chartheta,intb)//计算a和b运算结果3、流程图完美WORD格式专业整理知识分享详细设计数据类型typedefstructnode//构造char型栈{charch;structnode*next;}node;typedefstruct{structnode*base;structnode*top;}SqStack;typedefstructlnode//构造int型栈{intnum;完美WORD格式专业整理知识分享structlnode*next;}lnode;typedefstruct{structlnode*base;structlnode*top;}sqStack;操作部分voidInitStack_char(SqStack*S){S-base=(node*)malloc(sizeof(node));S-base-next=NULL;S-top=S-base;}//char型栈初始化voidInitStack_int(sqStack*S){S-base=(lnode*)malloc(sizeof(lnode));S-base-next=NULL;S-top=S-base;}//int型栈初始化voidPush_char(SqStack*S,charch){node*p;p=(node*)malloc(sizeof(node));p-ch=ch;p-next=S-top;S-top=p;}//char型元素进栈完美WORD格式专业整理知识分享StatusPush_int(sqStack*S,intnum){lnode*p;p=(lnode*)malloc(sizeof(lnode));p-num=num;p-next=S-top;S-top=p;returnOK;}//int型元素进栈charGetTop_char(SqStack*S){return(S-top-ch);}//取char型栈顶元素intGetTop_int(sqStack*S){return(S-top-num);}//取int型栈顶元素StatusPop_char(SqStack*S,char&x){if(S-base==S-top)returnERROR;node*p;p=S-top;x=p-ch;S-top=p-next;free(p);完美WORD格式专业整理知识分享returnOK;}//char型栈出栈StatusPop_int(sqStack*S,int&x){if(S-base==S-top)returnERROR;lnode*p;p=S-top;x=p-num;S-top=p-next;free(p);returnOK;}//int型栈出栈计算功能intOperate(inta,chartheta,intb){inti,z=1;switch(theta){case'+':z=(a+b);break;case'-':z=(a-b);break;case'*':z=(a*b);break;case'/':z=(a/b);break;case'^':for(i=1;i=b;i++)z=z*a;break;}return(z);完美WORD格式专业整理知识分享}//计算a和b运算结果StatusIn(charc){if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='='||c=='^')returnOK;elsereturnERROR;}//判断是否为运算符charPrecede(chara,charb){if(a=='+'||a=='-'){if(b=='+'||b=='-'||b==')'||b=='=')return'';elsereturn'';}if(a=='*'||a=='/'){if(b=='('||b=='^')return'';elsereturn'';}if(a=='('){if(b==')')return'=';完美WORD格式专业整理知识分享elsereturn'';}if(a==')'){if(b!='(')return'';}if(a=='#'){if(b=='=')return'=';elsereturn'';}if(a=='^')return('');}//判断两运算符的先后次序主函数intmain()//主函数{charc,x,theta;inta,b,c1;//定义变量SqStackOPTR;//定义字符栈sqStackOPNR;//定义整型栈InitStack_char(&OPTR);//初始化InitStack_int(&OPNR);//初始化Push_char(&OPTR,'#');//将字符型栈底设为#c=getchar();//从键盘输入得到字符while(c!='='||GetTop_char(&OPTR)!='#')//判定是否执行循环完美WORD格式专业整理知识分享{if(!In(c)){c1=0;while(!In(c)){c1=c1*10+c-'0';c=getchar();}Push_int(&OPNR,c1);}//当扫描字符不是运算符时，转化为整型数存入栈中else{switch(Precede(GetTop_char(&OPTR),c))//判定运算符的优先关系{case'':Push_char(&OPTR,c);c=getchar();break;//当前运算符优先级高，存入char栈case'=':Pop_char(&OPTR,c);c=getchar();break;//运算符次序相等，存入char栈case''://当前运算符优先级低Pop_char(&OPTR,theta);Pop_int(&OPNR,b);Pop_int(&OPNR,a);Push_int(&OPNR,Operate(a,theta,b));//计算运算结果，并存入int栈break;//继续循环}}完美WORD格式专业整理知识分享}printf(%d\n,GetTop_int(&OPNR));//计算完成，取出int栈顶元素，并输出return0;}四、程序调试分析编写程序的过程中遇到了很多的问题，最突出的两个问题就是整数和两位数的运算处理，一开始修改了主函数部分之后，原来可以执行一位数运算的程序出现了error，由于没有及时保存，并且之前的代码无法恢复，只得重新编写一次。第二次编写理清思路之后，在课本和网上资料的辅助下，终于成功的编出了程序并且可以完美执行。经验告诉了我在编程的时候一定要注意经常进行调试，只有学会调试才能处理好大程序的编写，否则极其容易出错。五、用户使用说明1.运行程序，2.将整个表达式从键盘键入，以“=”结束，回车可得到结果。六、程序运行结果（1）输入：（11+3）*5=输出：70（2）输入：(31-13)/(9-3)=输出：6七、程序清单#includestdio.h#includestdlib.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0typedefintStatus;typedefstructnode//构造char型栈{charch;structnode*next;}node;typedefstruct{structnode*base;完美WORD格式专业整理知识分享structnode*top;}SqStack;typedefstructlnode//构造int型栈{intnum;structlnode*next;}lnode;typedefstruct{structlnode*base;structlnode*top;}sqStack;voidInitStack_char(SqStack*S){S-base=(node*)malloc(sizeof(node));S-base-next=NULL;S-top=S-base;}//char型栈初始化voidInitStack_int(sqStack*S){S-base=(lnode*)malloc(sizeof(lnode));S-base-next=NULL;S-top=S-base;}//int型栈初始化voidPush_char(SqStack*S,charch){node*p;p=(node*)malloc(sizeof(node));p-ch=ch;p-next=S-top;S-top=p;}//char型元素进栈StatusPush_int(sqStack*S,intnum){lnode*p;p=(lnode*)malloc(sizeof(lnode));p-num=num;p-next=S-top;完美WORD格式专业整理知识分享S-top=p;returnOK;}//int型元素进栈charGetTop_char(SqStack*S){return(S-top-ch);}//取char型栈顶元素intGetTop_int(sqStack*S){return(S-top-num);}//取int型栈顶元素StatusPop_char(SqStack*S,char&x){if(S-base==S-top)returnERROR;node*p;p=S-top;x=p-ch;S-top=p-next;free(p);returnOK;}//char型栈出栈StatusPop_int(sqStack*S,int&x){if(S-base==S-top)returnERROR;lnode*p;p=S-top;x=p-num;S-top=p-next;free(p);returnOK;}//int型栈出栈intOperate(inta,chartheta,intb){inti,z=1;switch(theta){case'+':z=(a+b);break;完美WORD格式专业整理知识分享case'-':z