数据结构表达式求值课程设计报告.doc

数数据据结结构构课课程程设设计计报报告告 2011 2012 年度第年度第 1 学期学期 表达式求值表达式求值 专业专业计算机科学与技术计算机科学与技术 学生姓名学生姓名 班级班级 学号学号 指导教师指导教师 完成日期完成日期 表达式求值 目目 录录 目 录 2 1 概 述 1 1 1 课程设计目的 1 1 2 课程设计内容 1 2 系统需求分析 1 2 1 系统目标 1 2 2 主体功能 1 2 3 开发环境 1 3 系统概要设计 2 3 1 系统的功能模块划分 2 3 2 系统流程图 2 4 系统详细设计 3 5 测试 6 5 1 测试方案 6 5 2 测试结果 6 6 小结 8 参考文献 10 附录 1 源程序清单 11 表达式求值 0 表达式求值表达式求值 1 概 述 1 1 课程设计目的 1 要求学生达到熟练掌握 C 语言的基本知识和技能 2 了解并掌握数据结构与算法的设计方法 具备初步的独立分析和设计能力 3 提高程序设计和调试能力 学生通过上机实习 验证自己设计的算法的正 确性 学会有效利用基本调试方法 迅速找出程序代码中的错误并且修改 4 培养算法分析能力 分析所设计算法的时间复杂度和空间复杂度 进一步 提高程序设计水平 5 初步掌握软件开发过程的问题分析 系统设计 程序编码 测试等基本方 法和技能 1 2 课程设计内容 设计一个表达式求值的程序 该程序必须可以接受包含 和 求幂运算符 a b ab 的中缀表达式 并求出结果 如果表达式 正确 则输出表达式的结果 如果表达式非法 则输出错误信息 2 系统需求分析 2 1 系统目标 利用栈设计一个程序 该程序能够用于表达式求值 程序将读入的中缀表达 式转换为后缀表达式 然后读取后缀表达式 输出结果 输入要求 程序从 input txt 文件中读取信息 在这个文件中如果有多个 中缀表达式 则每个表达式独占一行 程序的读取操作在文件的结尾处停止 输出要求 对于每一个表达式 将其结果放在 output txt 文件的每一行 中 这些结果可能是值 精确到小数点后两位 也可能是错误信息 ERROR IN INFIX NOTATION 2 2 主体功能 能够处理以字符序列的形式输入的不含变量的实数表达式 正确处理负数与小数 判断表 达式是否语法正确 包含分母不能为零的情况 正确实现对算术四则混合运算表达式的求值 能够将计算中遇到的问题和结果以文件的形式予以存储 数据结构课程设计报告 2012 1 2 3 开发环境 Microsoft Visual C 6 0 3 系统概要设计 3 1 系统的功能模块划分 1 判断操作数的函数 isnum 判断当前所指字符是否属于数字 是就返回 1 不是就返回 0 2 求运算符优先级函数 priority 为了方便判断运算符优先级 先利用 switch 函数将不同的运算符返回不同的 整型数字 在根据数字的大小判断优先级 优先级相同 返回数字相同 也是 3 表达式求值函数 infix value 此函数是直接按照设计思路完成问题要求的函数 其中要调用到判断操作符的 函数 isnum 和求运算符优先级的函数 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 charGetTop SeqStack 销毁栈 Destory SeqStack charDestory SeqStack 3 2 系统流程图 表达式求值 2 开始 优先级比较算法 Operate 算法 建立栈 存放操作字符存放数据 计算 结束 表达式是 否合法 输出表达是值输出错误提 示 图 1 系统流程图 4 系统详细设计系统详细设计 1 基本分析 在计算机中 算术表达式的计算往往是通过使用栈来实现的 所以 本表达 式求值程序的最主要的数据结构就是栈 可以使用栈来存储输入表达式的操作符 和操作数 输入的表达式是由操作数和运算符以及改变运算次序的圆括号连接而成的式 子 表达式求值是高级语言编译中的一个基本问题 是栈的典型应用实例 任何 一个表达式都是由操作数 operand 运算符 operator 和界限符 delimiter 组 成的 操作数既可以是常数 也可以是被说明为变量或常量的标识符 运算符可 以分为算术运算符 关系运算符和逻辑运算符三类 基本界限符有左右括号和表 达式结束符等 2 中缀表达式求值 中缀表达式 每个二目运算符在两个运算量的中间 假设操作数是整型常数 运算符只含加 减 乘 除等四种运算符 界限符有左右括号和表达式起始 结 数据结构课程设计报告 2012 3 束符 如 7 15 23 28 4 要对一个简单的算术表达式求值 首先 要了解算术四则运算的规则 即 1 从左到右 2 先乘除 后加减 3 先括号内 后括号外 运算符和界限符可统称为算符 它们构成的集合命名为 OPS 根据上述三条运 算规则 在运算过程中 任意两个前后相继出现的算符 1 和 2 之间的优先关 系必为下面三种关系之一 1 2 1 的优先权高于 2 实现算符优先算法时需要使用两个工作栈 一个称作 operator 用以存放运 算符 另一个称作 operand 用以存放操作数或运算的中间结果 算法的基本过程 如下 首先初始化操作数栈 operand 和运算符栈 operator 并将表达式起始符 压入运算符栈 依次读入表达式中的每个字符 若是操作数则直接进入操作数栈 operand 若 是运算符 则与运算符栈 operator 的栈顶运算符进行优先权比较 并做如下处理 1 若栈顶运算符的优先级低于刚读入的运算符 则让刚读入的运算符进 operator 栈 2 若栈顶运算符的优先级高于刚读入的运算符 则将栈顶运算符退栈 送 入 同时将操作数栈 operand 退栈两次 得到两个操作数 a b 对 a b 进行 运算后 将运算结果作为中间结果推入 operand 栈 3 若栈顶运算符的优先级与刚读入的运算符的优先级相同 说明左右括号 相遇 只需将栈顶运算符 左括号 退栈即可 operator 栈的栈顶元素和当前读 入的字符均为 时 说明表达式起始符 与表达式结束符 相遇 整个 表达式求解结束 int ExpEvaluation 读入一个简单算术表达式并计算其值 InitStack InitStack PushStack printf n n Please input an expression Ending with ch getchar 读入表达式中的一个字符 while ch GetTop operator if In ch OPS 判断 ch 是否运算符 a GetNumber 用 ch 逐个读入操作数的各位数码 并转 化为十进制数 a PushStack else switch Compare GetTop operator ch case PopStack PopStack PopStack v Execute a op b PushStack break v GetTop operand return v 为了处理方便 编译程序常把中缀表达式首先转换成等价的后缀表达式 后 缀表达式的运算符在运算对象之后 在后缀表达式中 不再引入括号 所有的计 算按运算符出现的顺序 严格从左向右进行 而不用再考虑运算规则和级别 中 缀表达式 a b c d e 的后缀表达式为 abc de 3 后缀表达式求值 计算一个后缀表达式 算法上比计算一个中缀表达式简单的多 这是因为表 达式中即无括号又无优先级的约束 具体做法 只使用一个对象栈 当从左向右 扫描表达式时 每遇到一个操作数就送入栈中保存 每遇到一个运算符就从栈中 取出两个操作数进行当前的计算 然后把结果再入栈 直到整个表达式结束 这 时送入栈顶的值就是结果 下面是后缀表达式求值的算法 在下面的算法中假设 每个表达式是合乎语 法的 并且假设后缀表达式已被存入一个足够大的字符数组 A 中 且以 为结 束字符 为了简化问题 限定运算数的位数仅为一位且忽略了数字字符串与相对 应的数据之间的转换问题 double calcul exp char A 本函数返回由后缀表达式 A 表示的表达式运算 结果 SeqStarck s ch A InitStack s while ch if ch 运算符 PushStack s ch else PopStack s PopStack s 取出两个运算量 switch ch case ch c a b break case ch c a b break case ch c a b break case ch c a b break case ch c a b break PushStack s c ch A 数据结构课程设计报告 2012 5 PopStack s result return result 4 中缀表达式转换成后缀表达式 将中缀表达式转化为后缀表达式和前述对中缀表达式求值的方法完全类似 但只需要运算符栈 遇到运算对象时直接放后缀表达式的存储区 假设中缀表达 式本身合法且在字符数组 A 中 转换后的后缀表达式存储在字符数组 B 中 具体 做法 遇到运算对象顺序向存储后缀表达式的 B 数组中存放 遇到运算符时类似 于中缀表达式求值时对运算符的处理过程 但运算符出栈后不是进行相应的运算 而是将其送入 B 中存放 读者不难写出算法 在此不在赘述 程序的整体算法分两步 第一步 从 input txt 文件中读取中缀表达式 并应用运算符栈 OpHolder 把中 缀表达式转换为后缀表达式 将输出结果存放在一个 temp 文件中 第二步 从 temp 文件中读取中缀表达式 并应用操作栈 Operands 计算后缀表 达式结果 将结果输出到 output txt 文件中 5 测试 5 1 测试方案 设计针对程序的 input txt 文件 并将运行结果与期望测试进行比较 5 2 测试结果 1 基本测试 在 input 文件中输入表达式如下图 2 则输出结果如下图 3 图 2 图 3 表达式求值 6 图 4 2 扩展测试 在 input 文件中输入表达式如下图 5 则输出结果如下图 6 图 5 图 6 3 容错测试 在 input 文件中输入表达式如下图 7 则输出结果如下图 8 数据结构课程设计报告 2012 7 图 7 图 8 6 小结 通过此次的课程设计 巩固和加深了我对栈 队列 字符串等理论知识的理解 掌握现实复杂问题的分析建模和解决方法 提高利用计算机分析解决综合性实 际问题的基本能力 在细节问题的分析上 较以往有了很大的提高 在寻求最优解的问题上 也能 够找到多种解决方案来使自己的程序收放自如 如 在处理实数的问题上 我采 用的是每取得一个字符 就立刻对此字符进行处理的方法 其实 我们可以用一 个字符数组 来存储连接着的一系列数字字符 然后再通过 atof 函数 直接得到 字符数组中所存储的数字 再如 对负数问题的处理上 我最初的想法是通过一 个标志 mark 来记录前面的字符是否是负号 或减号 再在后面取到除符号外的 数字时 选择是否添加负号 另外 与其他人不同的是 在我的课程设计中 Compare 函数与其他有着很大的区别 通常情况下 同学们参照课本 都会采 用占用 7 7 49 个空间的数组来分别存储对应两个字符的优先级符号 并对两个字 符进行预算之后得到数组中的位置 虽然 7 7 的数组所占的空间并不是非常大 但在我看来这也是一种浪费 并且空间的浪费并没有换回时间一定的节省 因此 我采用了一种常规的思路 将各种运算符按照数学逻辑上的优先顺序进行排序 并得到两个字符之间的优先级关系 这样一来 我们将不再需要那 7 7 的数组 且时间复杂度并不大幅增涨 在这个课程设计中 运用到的数据结构的知识主要是栈的知识 栈在各种软件 表达式求值 8 系统中 应用非常广泛 栈的的存储特性 LIFO 先进后出 使得在用栈来编程时 思路清晰明了 在使用递归算法时 栈也是一种很好的选择 此外 这次的课程设计进一步加强了我们运用 C 语言进行编程 调试 处理 问题的能力 加深了我们对算法及数据结构的认识 同时我也意识到 开发程序 的早期计划要做的充分 以免出现程序完成后发现不足而带来的修改麻烦 虽然 这只是一个小小的软件 但对我们之后的影响确实很大的 数据结构课程设计报告 2012 9 参考文献参考文献 1 范策 周世平 胡哓琨 算法与数据结构 C 语言版 M 北京 机械工 业出版社 2004 2 严蔚敏 数据结构 C 语言版 北京 清华大学出版社 2004 3 许卓群 杨冬青 唐世渭 张铭 数据结构与算法 北京 高等教育出 版社 2004 4 徐孝凯 数据结构实用教程 第二版 北京 清华大学出版社 2006 表达式求值 10 附附 录录 附录 1 源程序清单 include include include int PrintError 0 全局变量 0代表正常 1代表表达式出错 char类型链表式堆栈 用来存放运算符号 以及用在中缀表达式转换等时候 typedef struct Node PtrToNode typedef PtrToNode Stack int IsEmpty Stack S void MakeEmpty Stack S void Push char X Stack S char Top Stack S void Pop Stack S typedef struct Node char Element PtrToNode Next float类型链表式堆栈 用来存放操作数 typedef struct FNode Ptr Fn typedef Ptr Fn FStack int FisEmpty FStack S void FPush float X FStack S float FTop FStack S void FPop FStack S typedef struct FNode float Element Ptr Fn Next void ConvertToPost FILE In Stack Whereat FILE Temp void Reverse Stack Rev void Calculate FILE Change Stack Whereat FILE Temp 主函数 数据结构课程设计报告 2012 11 int main FILE InputFile OutputFile Temp 初始化变量 Stack Whereat char sample InputFile fopen Input txt r 打开文件 OutputFile fopen Output txt w Whereat malloc sizeof struct Node 给 Whereat分配空间 Whereat Next NULL if InputFile OutputFile 错误处理 printf intput or output file s do not exist n return 1 sample getc InputFile while sample EOF Temp fopen Temp txt w 生成Temp文件 ungetc sample InputFile put back sample字符 ConvertToPost InputFile Whereat Temp 中缀变后缀 if PrintError 错误处理 fprintf OutputFile Error in infix notation fscanf InputFile n PrintError 0 else if IsEmpty Whereat 1 跳过在input文件中的空格 else if IsEmpty Whereat 1 Reverse Whereat if Top Whereat B 错误处理 A表示操作数B表示运算 符 PrintError 1 后缀表达式第一个元素应是操作 数而不是运算符号 fclose Temp Temp fopen Temp txt r Calculate OutputFile Whereat Temp 计算结果 表达式求值 12 fclose Temp MakeEmpty Whereat 清空Whereat用来处理下一 行 putc n OutputFile 在输出文件中换行 sample getc InputFile While循环结束 free Whereat fclose InputFile fclose OutputFile remove Temp txt 删除Temp txt return 1 检查堆栈是否为空 int IsEmpty Stack S return S Next NULL 检查float堆栈是否为空 int FIsEmpty FStack S return S Next NULL 弹出栈顶元素 void Pop Stack S PtrToNode FirstCell if IsEmpty S perror Empty Stack else FirstCell S Next S Next S Next Next free FirstCell 弹出float栈顶元素 void FPop FStack S Ptr Fn FirstCell 数据结构课程设计报告 2012 13 if FIsEmpty S perror Empty Stack else FirstCell S Next S Next S Next Next free FirstCell 将堆栈置空 void MakeEmpty Stack S if S NULL perror Must use Createstack first else while IsEmpty S Pop S 将float堆栈置空 void FMakeEmpty FStack S if S NULL perror Must use Createstack first else while IsEmpty S Pop S 元素进栈 void Push char X Stack S PtrToNode TmpCell TmpCell PtrToNode malloc sizeof struct Node if TmpCell NULL perror Out of Space else TmpCell Element X TmpCell Next S Next S Next TmpCell 表达式求值 14 float元素进栈 void FPush float X FStack S Ptr Fn TmpCell TmpCell Ptr Fn malloc sizeof struct FNode if TmpCell NULL perror Out of Space else TmpCell Element X TmpCell Next S Next S Next TmpCell 返回栈顶元素 char Top Stack S if IsEmpty S return S Next Element perror Empty Stack exit 1 return 0 返回float栈顶元素 float FTop FStack S if FIsEmpty S return S Next Element perror Empty Stack exit 1 return 0 将堆栈元素倒置 void Reverse Stack Rev Stack Tempstack Tempstack malloc sizeof struct Node Tempstack Next NULL 数据结构课程设计报告 2012 15 while IsEmpty Rev Push Top Rev Tempstack 将元素压栈到一个临时堆栈 Pop Rev Rev Next Tempstack Next 指向新的堆栈 Whereat 说明 Whereat 记录了操作数和运算符号的位置 用A和B区分 A operand B operator 例如 1 2转换成12 在whereat中的形式应该是 AAB OpHolder说明 Char类型的堆栈Opholder用来保存运算符号 将中缀表带式转换为后缀表达式 void ConvertToPost FILE In Stack Whereat FILE Temp Stack OpHolder char holder char lastseen int digitcounter 0 操作数的计数器 OpHolder malloc sizeof struct Node 初始化 OpHolder Next NULL holder getc In lastseen 用来防止输入格式错误 例如两 个小数点 putc Temp while holder n else if IsOperator holder 1 如果holder不是操作数或运算符 号 PrintError 1 else if IsOperator holder 0 if lastseen holder else lastseen holder if digitcounter 0 Push A Whereat 进栈 digitcounter 计数器加一 putc Temp putc holder Temp else digitcounter 0 if lastseen holder else lastseen holder if IsEmpty OpHolder 1 当OpHolder为空 Push holder OpHolder else if OperatorValue Top OpHolder 6 OpHolder是 的情况 if OperatorValue holder 5 Pop OpHolder else Push holder OpHolder else if OperatorValue holder 6 Push holder OpHolder else if OperatorValue holder 5 OpHolder是 的情况 while IsEmpty OpHolder 1 Push B Whereat putc Top OpHolder Temp Pop OpHolder 数据结构课程设计报告 2012 17 if IsEmpty OpHolder 1 错误处理 括号不匹配 PrintError 1 else Pop OpHolder else if OperatorValue holder OperatorValue Top OpHolder else if OperatorValue holder OperatorValue holder while IsEmpty OpHolder 1 putc Top OpHolder Temp Push B Whereat Pop OpHolder Push holder OpHolder else if OperatorValue Top OpHolder Next NULL while IsEmpty Whereat 1 fscanf Temp f 如果是A 则是操作数 FPush looker Operands Pop Whereat else if Top Whereat B fscanf Temp 如果是B 则是运算符 Op getc Temp switch Op 判断是什么运算符 case 幂运算 NumB FTop Operands FPop Operands if FIsEmpty Operands 错误处理 PrintError 1 else NumA FTop Operands FPop Operands if NumA 0 else answer pow NumA NumB FPush answer Operands break 数据结构课程设计报告 2012 21 case 取模运算 NumB FTop Operands FPop Operands if FIsEmpty Operands 错误处理 PrintError 1 else NumA FTop Operands FPop O