已阅读5页,还剩22页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
C C 程程序序设设计计 课程设计报告课程设计报告 选题名称选题名称 表 达 式 求 值 系 院 系 院 计 算 机 工 程 系 专专 业业 计算机科学与技术 班班 级级 姓姓 名名 学学 号号 指导教师指导教师 学年学期学年学期 学年 第 学期 年 月 日 设计任务书设计任务书 课题课题 名称名称 表达式求解 设计设计 目的目的 1 调研并熟悉表达式求解的基本功能 数据流程与工作规程 2 学习编译原理 基于 VC 集成环境的编程技术 3 通过实际编程加深对基础知识的理解 提高实践能力 4 学习开发资料的收集与整理 学会撰写课程设计报告 实验实验 环境环境 1 微型电子计算机 PC 2 安装 Windows 2000 以上操作系统 Visual C 6 0 开发工具 任务任务 要求要求 1 利用课余时间去图书馆或上网查阅课题相关资料 深入理解课题含义及 设计要求 注意材料收集与整理 2 在第 15 周末之前完成预设计 并请指导教师审查 通过后方可进行下一 步工作 3 本课题主要实现动态接受输入的任意表达式 能适应 1 5 位数的四则运 算 不但适应整数也要适应小数运算等 4 结束后 及时提交设计报告 含纸质稿 电子稿 要求格式规范 内容 完整 结论正确 正文字数不少于 3000 字 不含代码 工作进度计划工作进度计划 序号序号起止日期起止日期工工 作作 内内 容容 1 2 3 4 指导教师 签章 指导教师 签章 年年 月月 日日 摘要 表达式求值是程序设计语言 诸如 C C 语言编译中的一个最基本的问题 它的实现需要使用到栈 表达式是由运算对象 运算符 括号组成的有意义的 式子 运算符从运算对象的个数上分 有单目运算符和双目运算符 从运算类 型上分 有算术运算 关系运算 逻辑运算 在此仅限于讨论只含二目运算符 的算术表达式 此程序已完成功能 当用户输入一个合法的表达式后 能够返 回正确的结果 能够计算的运算符包括 加 减 乘 除 括号 次方 负号 能够计算的数包括正数 负数 小数 对于异常表达式给出错误提示 如计算用户输入四则运算表达式 1 2 4 5 13 88 5 6 78 3 能得出最终结果 关键词 栈 指针 循环 数据结构 目录目录 1 课题综述 1 1 1 1 课题来源 1 1 2 意义 1 1 3 预期目标 1 1 4 面对的问题 2 2 课题分析 2 2 1 基础知识 2 2 2 总体方案 4 2 3 功能模块框图 5 2 4 算法描述 6 2 5 代码说明 9 2 6 运行与测试 18 总结 20 致谢 21 参考文献 22 C 程序设计课程设计报告 1 1 课题综述课题综述 表达式求值是程序设计语言 诸如 C C 语言编译中的一个最基本的问题 它的实现需要使用到栈 表达式是由运算对象 运算符 括号组成的有意义的 式子 运算符从运算对象的个数上分 有单目运算符和双目运算符 从运算类 型上分 有算术运算 关系运算 逻辑运算 在此仅限于讨论只含二目运算符 的算术表达式 1 1 课题来源课题来源 由运算符 操作数及标点符号组成的 能取得一个值的式子称为表达式 表达式中的操作数可以是常量 变量或函数等 一个常数或一个变量即是最简 单的表达式 表达式的求值要根据运算符的意义 求值次序 优先级 结合性 以及类型转换约定进行 运用表达式求值可以解决科学 工程 日常生活等中 的数值计算问题 表达式求值是程序设计语言 诸如 C 语言编辑中的一个最基本的问题 它的实现需要使用到栈 栈是限制在表的一端进行插入和删除的线性表 允许插入和删除的一端为 栈顶 另一固定端为栈底 当表中没有元素时称为空栈 所以栈又称为后进先 出的线性表 简称 LIFO 表 在日常生活中有很多后进先出的例子 例如 分币筒 铁路调度站等 在 程序设计中 常常需要使得与保存数据时相反的顺序来使用这些数据 这时就 需要用一个栈来实现 1 2 意义意义 调研并熟悉表达式求解的基本功能 数据流程与工作规程 学习编译原理 基于 VC 集成环境的编程技术 通过实际编程加深对基础知识的理解 提高 实践能力 学习开发资料的收集与整理 学会撰写课程设计报告 1 3 预期目标预期目标 能适应 1 5 位数的四则运算 能适应正数 负数的运算 C 程序设计课程设计报告 2 不但适应整数 同时要求使用小数运算 能接受常见的一些数学函数 如 abs log sqrt sin cos 等 可以不区分大小写 仿计算器界面 动态接受输入的任意表达式 人机界面自定义 要友好 如用户输入错误在计算之前可以修改 提高要求 图形化操作界面 扩充运算符 1 4 面对的问题面对的问题 只能进行实数的一些简单的四则运算和次方运算 不能接受 abs log sqrt sin cos 等函数 2 课题分析课题分析 2 1 基础知识基础知识 栈 stack 是最常用和最重要的数据结构 局部变量是放在栈中的 表达 式的优先级处理也是基于栈来实现的 函数调用时的参数传递和函数值的返回 都是由栈来实现的 栈是限制在表的一端进行插入和删除的线性表 即一维数 组 允许插入删除的一端为栈顶 另一固定端为栈底 当表中没有元素时称 为空栈 如图 2 1 所示 栈中有三个元素 进栈的顺序是 a1 a2 a3 当需要 出栈时其顺序为 a3 a2 a1 所以栈又称为后进先出的线性表 Last In First Out 简称 LIFO 表 C 程序设计课程设计报告 3 在日常生活中 有很多后进先出的例子 在程序设计中 常常需要使得与 保存数据时相反顺序来使用这些数据 这时就需要用一个栈来实现 对于栈 常做的基本运算有 1 栈初始化 Init Stack s 初始条件 栈 s 不存在 操作结果 构造了一个空栈 2 判断栈空 Empty Stack s 初始条件 栈 s 已存在 操作结果 若栈 s 为空栈返回为 1 否则返回为 0 3 入栈 Push Stack s x 初始条件 栈 s 已存在 操作结果 在栈 s 的顶部插入一个新元素 x x 成为新的栈顶元素 栈发 生变化 4 出栈 Pop Stack s 初始条件 栈 s 存在且非空 操作结果 栈 s 的顶部元素从栈中删除 栈中少了一个元素 栈发生变化 出栈 入栈 图 2 1 a1 a2 top a3 C 程序设计课程设计报告 4 5 读栈顶元素 Top Stack s 初始条件 栈 s 存在且非空 操作结果 栈顶元素作为结果返回 栈不变化 栈可以用顺序表实现 称为顺序栈 也可以用链表实现 称为链栈 顺序栈和 链栈的逻辑功能一样 顺序栈必须先开一定大小的内存空间 执行起来简单并 且速度快 但可能溢出 链栈的内存空间随用随开 不会溢出 但执行复杂 不断地动态分配 且速度慢 2 2 总体方案总体方案 建立两个栈 一个是操作数栈 用来寄放操作或运算结果 另一个是运 算符栈 用来寄放运算符和界限符 读入表达式中的字符 若是操作数则压进操作数栈 若是运算符 则与 运算符栈的栈顶元素比较优先级 根据比较的结果作相应的操作 建立两个栈 操作数栈 ODS 和操作符栈 OPS 然后自左至右扫描 表达式 为叙述简洁 仅讨论算术表达式的计算 且假设表达式中只含有加 减 乘 除四种运算符和左 右圆括号 一个表达式用 作为分界符标识表达 式的结束 并将表达式中自左至右所读到的一个操作数或一个操作符称为 一个 词 用栈实现表达式求值的处理过程如下 读入一个词 判断该词是操作数还是操作符 如果是操作数 则将该操作数压入 ODS 栈 并转第 1 步 否则继续往下 判断表达式是否结束 是结束符则转第 7 步 否则继续往下 判断当前操作符优先级是否大于或等于 OPS 栈顶操作符的优先级 左括 号的优先级最高 其次是乘除 再是加减 右括号的优先级最低 或者 OPS 栈 是否为空 如果是 当前操作符压入 OPS 栈并转第 1 步 否则 继续往下 从 ODS 栈中弹出两个操作数 Y 和 X 从 OPS 栈中弹出一个操作符 进行运 算 X Y 并将结果压入 ODS 栈 需要说明的是 如果当前操作符是右括号 则重复第 5 步这一过程 直到 OPS 栈顶操作符为左括号 当前操作符压入 OPS 栈 如果当前操作符是右括号 则它不但不压入 C 程序设计课程设计报告 5 OPS 栈中 相反还从 OPS 栈中弹出左括号 这称为去括号 后 转第 1 步 判断 OPS 栈是否为空 不是 则从 ODS 栈中弹出两个操作数 Y 和 X 从 OPS 栈中弹出一个操作符 进行运算 X Y 并将结果压入 ODS 栈 ODS 栈顶的值即为所求表达式的值 求值过程结束 定义几个函数 实现算法的直接调用 最后解决操作数的读取问题 如果遇到数字或小数点 则连续读入一个 数字字符串到数组中 然后将其转化为实数 压入操作数栈 2 3 功能模块框图功能模块框图 利用栈处理算术表达式 a b d e f 的过程如下图 2 3 所示 图 2 3 a 表示了依次读入表达式中的 a b d e 等单词 后操作数栈 ODS 图示的左边 和操作符栈 OPS 图示的右边 的状态 图 2 3 b 和图 2 3 c 表示了读入 后 去括号的过程 其中 t1 d e t2 b t1 图 2 3 d 表示了读入 后 ODS 和 OPS 的状态 其中 t3 a t2 图 2 3 e 表示了读入 f 后 ODS 和 OPS 的状态 图 2 3 f 表示了读入表达式结束符后 ODS 和 OPS 的状态 其中 t4 t3 f 此时 操作符栈 OPS 为空 操作数栈 ODS 的栈顶元素 t4 就是所求的表达式的值 图 2 3 利用栈处理表达式 a b d e f 的示意图 C 程序设计课程设计报告 6 开始 是否是数值 输入表达 式 并从 左向右扫 描表达式 是 否 是否为数字 字符 是 处理成数字字符并 入字符栈 判断是否 结束 是 否 否 是否为算 符 否 运算并输出 结果 数学函数运算 结果入数字栈 结束 运算 结果 入栈 运算符栈 是 2 4 算法描述算法描述 1 中缀表达式求值 中缀表达式 每个二目运算符在两个运算量的中间 假设所讨论的算术运 算符包括 乘方 和括号 设运算规则为 C 程序设计课程设计报告 7 运算符的优先级为 有括号出现时先算括号内的 后算括号外的 多层括号 由内向外进行 乘方连续出现时先算最右面的 表达式作为一个满足表达式语法规则的串储存 如表达式 3 2 4 2 2 1 3 5 它的求值过程为 自左向右扫描表达式 当扫描到 3 2 时不能马上 计算 因为后面可能还有更高的运算 正确的处理过程是 需要两个栈 对象 栈 s1 和算符栈 s2 当自左至右扫描表达式的每一个字符时 若当前字符是运算 对象 入对象栈 是运算符时 若这个运算符比栈顶运算符高则入栈 继续向 后处理 若这个运算符比栈顶运算符低则从对象栈出栈两个运算量 从算符栈 出栈一个运算符进行运算 并将其结果入对象栈 继续处理当前字符 直到遇 到结束符 根据运算规则 左括号 在栈外时它的级别最高 而进栈后它的级别 则最低了 乘方运算的结合性是自右向左 所以 它的栈外级别高于栈内 就 是说有的运算符栈内栈外的级别是不同的 当遇到右括号 时 一直需要 对运算符出栈 并且做相应的运算 直到遇到栈顶为左括号 时 将其出 栈 因此右括号 级别最低但它是不入栈的 对象栈初始化为空 为了使 表达式中的第一个运算符入栈 算符栈中预设一个最低级的运算符 根据以上分析 每个运算符栈内 栈外的级别如下 算符栈内级别栈外级别 34 22 11 04 1 1 表 2 2 1 中缀表达式 3 2 4 2 2 1 3 5 求值过程中两个栈的状态情况见下图所示 读字符对象栈 s1算符栈 s2说明 33 3 入栈 s1 3 入栈 s2 C 程序设计课程设计报告 8 2 3 2 2 入栈 s1 3 2 入栈 s2 3 2 入栈 s2 4 3 2 4 4 入栈 s1 3 2 4 入栈 s2 2 3 2 4 2 2 入栈 s1 3 2 4 2 入栈 s2 2 3 2 4 2 2 2 入栈 s1 3 2 4 4 做 2 2 结果入栈 s1 3 2 8 做 4 4 结果入栈 s2 3 2 8 入栈 s2 1 3 2 8 1 1 入栈 s1 3 2 8 1 入栈 s2 3 3 2 8 1 3 3 入栈 s1 3 2 8 3 做 1 3 结果入栈 s1 3 2 5 做 8 3 结果入栈 s2 3 2 5 出栈 3 32 做 2 5 结果入栈 s1 96 做 3 32 结果入 s1 96 入栈 s2 5 96 5 5 入栈 s1 结束符 91 做 96 5 结果入 s1 表 2 2 2 为了处理方便 编译程序常把中缀表达式首先转换成等价的后缀表达式 后缀表达式的运算符在运算对象之后 在后缀表达式中 不再引入括号 所有 的计算按运算符出现的顺序 严格从左向右进行 而不再考虑运算规则和级别 中缀表达式 3 2 4 2 2 1 3 5 的后缀表达式为 32422 13 5 2 后缀表达式求值 计算一个后缀表达式 算法上比计算一个中缀表达式简单得多 因为表达 C 程序设计课程设计报告 9 式中即无括号又无优先级的约束 具体做法只使用一个对象栈 当从左向右扫 描表达式时 每遇到一个操作数就送入栈中保存 每遇到一个运算符就从栈中 取出两个操作数进行当前的计算 然后把结果再入栈 直到整个表达式结束 这时送入栈顶的值就是结果 3 中缀表达式转换成后缀表达式 将中缀表达式转换为后缀表达式和前述对中缀表达式求值的方法完全类似 但只需要运算符栈 遇到运算对象时直接放后缀表达式的存储区 假设中缀表 达式本身合法且在字符数组 A 中 转换后的后缀表达式存储在字符数组 B 中 具体做法 遇到运算对象顺序向存储后缀表达式的 B 数组中存放 遇到运算符 时类似于中缀表达式求值时对运算符的处理过程 但运算符出栈后不是进行相 应的运算 而是将其送入 B 中存放 2 5 代码说明代码说明 栈的储存结构 typedef struct 运算符栈 char base char top int stacksize SqStack1 typedef struct 运算数栈 float base float top int stacksize SqStack2 以下是运算符栈的基本操作函数 Status InitStack SqStack1 if S base exit OVERFLOW S top S base S stacksize STACK INIT SIZE return OK InitStack Status DestroyStack SqStack1 free S base return OK DestroyStack char GetTop SqStack1 S 若栈不空 则返回 S 的栈顶元素 并返回 OK 否则返回 ERROR if S top S base return ERROR return S top 1 Gettop Status Push SqStack1 if S base exit OVERFLOW S top S base S stacksize S stacksize STACKINCREMENT S top e return OK Push Status Pop SqStack1 e S top return OK Pop 以下是运算数栈的基本操作函数 Status InitStack SqStack2 if S base exit OVERFLOW S top S base S stacksize STACK INIT SIZE return OK InitStack Status DestroyStack SqStack2 free S base return OK DestroyStack float GetTop SqStack2 S 若栈不空 则返回 S 的栈顶元素 并返回 OK 否则返回 ERROR if S top S base return ERROR return S top 1 Gettop Status Push SqStack2 if S base exit OVERFLOW S top S base S stacksize S stacksize STACKINCREMENT S top e return OK Push Status Pop SqStack2 e S top return OK Pop 以下是相关的运算符判断函数 char Precede char A char B 比较运算符 A B 的优先关系 A B 的范围仅限于 返回 case return case return case return case return case return case return default cout 表达式错误 endl exit 0 C 程序设计课程设计报告 14 的判断同 Status InOP char c 判断 c 是否是运算符 是则返回 TRUE 否则返回 FALSE switch c case return TRUE case return TRUE case return TRUE case return TRUE case return TRUE case return TRUE case return TRUE case return TRUE default return FALSE InOP float Operate float a char theta float b switch theta case return a b case return a b case return a b case if b 0 cout 分母不能为 0 endl exit 0 C 程序设计课程设计报告 15 else return a b case if a 0 exit 0 else return float pow a b default cout 表达式错误 c while c GetTop OPTR cc 0 flag 0 ii 10 if c prec c cin c 若某 前面是 第一个符号就是 或 则此为负号 不 是减号 else if InOP c while InOP c if c 48 小数点之前 else if flag 1 cc cc c 48 ii ii 10 小数点之后 else C 程序设计课程设计报告 17 cout 小数点错误 endl exit 0 小数点有错 else if c flag 读到小数点 else cout 表达式错误 c c
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 大学生中秋节活动策划书集锦11篇
- 单级圆柱齿轮减速器设计答辩
- 产品设计功能分析法设计法
- 完全随机化试验设计
- 创新创业设计产品化妆品
- 优化设计管理办法
- 垃圾桶设计案例分析报告
- 大学生饮品市场调查报告总结
- 安全人机工程设计案例分析报告
- 2024氢气长管拖车安全使用技术规范
- 赖氨酸生产装置二级种子罐工艺及设备设计
- 2022年学前儿童心理卫生与辅导
- 西方管理思想史郭咸纲第三版
- 上海通用汽车2010
- 《三角形的内角和》优质课一等奖课件
- 矿井反风演习实施计划及安全技术措施
- 工程勘察设计收费标准(2002版)
- 41简单快速学会金口诀应期
- 巨人通力电梯调试全参数(精)
- 道路工程质量通病防治措施
- 康熙字典各字五行属性
评论
0/150
提交评论