数据结构课程设计说明书(表达式求值).docx

**大学 数据结构 课 程 设 计 说 明 书 ? ? ? 学生姓名: ?*** 学 号： ?********** 学 院: **********学院 专 业: ?网络工程 题 目: 利用栈求表达式的值 成绩 ? 指导教师 ****** ? ? 2009 年 7 ．设计目的 数据结构课程设计的目的是，通过设计掌握数据结构课程中学到的基本理论和算法并综合运用于解决实际问题中，它是理论与实践相结合的重要过程。设计要求学会如何对实际问题定义相关数据结构，并采用恰当的设计方法和算法解决问题，同时训练学生进行复杂程序设计的技能和培养良好的程序设计习惯。 设计内容和要求 利用栈求解表达式的值。 设计内容： 建立试题库文件，随机产生n个题目； 题目涉及加减乘除，带括弧的混合运算； 利用栈求解表达式的值； 随时可以退出； 保留历史分数，能回顾历史，给出与历史分数比较后的评价 基本要求： 1)系统功能的完善； 2)代码中有必要的注释 3．本设计所采用的数据结构 栈的数组表示方法（静态分配整型指针） typedef struct { typedef data[MAXSIZE]; int top; }; 4．功能模块详细设计 1.功能一：中缀表达式转化为后缀表达式； 2.功能二：后缀表达式求值； 3.功能三：文件读写； 4.功能四：作业评分； 5.功能五：历史成绩本次成绩比较； 6.功能六：输入“~”符号退出程序 4.1 详细设计思想 1.首先实现表达式的求值： 要用栈求解一个表达式,就要将这个表达式翻译成正确求值的一个机器指令序列,即正确解释表达式,了解算术四则混合运算的规则： (1).先乘除,后加减; (2).从左算到右; (3).先括号内,后括号外 再根据这个运算优先的规定来实现对表达式的编译或解释执行. 任何一个表达式都是由操作数(st)和操作符(op)组成的，根据四则运算基本法则，在运算的每一步中，任意两个相继出现的操作符op1和op2之间的优先关系最多有以下3种： (1).op1的优先级低于op2 (2).op1的优先级等于op2 (3).op1的优先级小于op2 为实现运算符优先，可以使用两个操作栈，操作栈st,用于存放操作数及运算结果；操作栈op，用于存放操作符。 算法思想： (1).首先将中缀表达式转换成后缀表达式： 1.从左至右依次扫描中缀表达式的每一个字符，如果是数字字符和“.” ，则直接将它们写入后缀表达式中。 2.如果遇到的是开括号“（”，则将它压入一个操作符栈中，它表明一个新的计算层次的开始，在遇到和它匹配的闭括号时，将栈中元素弹出并放入后缀表达式中，直到栈顶元素为开括号“（”时，将栈顶元素“（”弹出，表明这一层括号内的操作处理完毕。 3.如果遇到的是操作符，则将该操作符和操作符栈顶元素比较： a)当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到栈顶元素的优先级小于当前操作符的优先级； b)当所遇到的操作符的优先级大于栈顶元素的优先级时，则将它压入栈中。 重复上述步骤直到遇到中缀表达式的结束‘\0’，弹出栈中的所有元素并放入后缀表达式中，算法结束。 (2).对后缀表达式求值： 将遇到的操作数暂存在一个操作数栈中，凡是遇到操作符，便从栈中弹出两个操作数执行相应的操作，并将结果存于操作数栈中，直到表达式处理完毕，最后压入栈中的数就是表达式的结果。 2.建立试题库文件“shitiku.txt”和成绩库文件“chengji.txt”。 试题库文件“shitiku.txt”中存储20道带括号的四则混合运算；成绩库文件“chengji.txt”中存储历史成绩。 3.从试题库文件“shitiku.txt”中读出“total”道题： 当做的题目数小于“total”时，用随机函数产生每次要做的题号。 4.对本次作业进行评分： 本次作业共做题“total”道，每道“100/total”分； 做对题目数为“r”,本次作业得分为“r*(100/total)”。 5.输入“~”符号时，退出程序。 4.2 源代码 #includestdio.h #includestdlib.h #define MAXSIZE 30 int length[20]={13,15,12,9,11,17,13,15,9,11,11,11,12,10,15,13,18,16,16,9}; /*shitiku文件中20个字符串数组的长度*/ typedef struct { float data[MAXSIZE]; int top; }; float compvalu