数据结构算术表达式求解

数据结构算术表达式求解滨江学院数据结构课程设计题目算术表达式的求解院系计算机系专业学生姓名学号指导教师李燕二Ｏ一六年六月十日数据结构算术表达式求解全文共数据结构算术表达式求解全文共22页，当前为第1页。.前言1.1课题内容及要求题目39：算术表达式的求解问题描述：给定一个算术表达式，通过程序求出最后的结果。基本要求：从键盘输入要求解的算术表达式；采用栈结构进行算术表达式的求解过程；能够判断算术表达式正确与否；对于错误表达式给出提示；对于正确的表达式给出最后的结果；1.2选题目的及意义⑴进一步熟悉和使用栈的基本操作，如栈的初始化，进栈，出栈的特性。⑵学习在实际生活中使用栈来解决问题。数据结构算术表达式求解全文共22页，当前为第4页。数据结构算术表达式求解全文共22页，当前为第4页。2.系统分析2.1问题描述要正确计算表达式的值，必须要正确的解释表达式。首先解释算术表达式的运算规则，分为以下三点：⑴先乘除后加减；⑵从左往右进行计算；⑶有括号的，先算括号内的；2.2运算符的优先级分析：任何一个表达式都是由运算符，操作数和界限符组成的。这里把运算符，界限符统称为算符。设两个操作符分别为op1和op2。为实现运算符的优先法则，优先关系会出现三种情况，op1的优先级高于op2的优先级，op1的优先级等于op2的优先级，op1的优先级小于op2的优先级。2.3错误提示分析：对于输入错误的，比如出现了表达式以外的非法字符，没有按照正确格式进行输入。系统会给出提示。 数据结构算术表达式求解全文共22页，当前为第5页。数据结构算术表达式求解全文共22页，当前为第5页。3.系统概要设计3.1系统总体架构设计算术表达式的求解算术表达式的求解栈模块运算模块定义栈的结构初始化栈入栈出栈取栈顶的元素判断优先级判断是否为运算符进行基本运算函数运算函数3.2系统模块的设计为了更好的服务，结合用户的需求，有如下的模块设计：程序主要包括三个模块：⑴主函数设计模块intmain(){ 函数体}⑵栈模块：一些本程序需要的操作，如初始化栈，定义栈，出栈，入栈，取栈顶元素。⑶运算模块：对一些优先级的定义，以及基本的算术运算。数据结构算术表达式求解全文共22页，当前为第6页。数据结构算术表达式求解全文共22页，当前为第6页。4.系统详细设计4.1数据的存储设计与描述：为实现运算符的优先算法，可以用两个栈：运算符栈OPTR，操作数栈OPND。四则运算表达式算法的基本思想是：⑴首先置操作数栈OPND为空栈，表达式起始符“#”为OPTR栈的栈底元素。⑵依次读入表达式中的每个字符，是操作数则进栈OPND，是运算符就和OPTR栈的栈顶元素比较后，依据相应的优先权进行操作，直至整个表达式求值完毕（标志是两个运算符都为“#”）。4.2详细的优先级关系:Op2Op1+-*/（）#+>><<<>>->><<<>>*>>>><>>/>>>><>>（<<<<<=）>>>>>>#<<<<<=4.3具体的操作集合：栈的设计：typedefstruct{ ElemTypedata[StackSize]; inttop;}SeqStack;voidInit(SeqStack*s);//初始化栈intIsFull(SeqStack*s);//判断栈是否已满intIsEmpty(SeqStack*s);//判断栈是否是空voidPush(SeqStack*s,ElemTypex);//进行入栈操栈数据结构算术表达式求解全文共22页，当前为第7页。ElemTypePop(SeqStack*s);//进行出栈操作数据结构算术表达式求解全文共22页，当前为第7页。ElemTypegetTop(SeqStack*s);//提取栈顶元素函数运算：intAdvan(intt1,intt2);//判断符号的优先级intIn(intc);//判断c是否为运算符intOprea(inta,inttheta,intb);//进行四则运算intEvaluteExpression();//进行算术表达式求值数据结构算术表达式求解全文共22页，当前为第8页。数据结构算术表达式求解全文共22页，当前为第8页。5.程序实现//stack.h中#ifndef_STACK_H#define_STACK_H#defineStackSize100#defineMaxLength100typedefintElemType;typedefstruct{ ElemTypedata[StackSize]; inttop;}SeqStack;voidInit(SeqStack*s);//初始化栈intIsFull(SeqStack*s);//判断栈是否已满intIsEmpty(SeqStack*s);//判断栈是否是空voidPush(SeqStack*s,ElemTypex);//进行入栈操栈ElemTypePop(SeqStack*s);//进行出栈操作ElemTypegetTop(SeqStack*s);//提取栈顶元素#endif//stack.c中#include"stack.h"#include<stdio.h>#include<stdlib.h>voidInit(SeqStack*s)//初始化?{ s->top=-1;}数据结构算术表达式求解全文共22页，当前为第9页。intIsFull(SeqStack*s)//判断栈是否已满数据结构算术表达式求解全文共22页，当前为第9页。{ returns->top==StackSize-1;}intIsEmpty(SeqStack*s)//判断栈是否是空{ returns->top==-1;}voidPush(SeqStack*s,ElemTypex)//进行入栈操栈{ if(IsFull(s)){ printf("栈已经溢出。"); exit(1); } s->top++;//栈顶指针加1 s->data[s->top]=x;//栈顶为新插入的值，data是数组，s->top数字}ElemTypePop(SeqStack*s)//进行出栈操作{ if(IsEmpty(s)){ printf("栈是空的"); exit(1); } returns->data[s->top--]; //先删除栈顶的元素，然后指针减一}ElemTypegetTop(SeqStack*s)//提取栈顶元素{ if(IsEmpty(s)){ printf("栈是空的"); exit(1); }数据结构算术表达式求解全文共22页，当前为第10页。 returns->data[s->top];数据结构算术表达式求解全文共22页，当前为第10页。 }//operstack.h中#ifndef_OPERSTACK_H#define_OPERSTACK-HintAdvan(intt1,intt2);//判断符号的优先级intIn(intc);//判断c是否为运算符intOprea(inta,inttheta,intb);//进行四则运算intEvaluteExpression();//进行算术表达式求值#endif//operstack.c中#include"stack.h"#include<stdio.h>#include<stdlib.h>#include"operstack.h"intAdvan(intt1,intt2)//判断符号的优先级{ intf; switch(t2) { case'+'://若t2符号是“+”“-” case'-': if(t1=='('||t1=='#') f='<'; else f='>'; break; 数据结构算术表达式求解全文共22页，当前为第11页。 case'*'://若t2符号是*，/时数据结构算术表达式求解全文共22页，当前为第11页。 case'/': if(t1=='*'||t1=='/'||t1==')') f='>'; else f='<'; break; case'('://若t2符号是（，此时应该优先级小继续输入，而不进行运算 if(t1==')'){ printf("ERROR括号不匹配\n"); exit(0); } else f='<'; break; case')'://若t2符号是），此时一个括号已经完整，应该进行运算 switch(t1) { case'(':f='='; break; case'#':printf("ERROR缺少左括号\n"); exit(0); default:f='>'; } break; case'#'://若t2取出时是#，表示已经要计算最后一个表达式了 switch(t1) { case'#':f='='; break; case'(':printf("ERROR缺少右括号\n"); exit(0); default:f='>'; }数据结构算术表达式求解全文共22页，当前为第12页。 } 数据结构算术表达式求解全文共22页，当前为第12页。 returnf; }intIn(intc)//判断c是否为运算符{ switch(c) { case'+': case'-': case'*': case'/': case'(': case')': case'#':return1; default:return0; }}intOprea(inta,inttheta,intb)//进行四则运算{ intc; switch(theta) { case'+': c=a+b; break; case'-': c=a-b; break; case'*': c=a*b; break;数据结构算术表达式求解全文共22页，当前为第13页。 case'/':数据结构算术表达式求解全文共22页，当前为第13页。 c=a/b; break; } returnc;}intEvaluteExpression()//进行算术表达式求值{ SeqStackOPTR,OPND;//构建两个栈，一个是放操作符，一个是放数据 inta,b,d,x,theta; charc;//存放键盘接收的字符 charz[6];//存放整数串 inti; Init(&OPTR);//初始化运算符栈 Push(&OPTR,'#');//#入栈，#是表达式结束的标志 Init(&OPND);//初始化数据栈 c=getchar();//从键盘读入下一个字符到c x=getTop(&OPTR);//x赋值为运算符栈顶元素 while(c!='#'||x!='#'){//当读入两个字符都为#时，则停止，返回最后的 // 结果X的值，否则继续进行运算 if(In(c)){//是运算符 switch(Advan(x,c)) { case'<':Push(&OPTR,c);//优先级低，继续进行输入 c=getchar(); break; case'=':x=Pop(&OPTR);//脱括号并计算下一个值 c=getchar(); break; case'>':theta=Pop(&OPTR);//优先级高，此时进行运算,从操 //作栈中取出一个运算符 b=Pop(&OPND);//从数据栈中取出两个数 a=Pop(&OPND);数据结构算术表达式求解全文共22页，当前为第14页。 Push(&OPND,Oprea(a,theta,b));//然后通过这两个数进行运算 }数据结构算术表达式求解全文共22页，当前为第14页。 }elseif(c>='0'&&c<='9'){//是数字 i=0; do{ z[i]=c; i++; c=getchar(); }while(c>='0'&&c<='9'); z[i]=0;//整数串结束 d=atoi(z);//将字符串转化为整数放入d中 Push(&OPND,d); //一个整数入到数据栈中 }else{//两者以外显然不可能，出错 printf("ERROR出现了非法的字符，表达式不符合格式\n"); exit(0); } x=getTop(&OPTR); } x=getTop(&OPND); returnx;}数据结构算术表达式求解全文共22页，当前为第15页。数据结构算术表达式求解全文共22页，当前为第15页。6.程序测试6.1正确的结果6.2错误16.3错误2数据结构算术表达式求解全文共22页，当前为第16页。6.4错误3数据结构算术表达式求解全文共22页，当前为第16页。数据结构算术表达式求解全文共22页，当前为第17页。数据结构算术表达式求解全文共22页，当前为第17页。7.收获及体会：该程序经过调试已经能够运行，并且能够正确的输出答案以及错误的提示。通过本次数据结构课程设计，能够更加深刻的体会栈的特点，更熟悉栈的相关操作，以及如何运用栈的相关知识解决生活中的实际问题。参考文献：[1]李文书．数据结构与算法应用实践教程．北京大学出版社．2012.02[2]戴文华赵君喆．数据结构项目实训．人民邮电出版社．2012.09[3]李业丽程晓锦齐亚莉．数据结构实验教程（基于c语言）．清华大学出版社．2014.04目录TOC\o"1-2"\h\z\u第一章总论 11.1项目名称与承办单位 11.2研究工作的依据、内容及范围 1数据结构算术表达式求解全文共22页，当前为第18页。1.3编制原则 3数据结构算术表达式求解全文共22页，当前为第18页。1.4项目概况 31.5技术经济指标 51.6结论 6第二章项目背景及建设必要性 82.1项目背景 82.2建设的必要性 9第三章建设条件 113.1项目区概况 113.2建设地点选择 错误！未定义书签。3.3项目建设条件优劣势分析 错误！未定义书签。第四章市场分析与销售方案 134.1市场分析 134.2营销策略、方案、模式 14第五章建设方案 155.1建设规模和产品方案 155.2建设规划和布局 155.3运输 185.4建设标准 185.5公用工程 205.6工艺技术方案 215.7设备方案 21数据结构算术表达式求解全文共22页，当前为第19页。5.8节能减排措施 24数据结构算术表达式求解全文共22页，当前为第19页。第六章环境影响评价 256.1环境影响 256.2环境保护与治理措施 266.3评价与审批 28第七章项目组织与管理 297.1组织机构与职能划分 297.2劳动定员 297.3经营管理措施 307.4技术培训 30第八章劳动、安全、卫生与消防 318.1编制依据及采用的标准 318.2安全卫生防护原则 318.3自然灾害危害因素分析及防范措施 328.4生产过程中产生的危害因素分析及防范措施 328.5消防编制依据及采用的标准 348.6消防设计原则 358.7火灾隐患分析 358.8总平面消防设计 358.9消防给水设计 368.10建筑防火 368.11火灾检测报警系统 37数据结构算术表达式求解全文共22页，当前为第20页。8.12预期效果 37数据结构算术表达式求解全文共22页，当前为第20页。第九章项目实施进度 389.1实施进度计划 389.2项目实施建议 38第十章项目招投标方案 4010.1招标原则 4010.2项目招标范围 4010.3投标、开标、评标和中标程序 4010.4评标委员会的人员组成和资格要求