《数据结构表达式求值课程设计报告》由会员分享，可在线阅读，更多相关《数据结构表达式求值课程设计报告（26页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告（2011 - 2012年度第1学期）表达式求值专 业计算机科学与技术学生姓名班 级学 号指导教师完成日期目录目 录21 概 述 11.1 课程设计目的 11.2 课程设计内容 12 系统需求分析12.1 系统目标 12.2 主体功能 12.3 开发环境 13 系统概要设计23.1 系统的功能模块划分 23.2 系统流程图 24系统详细设计35 测试65.1 测试方案 65.2 测试结果 66 小结8参考文献1.0附录1 源程序清单 11表达式求值1 概 述1.1 课程设计目的1. 要求学生达到熟练掌握C语言的基本知识和技能。2了解并掌握数据结构与算法的设计方法，具备初步的
2、独立分析和设计能力。 3提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正 确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。4培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步 提高程序设计水平。5初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方 法和技能。1.2 课程设计内容设计一个表达式求值的程序。该程序必须可以接受包含（，），+，-，*，/，%， 和八（求幂运算符，a=ab）的中缀表达式，并求出结果。如果表达式正确，则输出 表达式的结果；如果表达式非法，则输出错误信息。2 系统需求分析2.1 系统目标利用栈设计一个程序，该程序
3、能够用于表达式求值，程序将读入的中缀表达式 转换为后缀表达式，然后读取后缀表达式，输出结果。输入要求：程序从“ input.txt”文件中读取信息，在这个文件中如果有多个 中缀表达式，则每个表达式独占一行，程序的读取操作在文件的结尾处停止。输出要求：对于每一个表达式，将其结果放在“output.txt”文件的每一行中。 这些结果可能是值（精确到小数点后两位），也可能是错误信息“ ERROR IN INFIX NOTATION”。2.2 主体功能能够处理以字符序列的形式输入的不含变量的实数表达式，正确处理负数与小数，判断表 达式是否语法正确（包含分母不能为零的情况），正确实现对算术四则混合运算表
4、达式的求值， 能够将计算中遇到的问题和结果以文件的形式予以存储。2.3 开发环境Microsoft Visual C+ 6.03系统概要设计3.1 系统的功能模块划分1. 判断操作数的函数isnum() 判断当前所指字符是否属于数字，是就返回1，不是就返回0。2. 求运算符优先级函数priority()为了方便判断运算符优先级，先利用switch函数将不同的运算符返回不同的整 型数字，在根据数字的大小判断优先级。+，-优先级相同，返回数字相同 ， *，/也是。3. 表达式求值函数infix_value() 此函数是直接按照设计思路完成问题要求的函数，其中要调用到判断操作符的函数isnum()和
5、求运算符优先级的函数priority()。循环结束弹出栈2的数值，并 返回。4. 主函数main() 定义一个数组存储表达式整个字符串，将返回的数值直接赋值到浮点型的result，输出 result。5. 两个栈的函数设计：栈的初始化函数charInit_SeqStack()Init_SeqStack()栈判空Empty_SeqStack() char Empty_SeqStack()入栈函数Push_SeqStack() charPush_SeqStack()出栈函数Pop_SeqStack() charPop_SeqStack()取栈顶函数GetTop_SeqStack() charGet
6、Top_SeqStack()销毁栈Destory_SeqStack() charDestory_SeqStack()3.2 系统流程图图 1 系统流程图4 系统详细设计1. 基本分析:在计算机中，算术表达式的计算往往是通过使用栈来实现的。所以，本表达式 求值程序的最主要的数据结构就是栈。可以使用栈来存储输入表达式的操作符和操 作数。输入的表达式是由操作数和运算符以及改变运算次序的圆括号连接而成的式 子。表达式求值是高级语言编译中的一个基本问题，是栈的典型应用实例。任何一 个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成 的。操作数既可以是常数
7、，也可以是被说明为变量或常量的标识符；运算符可以分 为算术运算符、关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结 束符等。2. 中缀表达式求值:中缀表达式：每个二目运算符在两个运算量的中间，假设操作数是整型常数， 运算符只含加、减、乘、除等四种运算符，界限符有左右括号和表达式起始、结束 符“#”，如：#(7+15 )* (23-28/4)#。要对一个简单的算术表达式求值，首先要 了解算术四则运算的规则，即：(1) 从左到右；(2) 先乘除，后加减；(3) 先括号内，后括号外。运算符和界限符可统称为算符，它们构成的集合命名为OPS。根据上述三条运 算规则，在运算过程中，任意两个前后相
8、继出现的算符G1和。2之间的优先关系 必为下面三种关系之一：0 102，01的优先权高于0 2。实现算符优先算法时需要使用两个工作栈：一个称作opera tor，用以存放运算 符；另一个称作operand，用以存放操作数或运算的中间结果。算法的基本过程如 下：首先初始化操作数栈operand和运算符栈opera tor,并将表达式起始符“#” 压入运算符栈；依次读入表达式中的每个字符，若是操作数则直接进入操作数栈operand，若 是运算符，则与运算符栈opera tor的栈顶运算符进行优先权比较，并做如下处理:(1) 若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进 opera
9、tor 栈；(2) 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入 0，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、b进行0运 算后，将运算结果作为中间结果推入operand栈；(3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相 遇，只需将栈顶运算符(左括号)退栈即可。opera tor栈的栈顶元素和当前读入的 字符均为“ #”时，说明表达式起始符“#”与表达式结束符“ #”相遇，整个表达 式求解结束。int ExpEvaluation()/*读入一个简单算术表达式并计算其值。*/InitStack(&operand);InitSt
10、ack(&operator);PushS tack(&o pera tor,printf(“ nn Please input an expression (Ending with #):“)； ch=ge tchar();/*读入表达式中的一个字符*/whil e(ch!二 #|Ge tTop(opera tor)!二#) if(!In(ch, OPS)/*判断 ch 是否运算符*/ a=GetNumber(&ch);/*用ch逐个读入操作数的各位数码，并转化为十进制数a */PushS tack(&operand,a);elseswit ch(Compare(Ge tTop(opera to
11、 r),ch) case z z : PushStack(&operator, ch);ch=getchar();break;case z =z: PopS tack(&opera tor,& x);ch=ge tchar();break;case y: PopStack(&operator, &op); PopStack(&operand,& b);PopS tack(&operand, & a);v二Exec ut e(a,op,b);PushS tack(&o perand,v);break;v=GetTop(operand);retu rn(v);为了处理方便，编译程序常把中缀表达式首
12、先转换成等价的后缀表达式，后缀 表达式的运算符在运算对象之后。在后缀表达式中，不再引入括号，所有的计算按 运算符出现的顺序，严格从左向右进行，而不用再考虑运算规则和级别。中缀表达 式 “(a+b*c)-d/e 的后缀表达式为：“abc*+de/-。3. 后缀表达式求值：计算一个后缀表达式，算法上比计算一个中缀表达式简单的多。这是因为表达 式中即无括号又无优先级的约束。具体做法：只使用一个对象栈，当从左向右扫描 表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两 个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈 顶的值就是结果。下面是后缀表达式求值的
13、算法，在下面的算法中假设，每个表达式是合乎语法 的，并且假设后缀表达式已被存入一个足够大的字符数组A中，且以#为结束 字符，为了简化问题，限定运算数的位数仅为一位且忽略了数字字符串与相对应的 数据之间的转换问题。double calcul_exp(char *A) /*本函数返回由后缀表达式A表示的表达式运算结 果*/ SeqStarck s;ch二*A+ ; InitStack(s);while(ch!= #) if(ch!=运算符)PushS tack(s, ch);elsePopS tack(s, & a);PopS tack(s, &b);/*取出两个运算量*/swit ch(ch)
14、casech二二+ : c=a+b;break ;casech二二: c=a-b;break ;casech二二*: c=a*b;break ;casech二二/: c=a/b;breakcasech二二%:c=a%b;break ;PushS tack (s, c) ch=*A+ ;PopS tack(s, resu lt);return result ;4. 中缀表达式转换成后缀表达式：将中缀表达式转化为后缀表达式和前述对中缀表达式求值的方法完全类似，但 只需要运算符栈，遇到运算对象时直接放后缀表达式的存储区，假设中缀表达式本 身合法且在字符数组A中，转换后的后缀表达式存储在字符数组B中。具体做法： 遇到运算对象顺序向存储后缀表达式的B数组中存放，遇到运算符时类似于中缀表 达式求值时对运算符的处理过程，但运算符出栈后不是进行相应的运算，而是将其 送入B中存放。读者不难写出算法，在此不在赘述。程序的整体算法分两步：第一步，从”input.txt”文件中读取中缀表达式，并应用运算符栈OpHolder把中 缀表达式转换为后缀表达式，将输出结果存放在一个temp文件中。第二步，从temp文件中读取中缀表达式，并应用操作栈Operands计算后缀表 达式结果，将结果输出到”output.txt”文件中。5测试5.1测试方案设计针对程序的input.txt文件，并将运行结果与期
