算是表达式栈实验报告.doc

中南大学数据结构与算法课程实验实验报告题 目 线性表的操作 学生姓名 张悦 学生学号 3901090516 专业班级 软件工程0905班 实验二 栈的基本操作一、实验目的熟练掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。理解栈在数据处理中扮演的角色，运用栈结构实现具体的应用。二、实验内容栈是数据结构中一个非常重要的结构。表达式计算是掌握程序设计语言的重要部分之一，也是栈的应用的一个典型例子。本次实验的主要内容是利用栈的基本操作，设计一个程序，实现用算符优先法对算术表达式求值的过程。对本设计系统实现+、-、*、/、%和乘方（）运算。符合要求，同时提高自己的编程能力。实现算术表达式求值。选作内容：提供对小数点的支持，允许输入的表达式中出现多位数字和小数点。三、实验要求1认真阅读和掌握本实验的算法。2上机将本算法实现。3在程序的编写中尽量与专业的编程规范靠拢，系统代码采用结构化的编程方式，力求设计代码以及注释等规范，4保存和打印出程序的运行结果，并结合程序进行分析。一 需求分析本程序用于计算“+”、“-”、“*”、“”、“”、“（）”的简单计算器，对简单的计算式子进行计算，并输出运算结果。1. 输入的形式和输入值的范围：整数类型的实数(float)，并以“#”对每个式子结尾；2. 输出的形式：算式的最后结果；3. 程序所能达到的功能：计算出所输入运算式子的结果；4. 测试数据：正确输入：（3+4）*5# 输出结果：35错误输入：没有以“#”结尾、除数为0、输入了除“+”、“-”、“*”、“”、“”、“（）”意外的运算符、括号的左右不匹配、数据 溢出等。 输出结果：“Operator error!”、“Divide zero！”、“Input error, Retry!”、“Out of space!”二 概要设计栈的储存结构：此方法中用到的抽象数据类型为结构体：struct STACK1 /此为操作符的栈；char staMAX;int top;typedef struct STACK1 stack1;struct STACK2 /此为运算数的栈；float staMAX;int top; typedef struct STACK2 stack2;主程序中提示输入所需要计算的运算公式，调用check_ch函数检查输入是否错误，然后调用operate函数计算所输入算式的计算所得结果；其中在operate函数中还调用了pop、push、Output等函数对所输入的运算公式进行计算。最后用在主函数中直接输出经过operate函数计算后的程序结果。三 详细设计定义的栈的结构体：struct STACK1 /储存运算符的栈char staMAX; /定义存入运算符为char类型数据int top;struct STACK2 /储存数字的栈float staMAX; /定义存入数字为float类型数据int top; typedef struct STACK1 stack1;typedef struct STACK2 stack2;所用主要函数：int check_ch(char chMAX) /查看表达式括号是否匹配函数int i=0;char tch; stack1 *s; s=new stack1; s-top=0; while(chi!=#)switch(chi)case(: push(chi,s); break; case): if(!IsEmpty(s)tch=pop(s); if(tch=() break; else return 0;elsereturn 0;i+; if(IsEmpty(s) return 1; else return 0;float operate(stack1 *base, stack2 *operand, char chMAX) /计算所给表达式的值char tch;int i=0;push(#,base); /在栈低先压入#while(chi!=NULL)if(check(chi) /对于运算表达式中的字符进行判断float NUM,num;NUM=0;while(check(chi)num=chi-0;NUM=NUM*10+num;i+;push(NUM,operand);elseif(!IsEmpty(base)if(chi=) /遇到(时的计算tch=pop(base);while(tch!=()Output(tch,base,operand);tch=pop(base);elsetch=base-stabase-top;while(Osp(chi)stabase-top;push(chi,base);elsepush(chi,base);i+;tch=pop(base);while(tch!=#) /把栈中剩余的运算符弹出进行计算Output(tch,base,operand);tch=pop(base);return pop(operand); /弹出栈中最后的数，即为运算式子的最后结果int Output(char ch, stack1 *base, stack2 *operand) /弹出运算符时进行两数的运算float n1,n2,num;n1=pop(operand);n2=pop(operand);num=analyse(n1,n2,ch);push(num,operand);return 0;主函数：int main()int flag;while(flag)char chMAX,c;stack1 *base;stack2 *operand;base=new stack1;operand=new stack2;float num;if(base=NULL)coutOut of space!endl; /数据溢出报错return -1;if(operand=NULL)coutOut of space!top=-1;operand-top=-1;cout Please enter the Expressions, and end with #:ch;if(!check_ch(ch)coutput error,Retry!endl; /符号不匹配则重新输入continue;num=operate(base,operand,ch);coutThe answer is num.endl;coutc;if(c=y | c=Y) /实现多次输入flag=1;elseflag=0;delete base;delete operand;return 0;函数和过程的调用关系图：四 调试分析在最一开始的时候，觉得栈是一个很神秘很抽象的东西，听老师讲课也觉得似懂非懂的，觉得理论上好像懂了，但遇到实际操作时，又开始糊涂了。直到要开始做实验，对于栈的程序代码的编写才开始有了比较清晰的轮廓。指针这方面我不太在行，所以我选择了用数组来进行栈的数据储存。我觉得数和运算符应该分开，分别为两个栈，所以我用两个结构体分别定义了一个储存字符和数字。为了能判断输入的数是否结束，我要求程序使用者在输入完算式后以“#”做结尾。考虑到有些人会不注意输入的格式，或者是括号没有匹配等，借鉴了老师的程序，我用check_ch函数来判断输入的算式是否符合要求，如果不符合要求，则重新输入。输入结束后，我就直接用了一个笼统的函数operate来对该算式来进行运算。我对输入的字符串一个一个字符的进行操作。当遇到数字时，用push函数压入数字栈内；当遇到符号时，分类讨论。当符号为“）”时，开始放出符号栈中的栈顶符号，并进行运算，知道遇到符号“）”停止。当遇到的是普通的符号时，比较符号栈的栈顶符号与该符号的优先级大小，优先级大的先进行运算。运算是指在栈中弹出最后两个数与当前运算符进行运算，将得到的结果压入数字栈中。当遇到“#”时，运算结束，弹出数字栈中最后的数，即为最终答案。在实验过程中，一开始的程序是有错误的，主要是没有考虑到符号栈中当除去括号外多余的符号，而且“i+”这一句语句放错了位置，导致程序的结果永远是我输入的最后一位数字。经过反复修改后，我的程序终于可以正常的运行了。感谢老师提供的程序，让我解决了许多程序中无法正常运行的部分，并且我知道了如何输入多位数，让程序可以进行多位数的运算。五 用户使用说明运行程序后，会出现提示：Please enter the Expressions, and end with #:（输入运算式子，并以“#”结尾，按回车；例如输入：（3+4）*5）程序运行后，屏幕上会显示出：The answer is 35.Do you want to continue?(y/n):(输入Y或y，程序将继续进行计算，否则退出程序)六 测试结果七 附录#includeusing namespace std;const MAX=50;struct STACK1 /储存运算符的栈char staMAX;int top;struct STACK2 /储存数字的栈float staMAX;int top;typedef struct STACK1 stack1;typedef struct STACK2 stack2;float operate(stack1 *base, stack2 *operand, char chMAX);int check(char ch);int Isp(char ch);int Osp(char ch);char pop(stack1 *base);float pop(stack2 *operand);float analyse(float n, float m, char ch);float power(float n, float m);int push(float num, stack2 *operand);int push(char ch, stack1 *base);int IsEmpty(stack1 *base);int Output(char ch, stack1 *base, stack2 *operand);int check_ch(char chMAX);int main()int flag;while(flag)char chMAX,c;stack1 *base;stack2 *operand;base=new stack1;operand=new stack2;float num;if(base=NULL)coutOut of space!endl; /数据溢出return -1;if(operand=NULL)coutOut of space!top=-1;operand-top=-1;coutPlease enter the Expressions, and end with #:ch;if(!check_ch(ch)coutput error,Retry!endl; /符号不匹配则重新输入continue;num=operate(base,operand,ch);coutThe answer is num.endl;coutc;if(c=y | c=Y) /实现多次输入flag=1;elseflag=0;delete base;delete operand;return 0;int check_ch(char chMAX) /查看表达式括号是否匹配函数int i=0;char tch; stack1 *s; s=new stack1; s-top=0; while(chi!=#)switch(chi)case(: push(chi,s); break; case): if(!IsEmpty(s)tch=pop(s); if(tch=() break; else return 0;elsereturn 0;i+; if(IsEmpty(s) return 1; else return 0;float operate(stack1 *base, stack2 *operand, char chMAX) /计算所给表达式的值char tch;int i=0;push(#,base); /在栈低先压入#while(chi!=NULL)if(check(chi) /对于运算表达式中的字符进行判断float NUM,num;NUM=0;while(check(chi)num=chi-0;NUM=NUM*10+num;i+;push(NUM,operand);elseif(!IsEmpty(base)if(chi=) /遇到(时的计算tch=pop(base);while(tch!=()Output(tch,base,operand);tch=pop(base);elsetch=base-stabase-top;while(Osp(chi)stabase-top;push(chi,base);elsepush(chi,base);i+;tch=pop(base);while(tch!=#) /把栈中剩余的运算符弹出进行计算Output(tch,base,operand);tch=pop(base);return pop(operand); /弹出栈中最后的数，即为运算式子的最后结果int Output(char ch, stack1 *base, stack2 *operand) /弹出运算符时进行两数的运算float n1,n2,num;n1=pop(operand);n2=pop(operand);num=analyse(n1,n2,ch);push(num,operand);return 0;int IsEmpty(stack1 *base) /判断栈是否为空if(base-top=0)return 1;elsereturn 0;int check(char ch) /判断读入的字符是否为数字if(ch9)return 0;elsereturn 1;int push(float num, stack2 *operand) /压入栈的操作operand-top+;if(operand-topMAX)coutOut of space!staoperand-top=num;return 0;int push(char ch, stack1 *base)base-top+;if(base-topMAX)coutOut of space!stabase-top=ch;return 0;char pop(stack1 *base) /弹出栈的操作char tch;tch=base-stabase-top;base-top-;return tch;float pop(stack2 *operand)float tnum;tnum=operand-staoperand-top;operand-top-;return tnum;int Isp(char ch) /运算符优先级的判断switch(ch)case #: return 0;break;case (: return 1;break;case +: return 3;br