资源描述：
《数据结构课程设计报告书》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构课程设计南通大学计算机学院《数据结构课程设计报告书》题目：2.3表达式求值问题专业：计算机科学与技术开始日期：2013.01.14完成日期：2012.01.161.问题的描述和分析1.1问题描述表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*（7-4）/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：2274-*3/11+）和前缀式（如：+11/*22–743）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计
2、算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。19/19数据结构课程设计1.2问题分析选择了栈，在某些运算部分采用了数组。重点是栈的使用问题，栈是限制只能在表的一端进行插入和删除的线性表，栈顶能进行插入和删除而栈底不允许插入和删除。难点是使用栈存表达式和让表达式逆序输出这些问题。2.概要设计2.1系统模块划分表达式求值系统创建表达式前缀表达式求值显示表达式并退出系统求前缀表达式后缀表达式求值表达式求值求后缀表达式图2-1系统模块图2.2ADT（抽象数据类型）描述要求：描述系统所采用数据结构的抽象数据类型，只
3、要说清楚数据对象、数据关系，基本操作集合，切勿复制大量代码，可以参考教材如何定义ADT的。例如：ADTStack{数据对象:D={ai
4、ai∈ElementSet,i=1,2,…,n,n≥0}数据关系:R={
5、ai-1,ai∈D,i=2,…,n基本操作：（1）charPrecede(chart1,chart2)进行运算符优先级的比较（2）intIn(charc)判断输入的c是否是运算符19/19数据结构课程设计（1）doubleOperate(doublea,chartheta,doubleb)进行一次运算（
6、2）doubleVal_Exp(char*exp)进行中缀表达式的求值（5）voidCreatePostExp(char*exp,char*&postexp)中缀表达式求后缀表达式（6）doubleVal_PostExp(char*postexp)后缀表达式求值（7）voidCreatePreFax(char*exp,char*&prefax)中缀表达式求前缀表达式（8）doubleVa2_PreFax(char*prefax)前缀表达式求值}3.详细设计3.1ADT基本操作算法设计3.1.1ADT操作（1）charPrece
7、de(chart1,chart2)进行运算符优先级的比较括号优先级高，其实乘除，最后加减（3）intIn(charc)判断输入的c是否是运算符（4）doubleOperate(doublea,chartheta,doubleb)进行一次运算19/19数据结构课程设计进行加减乘除运算（1）doubleVal_Exp(char*exp)进行中缀表达式的求值Step1：设定两栈，操作符栈和操作数栈；Step2：栈初始化：设操作数栈为空；Step3：依次读入字符：若是操作数则入栈；如果是操作符：若优先级小于栈顶元素，则退栈、计算，结果
8、压入操作数栈；若优先级等于栈顶元素，则脱括号；若优先级大于栈顶元素，则压入操作符栈；（5）voidCreatePostExp(char*exp,char*&postexp)中缀表达式求后缀表达式Step1：设立暂存运算符的栈；Step2：设表达式的结束符为“=”；Step3：若当前字符是操作数，则直接给输出串；Step4：若当前运算符的优先级高于栈顶运算符，则压栈；Step5：否则，栈顶运算符出栈；Step6：“（”对它之前后的运算符起隔离作用，“）”可视为自相应左右括弧的表达式的结束符。（6）doubleVal_PostEx
9、p(char*postexp)后缀表达式求值Step1:读入表达式的一个字符；19/19数据结构课程设计Step2：若是操作数，压入栈，转4；Step3：若是运算符，从栈中弹出两个数，将运算结果压入栈Step4：若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转1；（7）voidCreatePreFax(char*exp,char*&prefax)中缀表达式求前缀表达式Step1：求输入串的逆序；Step2：检查输入的下一个元素；Step3：假如是操作数，把他添加到输出串；Step4：假如是闭括号，将它压栈；Step5：假
10、如是运算符，则：（1）如果栈空，此运算符入栈；（2）如果栈顶是闭括号，此运算符入栈；（3）如果它的优先级高于或等于栈顶运算符，此运算符入栈；（4）否则，栈顶运算符出栈并添加到到输出串，重复步骤5；Step6：假如是开括号，栈中运算符逐个出栈并输出，知道遇到闭括号，闭括号出栈并
