数据结构算术表达式求值课程设计.doc

1 目目 录录 1 前 前 言言 2 2 问题描述问题描述 3 3 总体设计总体设计 3 3 1 概要设计概要设计 3 3 1 1 数据结构数据结构的选择的选择 3 3 1 2 相关功能函数相关功能函数 3 3 1 3 函数模块调用关系函数模块调用关系 4 3 2 详细设计和编码详细设计和编码 5 4 运行与测试运行与测试 9 4 1 上机调试上机调试 9 4 2 算法时间和空间性能分析算法时间和空间性能分析 10 4 3 程序运行测试结果程序运行测试结果 11 5 总结与心得总结与心得 13 5 1 设计中难点的总结以及其它解决方案设计中难点的总结以及其它解决方案 13 5 2 实验心得实验心得 14 6 用户使用说明用户使用说明 16 7 参考文献参考文献 16 8 附附 录录 1 源代码清单 源代码清单 16 9 附附 录录 2 成绩评定表 成绩评定表 25 2 1 前言前言 课程设计是实践性教学中的一个重要环节 它以某一课程为基础 它可以 涉及和课程相关的各个方面 是一门独立于课程之外的特殊课程 课程设计是 让同学们对所学的课程更全面的学习和应用 理解和掌握课程的相关知识 数据结构 是一门重要的专业基础课 是计算机理论和应用的核心基础课程 在数据结构的学习和课程设计过程中 我发现它要求学生在数据结构的逻 辑特性和物理表示 数据结构的选择和应用 算法的设计及其实现等方面 都 必须加深对课程基本内容的理解 同时 在程序设计方法以及上机操作等基本 技能和科学作风方面受到比较系统和严格的训练 对于我们专业来说 虽然说 对技术要求不是特别高 但是在实际操作过程中 没有足够的专业知识对于编 程来说是远远不可以达到要求的 所以对于这次的课程设计 我们必须要通过 自己额外补充知识来完成它 在这次的课程设计中我选择的题目是表达式的求值演示 它的基本要求是 以字符序列的形式从终端输入语法正确的 不含变量的表达式 利用算符优先 关系 实现对算术四则混合运算表达式的求值 并演示在求值中运算符栈 运 算数栈 输入字符和主要操作的变化过程 表达式计算是实现程序设计语言的 基本问题之一 也是栈的应用的一个典型例子 设计一个程序 演示用算符优 先法对算术表达式求值的过程 深入了解栈和队列的特性 以便在解决实际问 题中灵活运用它们 同时加深对这种结构的理解和认识 对于表示出栈在每执 行一个过程中都要输出它的变化 这点我认为在编程中是比较困难的 以我自 身的能力 是不可能在规定的时间内完成任务的 所以我参考了很多有价值的 书籍来帮助我完成我的程序设计 3 2 问题描述 问题描述 问题分析和任务定义 在计算机中 算术表达式由常量 变量 运算符和括号组成 由于不同的 运 算符具有不同的优先级 又要考虑括号 因此 算术表达式的求值不可能 严格 地 从左到右进行 因此 要求设计一个程序 利用栈演示运算符优先法 对算术表 达式求值的过程 利用算符有限关系 实现对算数混合四则运算表 达式的求值 程序输入 一个算术表达式 由常量 运算符和括号组成 以字符串 形式输入 不含变量 为了简化 操作数只能为浮点数 操作 符 为 用 表示结束 程序输出 表达式运算结果 运算符栈 运算数栈 输入字符和主要操作变 化过程 测试数据 1024 4 8 20 2 6 2 用于正确性检测的合法输入数据 9 0 用于健壮性检测的非法输入数据 3 总体设计总体设计 3 1 概要设计概要设计 3 1 1 数据结构的选择 任何一个表达式都是由操作符 运算符和界限符组成的 我们分别用顺序 栈 来寄存表达式的操作数和运算符 栈是限定于紧仅在表尾进行插入或删除 操作 的线性表 为了实现算符优先算法 可以使用两个工作栈 一个称做 OPTR 用以寄 存运算符 另一个称做 OPND 用以寄存操作数或运算结果 首先置操作数栈 为空栈 表达式起始符 作为运算符栈的栈底元素 然后依次读入表达式 的每个字符 若是操作数则进入 OPND 栈 若是运算符 则和 OPTR 栈的栈顶 运算符比较优先权后做相应操作 直至整个表达式求值完毕 栈的抽象数据类型定义 ADT SqStack 数据对象 D ai ai ElemSet i 1 2 3 n n 0 数据关系 R1 ai 1 ai D i 1 2 3 n 约定其中 ai 端为栈底 an 端为栈顶 操作集合 见如下相关功能函数 ADT SqStack 3 1 2 相关功能函数 运算符栈的功能函数运算符栈的功能函数 OPTR 栈 4 void Optr InitStack Optr Stack 算符栈的栈底 char top 算符栈的栈顶 int stacksize 算符栈的最大长度 Optr Stack OPND 栈定义如下 typedef struct float base 操作数栈的栈底 float top 操作数栈的栈顶 int stacksize 操作数栈的最大长度 Opnd Stack 然后是主要功能函数的详细设计 1 char Precede char m char n 判断运算符优先权 返回优先权高的 算符间的优先关系如下 1 2 6 函数实现如下 char Precede char m char n 运算符的优先级比较 if n n 输入符号为 if m m return 栈顶元素为 此时栈顶符号优先级低 返回 否则 栈顶符号优先级高 返回 else if n n 输入的符号为 if m m m return 栈顶元素为 此时栈顶符 号优先级高 返回 else return 否则 栈顶符号优先级低 返回 else if n return 输入的符号为 则直接返回 否则 栈顶符号优先级高 返回 else 输入符号为其他 if m return 栈顶元素为 此时优先级同 返回 else return 否则 栈顶符号优先级高 返回 2 void Evaluate Optr Stack float t e int n 0 i 1 j 0 k 0 l 0 char ch STACK INIT SIZE int s 1 int flag 0 flag2 0 7 float p1 p2 char ch1 Optr Push S1 将 入栈 作为低级运算符 cout ch c ch 0 cout n 对表达式求值的操作过程如下 n n 步骤 t 运算符栈 S1 t 运算数栈 S2 t 字符表达式 t t 栈操作过程 while c Optr GetTop S1 cout n n cout i t Optr DispStack S1 cout t t Opnd DispStack S2 cout t t if flag 1 k flag 0 if flag2 k flag2 flag2 0 for l 0 l k l cout for j k ch j 0 j cout 0 小数点前面的数 e float c 48 n if n 1 t e 8 else if n 1 t t 10 e 转换小数点前面的部分 c ch s if n 1 小数点后面的数 e float c 48 转换小数点后面的部分 t t e 10 c ch s 最终将转换后的两部分加起来 转换成浮点数 if c n 1 c ch s if c 0 goto as if c 9 Opnd Push S2 t cout t tOpnd Push S2 t else 输入的是运算符 n 0 非运算型数据计数器清零 switch Precede Optr GetTop S1 c 比较运算符的优先级 case 栈顶元素优先级低 则入栈且继续输入 Optr Push S1 c cout t tOptr Push S1 c c ch s break case 栈顶元素优先级相等 脱括号并接收下一字符 Optr Pop S1 cout 栈顶元素优先级高 则退栈并将运算结果入栈 p1 Opnd Pop S2 p2 Opnd Pop S2 ch1 Optr Pop S1 Opnd Push S2 Calculate p2 ch1 p1 cout t tCalculate p2 ch1 p1 flag 1 break cout n n cout i t t t Opnd GetTop S2 t t for j 0 j k j cout cout t t RETURN GETTOP S2 cout n n if S2 top 1 S2 base 显示表达式最终结果 cout n 表达式的结果为 Opnd GetTop S2 endl else cout n 表达式出错 n 3 float Calculate float a char theta float b 运算函数 运用 else if 语句 不同的运算符则进行不同的运算 进行除法 时 若分母为 0 则将标志标记成错误 函数实现如下 float Calculate float a char theta float b 运算函数 float tmp 0 if theta tmp a b 从运算符栈取出的符号为 则运算数栈的两 元素相加 并返回 else if theta tmp a b 从运算符栈取出的符号为 则运算数栈的两元 素相减 并返回 else if theta tmp a b 从运算符栈取出的符号为 则运算数栈的两元 素相乘 并返回 else if theta 从运算符栈取出的符号为 则运算数栈的两元 素相除 并返回 if b 0 cout i LocateChar c1 定位 c1 在 中的位 15 序 从 0 开始计数 j LocateChar c2 定位 c2 在 中的位 序 从 0 开始计数 if P i j cout 0 i c getchar Data i 0 数字没有存满 输入字符串结束符 16 d atof Data 此处是把数组里的数字 实际上是按字符串 转 换 为double 类型 return d 5 25 2 实验心得实验心得 通过此次课程设计 使我更加扎实的掌握了有关数据结构栈方面的知识 在 设计过程中虽然遇到了一些问题 但经过一次又一次的思考 一遍又一遍的检 查终于找出了原因所在 也暴露出了前期我在这方面的知识欠缺和经验不足 实践出真知 通过亲自动手制作 使我掌握的知识不再是纸上谈兵 而且通过 实际操作 我也发现我的好多不足之处 1 用栈的结构来解决表达式的求值 首先要解决的问题是如何将人们习惯 书写的表达式转换成计算机容易处理的表达式 开始有些茫然 后来通过结合 课本和同学的帮助完成了该课题 2 对一些看似简单的东西掌握不够熟练 比如由于函数的调用参数问题不 熟而造成了调试的困难 对于语法的掌握也欠缺成熟 需要进一步掌握 3 栈的结构理解不够清晰 造成了设计程序时理不清头绪 需要对数据结 构有更深层次的理解 这不仅要求要端正自己学习的态度 更要求要对程序设 计报以严谨的态度 我希望自己在以后的学习能更多的用到这些知识 过而能改 善莫大焉 在课程设计过程中 我们不断发现错误 不断改正 不断领悟 不断获取 最终的检测调试环节 本身就是在践行 过而能改 善 莫大焉 的知行观 在今后社会的发展和学习实践过程中 一定要不懈努力 不能遇到问题就想到要退缩 一定要不厌其烦的发现问题所在 然后一一进行 解决 只有这样 才能成功的做成想做的事 才能在今后的道路上劈荆斩棘 而不是知难而退 那样永远不可能收获成功 收获喜悦 也永远不可能得到社 会及他人对你的认可 课程设计诚然是一门专业课 给我很多专业知识以及专业技能上的提升 但它同时又是一门讲道课 一门辩思课 给了我许多道 给了我很多思 给了 我莫大的空间 同时 设计让我感触很深 使我对抽象的理论有了具体的认识 在这个过程中 我不仅培养了独立思考 动手操作的能力 还在各种其它能力 上也都有了提高 更重要的是 在实践中 我学会了很多学习的方法 而这是 日后最实用的 也是最受益匪浅的 要面对社会的挑战 只有不断的学习 实 践 再学习 再实践 这对于我们的将来也有很大的帮助 此外 本次课程设计也让我明白了思路即出路 有什么不懂不明白的地方 要及时请教老师或上网查询 只要认真钻研 动脑思考 动手实践 就没有弄 不懂的知识 收获肯定也会颇丰 17 6 用户使用说明用户使用说明 1 使用环境 Visual C 6 0 2 操作要求 程序运行后 用户根据提示输入合法的不含变量的算术表达式 以 输入结束 即可以计算出结果 并看到运算符与运算 数栈的操作过程 之后用户再根据提示 选择是否还要继续进 行算术表达式的运算 是则继续输入 否则退出程序 7 参考文献参考文献 1 严蔚敏 吴伟民 数据结构 C 语言版 M 北京 清华大学版社 2007 2 严蔚敏 吴伟民 米宁 数据结构习题集 C 语言版 M 北京 清华大学 版 社 2007 3 王淑礼 王新霞 算术表达式求值算法实现的难点剖析 J 福建电脑 2012 年 第 3 期 4 唐蔼明 谢泉钦 算术表达式程序设计算法分析 J 闽江学院学报 24 2 2013 年 4 月 5 殷人昆 数据结构 C 版 M 北京 清华大学版社 2001 8 附录附录 源程序清单 include using namespace std define STACK INIT SIZE 100 define STACKINCREMENT 10 typedef struct 运算符栈 char base char top int stacksize Optr Stack typedef struct 运算数栈 float base float top 18 int stacksize Opnd Stack void Optr InitStack Optr Stack 声明栈建立运算符函数 void Opnd InitStack Opnd Stack 声明栈建立运算数数函数 void Evaluate Optr Stack 声明确定如何入栈函 数 void Optr Push Optr Stack 声明运算符入栈函数 void Opnd Push Opnd Stack 声明运算数入栈函数 char Optr GetTop Optr Stack 声明取运算符栈顶元素函数 float Opnd GetTop Opnd Stack 声明取运算数栈顶元素函数 char Optr Pop Optr Stack 声明运算符出栈函数 float Opnd Pop Opnd Stack 声明运算数出栈函数 char Precede char m char n 声明运算符优先级比较函数 float Calculate float a char rheta float b 声明运算表达式函数 void Optr DispStack Optr Stack 从运算符栈底到栈顶依次输出 各 运算符 void Opnd DispStack Opnd Stack 从运算数栈底到栈顶依次输出 各 运算数 主函数 int main Optr Stack S1 定义运算符栈 Opnd Stack S2 定义运算数栈 freopen data1 in r stdin freopen data1 out w stdout int flag 1 while flag 可以反复进行算术表达式的求值 int m Optr InitStack S1 调用运算符栈建立函数 Opnd InitStack S2 调用运算数栈建立函数 Evaluate S1 S2 输入字符表达式确定如何入栈函数 cout 请问是否继续算术表达式求值 0 否 1 是 endl 与 用 户进行简单的会话是否继续 输入1就继续 0就退出 cout m flag m 19 return 0 运算符栈函数 void Optr InitStack Optr Stack if S1 base cout S1 stacksize 如果栈满 追加存储空间 S1 base char realloc S1 base S1 stacksize STACKINCREMENT size of char if S1 base cout 存储分配失败 else S1 top S1 base S1 stacksize S1 stacksize S1 stacksize STACKINCREMENT S1 top e S1 top S1 top 1 将运算符压入栈中 指针上移 char Optr GetTop Optr Stack if S1 top S1 base cout n t t t运算符栈已空 n else e S1 top 1 return e void Optr DispStack Optr Stack if S1 top S1 base cout else 20 p S1 base while p S1 top e p p cout e char Optr Pop Optr Stack if S1 top S1 base cout n t t t运算符栈已空 n e S1 top return e 运算数栈函数 void Opnd InitStack Opnd Stack if S2 base cout S2 stacksize 栈满 追加存储空间 S2 base float realloc S2 base S2 stacksize STACKINCREMENT siz eof float if S2 base cout 存储分配失败 else S2 top S2 base S2 stacksize S2 stacksize S2 stacksize STACKINCREMENT 21 S2 top e S2 top S2 top 1 将数e入栈 指针上移 void Opnd DispStack Opnd Stack if S2 top S2 base cout else p S2 base while p S2 top e p p cout e float Opnd GetTop Opnd Stack if S2 top S2 base cout n t t运算数栈已空 else e S2 top 1 return e float Opnd Pop Opnd Stack if S2 top S2 base cout n t t运算数栈已空 e S2 top return e 输入表达式确定如何入栈函数 void Evaluate Optr Stack float t e 22 int n 0 i 1 j 0 k 0 l 0 char ch STACK INIT SIZE int s 1 int flag 0 flag2 0 float p1 p2 char ch1 Optr Push S1 将 入栈 作为低级运算符 cout ch c ch 0 cout n对表达式求值的操作过程如下 n n 步骤 t运算符栈S1 t运算数栈S2 t字符表达式 t栈主要操作过 程 while c Optr GetTop S1 cout n n cout i t Optr DispStack S1 cout t t Opnd DispStack S2 cout t t if flag 1 k flag 0 if flag2 k flag2 flag2 0 for l 0 l k l cout for j k ch j 0 j cout 0 e float c 48 n if n 1 t e else if n 1 t t 10 e 转换小数点前面的部 分 c ch s if n 1 e float c 48 转换小数点后面的部分 t t e 10 c ch s 将转换后的两部分加起 来 最终转换成浮点数 if c n 1 c ch s if c 0 goto as if c 9 Opnd Push S2 t cout tOpnd Push S2 t else 输入的是运算符 n 0 非运算型数据计数器清零 switch Precede Optr GetTop S1 c 比较运算符的优先级 24 case 栈顶元素优先级低 则入栈且继续输入 Optr Push S1 c cout tOptr Push S1 c c ch s break case 栈顶元素优先级相等 脱括号并接收下一字符 Optr Pop S1 cout 栈顶元素优先级高 则退栈并将运算结果入栈 p1 Opnd Pop S2 p2 Opnd Pop S2 ch1 Optr Pop S1 Opnd Push S2 Calculate p2 ch1 p1 cout tCalculate p2 ch1 p1 flag 1 break cout n n cout i t t t Opnd G