数据结构(表达式求值)课程设计

课程设计报告课程名称：数据结构课程设计课程设计题目：表达式求值问题姓名：系：计算机科学与技术专业：计算机科学与技术年级：2011级学号：指导教师：职称：讲师2011年12

目录TOC\o"1-2"\u1.设计目的: 12.设计要求: 13.设计方案: 14.设计内容: 24.1．需求分析 24.2．概要设计 24.3.详细设计 44.4.调试分析与结果 74.5：使用说明 115.总结： 126.附录三：源代码 12第25页表达式求值问题1.设计目的:《数据结构课程设计》是计算机专业集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。其目的是：（1）要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。（2）在实践中认识为什么要学习数据结构，掌握数据结构、程序设计语言、程序设计技术之间的关系，是前面所学知识的综合和回顾。2.设计要求:以字符序列的形式从键盘输入语法正确的、不含变量的整数（或实数）表达式，实现对算术四则混合运算表达式的求值。当用户输入一个合法的算术表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号，对于异常表达式能给出错误提示。3.设计方案:任何一个表达式都是由操作符，运算符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素。为了实现算符优先算法。可以使用两个栈。一个称为OPF，用以寄存运算符，另一个称做OPS，用以寄存操作数或运算结果。1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；2.依次读入表达式，若是操作符即进OPS栈，若是运算符则和OPF栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPF栈的栈顶元素和当前读入的字符均为”#”）。4.设计内容:4.1．需求分析本程序所做的工作为：能直接求出四则表达式的值，并输出；本程序可用于小学教师对学生作业的快速批改以及对数值位数要求较大的科学运算。4.2．概要设计1.//用于存储操作数和运算结果（OPS）:ADTLinkStack{数据元素：此链栈中的所有元素类型为字符型的数字字符数据关系：栈中数据元素之间是线性关系。基本操作:（1）InitStack(LinkStack&head)操作结果：构造一个空栈head（2）IsEmpty(LinkStackhead)初始条件：栈head已存在操作结果：若栈为空栈，则返回TRUE,否则FALSE（3）Push(LinkStack&head,ElementTypeelement)初始条件：栈head已存在操作结果：插入元素element为新的栈顶元素（4）Pop(LinkStack&head,ElementType&element)初始条件：栈head已存在且非空操作结果：删除head的栈顶元素，并用e返回其值（5）GetTop(LinkStackhead,ElementType&element)初始条件：栈head已存在并且非空操作结果：用e返回head的栈顶元素（6）DestroyStack(LinkStack&head)初始条件：栈head已存在操作结果：栈head被销毁}ADTLinkStack2．//用于存储运算符(OPF)：ADTLinkCharStack{数据对象D：元素类型为字符型的符号字符数据关系R：基本操作：栈中数据元素之间是线性关系。（1）CInitStack(LinkCharStack&head)操作结果：构造一个空栈head（2）CIsEmpty(LinkCharStackhead)初始条件：栈head已存在操作结果：若栈为空栈，则返回TRUE,否则FALSE（3）CPush(LinkCharStack&head,ElementTypeelement)初始条件：栈head已存在操作结果：插入元素element为新的栈顶元素（4）CPop(LinkCharStack&head,ElementType&element)初始条件：栈head已存在且非空操作结果：删除head的栈顶元素，并用e返回其值（5）CGetTop(LinkCharStackhead,ElementType&element)初始条件：栈head已存在并且非空操作结果：用e返回head的栈顶元素（6）CDestroyStack(LinkCharStack&head)初始条件：栈head已存在操作结果：栈head被销毁}ADTLinkCharStack3.系统中子程序及功能要求：Comop(charch)：判断输入的字符是否为运算符charPrecede(charch,charc)：比较两个运算符的优先级，ch是栈顶字符，c是表达式字符。ElementTypeOperate(ElementTypea,charch,ElementTypeb)：解析表达式中的双目运算，其返回的结果即为双目运算表达式的值。interror(char*str)：错误提示函数，实现对多种非法四则表达式的判断，并给出提示，让用户更正自己的输入错误。voidMenuPrint()：主菜单打印函数。voidClear()：清屏函数。ElementTypeEvaluateExpression(char*exp)：这是此程序的核心函数，可以综合其它子函数，实现最终的表达式求解。各程序模块之间的调用关系（子程序编号见上）：主函数可调用子程序5，6，7。子程序7可调用子程序1，2，3，4。4.3.详细设计此算法的基本思想：首先置操作数栈OPS为空栈，表达式起始符“#”为运算符的栈底元素；依次读入表达式中每个字符，若是操作数则进栈，若是运算符则和OPF栈的栈顶运算符比较优先权作相应操作，直至整个表达式求值完毕（即OPF栈的栈顶元素和当前读入的字符均为“#”）此算法的伪代码： ElementTypeEvaluateExpression(char*exp){定义两个字符变量c和ch,c代表输入表达式中的字符，ch代表栈顶运算符;定义字符指针*p,*q,*temp;temp指向运算符后面的一个字符 doublei=0,a=0,b=0; 将传入的实参赋给p,q; 定义一个运算符栈OPF; 定义一个操作数栈OPS; 调用函数InitStack()初始化栈OPS;调用函数CInitCharStack()初始化栈OPF;调用函数CPush(OPF,'#')将#压入运算符栈; c=*p;temp=p;p++; if(第一个字符就为‘-’) { c=*p;temp=p;p++; } while(栈不为空或表达式没有结束) {//进入最外层循环 if(不是运算符)//则解析数字字符串然后进操作数栈 { 整数部分m=0;小数部分n=0; while(没有遇到小数点并且为数字字符) {解析整数部分m} if(遇到小数点) {解析小数部分 c=*p; 将p指针移到第一个出现的字符; 将q指针指向小数的最后一位; while(p指针不指向’.’) { 将p指向的字符转为小数n p--; } p=q; p++; } if(运算符为‘-’并且运算符前一个为‘（’或者为表达式的开始) 调用Push(OPS,-(m+n))将m+n的相反数入栈; else 调用Push(OPS,m+n)将m+n入栈;}数字进栈结束 else//是运算符时则进栈OPF {if(运算符为‘-’&&运算符前一个为‘（’) {c=*p; temp=p; p++; } else {调用函数CGetTop(OPF,ch)得到OPF的栈顶元素;switch(调用函数Precede(ch,c)判断栈顶元素与接收的字符的优生级别) { case栈顶运算符优先权低: 调用函数CPush(OPF,c)将c入运算符栈; 接收下一个字符; case栈顶运算符优先权高： 运算符出栈得到ch; 数字栈连续出栈两次得到a,b; 调用Operate(a,ch,b)并将结果入栈到数字栈;break; case优生权相等：脱括号并接收下一个字符; 调用CPop(OPF,ch)脱括号;接收下一个字符; default:接收下一个字符; }退出switch循环 }//else1 }//else2 }//退出最外层while循环 调用函数GetTop(OPS,i)得到栈顶元素i; 将两个栈消毁;}EvaluateExpression函数结束利用该算法对算术表达式3*(7-2)求值操作过程如下：步骤OPF栈OPS栈输入表达式主要操作1#3*(7-2)#Push(OPS,’3’2#3*(7-2)#CPush(OPF,’*’)3#*3(7-2)#CPush(OPF,’(’)4#*(37-2)#Push(OPS,’7’5#*(37-2)#CPush(OPF,’-’)6#*(-372)#Push(OPS,’2’7#*(-372)#Operate(‘7’,’-’,’28#*(35)#CPop(OPF)9#*35#Operate(‘3’,’*’,510#15#Return(GetTop(OPS))表一4.4.调试分析与结果附录一：测试数据组别表达式正确值112+（9-8）*7-（-6*5）4923.14*（67.305-65.305）+3.149.4233+{2*[2*(3+4)]}3144.3-{2.5*[9.9/(1.1+2.2)]}-3.2512-（3-6*7）8-4错误表达式表二按照附录中的测试数据，得出如下测试、分析结果：当我们输入表格中两个正确的四则表达式时程序能准确地求得其值：完全支持浮点数，正负数的运算;而当我们输入第五组错误的表达式时，程序能做出正确判断，提醒用户输入的表达式错误。其数据测试的情况见截图：表达式一运算结果表达式二运行结果表达式三运行结果表达式四运行结果由表二可知以上四组表达式运行结果皆正确。表达式五运行结果由表二可知第五组表达式错误。

附录二：部分错误表达式组别第一个字符前一个运算符符当前运算符后一个字符1+\-\*\/\.)\]\}2(\[\{+\-\*\/\.3)\]\}.4.(\[\{5()6)(7[]8][9{}10}{11)\]\}0~9120~9(\[\{13+\*\/\)\}\]14+\-\*\/\.+\-\*\/\.15/0表三4.5：使用说明运行程序，首先出现主菜单。主菜单包括三个选项：选项a：表达式求解，选择该项可进行四则表达式的求解；选项b：清屏；选项c：退出程序，选择该项将退出程序。5.总结：这次课程设计让我更加了解了学到的C语言和数据结构。课程设计不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力同时这也使我更加了解编程思想和编程技巧。这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。就像我在写EvaluateExpression()函数时，忘了指针的地址符值不用加*，这一点小小的错误也耽误了我几十分钟，所以说细节很重要。程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意。6.附录三：源代码//这个栈是用来存储数字字符的#include<stdlib.h>#include<stdio.h>#include<string.h>#defineERROR0#defineOK1#define TRUE1#defineFALSE0typedefcharElemType;typedefintStatus;typedefdoubleElementType;typedefintStatus;#defineSTACK_INIT_SIZE30#defineSTACKINCREAMENT10#defineNUMBER30typedefstructnode{ElementTypedata;structnode*next;}StackNode,*LinkStack;voidInitStack(LinkStack&head){head=(LinkStack)malloc(sizeof(StackNode)); head->next=NULL;}StatusIsEmpty(LinkStackhead){ if(head->next==NULL)returnTRUE; elsereturnERROR;}StatusPush(LinkStack&head,ElementTypeelement){//入栈 LinkStackp; p=(LinkStack)malloc(sizeof(StackNode)); if(p==NULL)returnFALSE; p->data=element; p->next=head->next; head->next=p; returnOK;}StatusPop(LinkStack&head,ElementType&element){//出栈 if(IsEmpty(head))returnFALSE; LinkStacktemp=head->next;element=temp->data; head->next=temp->next; free(temp); returnOK;}StatusGetTop(LinkStackhead,ElementType&element){ if(head->next==NULL) returnERROR;element=head->next->data; returnOK;}StatusDestroyStack(LinkStack&head){ LinkStackq; while(head) { q=head->next; free(head); head=q; } returnTRUE;}//这个栈是用来存储符号字符的typedefstructnode1{ ElemTypedata; structnode1*next;}StackCharNode,*LinkCharStack;voidCInitCharStack(LinkCharStack&head){ head=(LinkCharStack)malloc(sizeof(StackCharNode)); head->next=NULL;}StatusCIsEmpty(LinkCharStackhead){ return(head->next==NULL)?TRUE:FALSE;}StatusCPush(LinkCharStack&head,ElemTypeelement){ LinkCharStacktemp=(LinkCharStack)malloc(sizeof(StackCharNode)); if(!temp)returnERROR; temp->data=element; temp->next=head->next; head->next=temp; returnTRUE;}StatusCPop(LinkCharStack&head,ElemType&element){ if(CIsEmpty(head))returnFALSE; StackCharNode*temp=head->next; element=temp->data; head->next=temp->next; free(temp); returnTRUE;}StatusCGetTop(LinkCharStackhead,ElemType&element){ if(head->next!=NULL) { element=head->next->data; returnTRUE; } element='#'; returnFALSE;}StatusCDestroyStack(LinkCharStack&head){ LinkCharStackq; while(head) { q=head->next; free(head); head=q; } returnTRUE;}//判断ch是否为运算符intComop(charch){ switch(ch) { case'+': case'-': case'*': case'/': case'(': case')': case'[': case']': case'{': case'}': case'#':return1; default:return0; }}//Comop

//比较两个运算符的优先级charPrecede(charch,charc)//ch是栈顶字符,c是表达式字符{ switch(ch) { case'+': case'-': if(c=='+'||c=='-'||c==')'||c=='#'||c==')'||c==']'||c=='}')return'>'; if(c=='*'||c=='/'||c=='('||c=='['||c=='{')return'<'; case'*': case'/': if(c=='+'||c=='-'||c=='*'||c=='/'||c==')'||c==']'||c=='}'||c=='#')return'>'; if(c=='('||c=='['||c=='{')return'<'; case'(': if(c=='+'||c=='-'||c=='*'||c=='/')return'<'; if(c==')')return'='; case')': if(c=='+'||c=='-'||c=='*'||c=='/'||c==']')return'>'; if(c=='#')return'>'; case'[': if(c=='+'||c=='-'||c=='*'||c=='/'||c=='(')return'<'; if(c==']')return'='; case']': if(c=='+'||c=='-'||c=='*'||c=='/'||c=='}')return'>'; if(c=='#')return'>';case'{': if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c=='[')return'<'; if(c=='}')return'=';case'}': if(c=='+'||c=='-'||c=='*'||c=='/')return'>'; if(c=='#')return'>'; case'#': if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c=='['||c=='{')return'<'; if(c=='#')return'='; default: return'$'; }}//precede//运算函数ElementTypeOperate(ElementTypea,charch,ElementTypeb){ switch(ch) { case'+':returna+b; case'-':returna-b; case'*':returna*b; case'/': if(b==0) { return-32767; } returna/b; default: return-32767; }}//Operate

//错误提示函数interror(char*str){inti=0;while(str[i]!='#')//主要通过判断所有输入的字符数组str[30]{if(((str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'||str[i]=='.')&&//其它函数只要一声明err=1也就说明输入有误(str[i+1]==')'||str[i+1]==']'||str[i+1]=='}'))||((str[i]=='+'||str[i]=='*'||str[i]=='/'||str[i]=='.')&&(str[i-1]=='('||str[i-1]=='['||str[i-1]=='{'))||( (str[i]==')'||str[i]==']'||str[i]=='}')&&str[i+1]=='.' )||( str[i]=='.'&&(str[i+1]=='('||str[i+1]=='['||str[i+1]=='{') )||(str[i]==')'&&str[i+1]=='(')||(str[i]=='('&&str[i+1]==')') ||(str[i]=='['&&str[i+1]==']')||(str[i]==']'&&str[i+1]=='[')||(str[i]=='{'&&str[i+1]=='}')||(str[i]=='}'&&str[i+1]=='{') ||( (str[i]==')'||str[i]==']'||str[i]=='}')&&str[i+1]>='0'&&str[i+1]<='9' ) ||( (str[i]>='0'&&str[i]<='9'&&(str[i+1]=='('||str[i+1]=='['||str[i+1]=='{') )||(str[0]=='+'||str[0]=='*'||str[0]=='/'||str[0]==')'||str[0]==']'||str[0]=='}')||((str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'||str[i]=='.')&&(str[i+1]=='+'||str[i+1]=='-'||str[i+1]=='*'||str[i+1]=='/'||str[i+1]=='.') )||(int(str[i])>57&&(int(str[i])!=91&&int(str[i])!=93&&int(str[i])!=123&&int(str[i])!=125))||(str[i]=='/'&&str[i+1]=='0')||(int(str[i])>31&&int(str[i])<38)))return1;elseif(str[i]=='#')return0;i++;}//whilereturn0;}//错误提示函数//表达式计算函数ElementTypeEvaluateExpression(char*exp){ charc,ch;//c代表输入表达式中的字符，ch代表栈顶运算符 char*p,*q,*temp;//temp指向运算符后面的一个字符 doublei=0,a=0,b=0; p=q=exp; LinkCharStackOPF;//运算符栈 LinkStackOPS;//操作数栈 CInitCharStack(OPF);CPush(OPF,'#'); InitStack(OPS); c=*p;temp=p;p++; if(c=='-') { c=*p;temp=p;p++; } while(c!='#'||!CIsEmpty(OPF))//栈不为空或表达式没有结束 {//*********************进入最外层循环********************* if(!Comop(c))//不是运算符则解析数字字符串然后进操作数栈 { doublem=0,n=0; while(c!='.'&&c>='0'&&c<='9') {//解析整数部分 m=m*10+(c-48); c=*p; p++; } if(c=='.') {//解析小数部分 c=*p; while(c>='0'&&c<='9') {p++;c=*p;} q=p; p--; while(*p!='.') { n=n/10+(*p-48)/10.0; p--; } p=q; p++; } if(*(temp-2)=='('&&*(temp-1)=='-'||temp-1==exp) Push(OPS,-(m+n)); else Push(OPS,m+n); }//*****数字进栈结束****** else//是运算符时则进栈OPF { if(c=='-'&&*(p-2)=='(') { c=*p; temp=p; p++; } else//else1 { CGetTop(OPF,ch); switch(Precede(ch,c)) { case'<'://栈顶运算符优先权低 CPush(OPF,c);c=*p;temp=p;p++;break; case'>'://栈顶运算符优先权高 CPop(OPF,ch); Pop(OPS,b);Pop(OPS,a); Push(OPS,Operate