1、 课程设计(论文) 题 目 名 称 表达式求值问题 课 程 名 称 数据结构课程设计 学 生 姓 名 XXX 学 号 xxxxxxxxx 系 、专 业 信息工程系、信息工程类 指 导 教 师 xxxxxx 2010 年 1 月 3 日 1 目 录 1 问题描述 . 2 2 需求分析 . 2 3 概要设计 . 2 31 抽象数据类型定义 2 32 模块划分 . 3 4 详细设计 . 4 41 数据类型的定义 4 42 主要模块的算法描述 4 5 测试分析 . 7 51 程序运行结果 7 52 程序调试与体会.8 6 课程设计总结 8 参考文献 . 8 附录（源程序清单） 9 2 1 问题描述 编
2、写一个表达式求值程序，使输入一个四则运算表达式后，能够返回正确 的结果。该表达式由数字09、+、-、*、/、括号组成，且表达式必须正确 无误。程序的编写可用到栈或队列的基本算法，求出该表达式的值，并分析算法 的时间复杂度和运算的结果。 2 需求分析 （1）为实现算符优先算法,可以使用两个工作栈。一个称做OPTR，用以 寄存运算符;另一个称做OPND;用以寄存操作数或运算结果。算法的基本思想 是： 首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素; 依次读入表达式中每个字符,若是操作数则OPND栈,若是运算符,则和 OPTR栈的栈顶运算符比较优先权后做相应操作,直至整个表达式求值完毕
3、(即 OPTR栈的栈顶元素和当前读入的字符均为“#“)。 （2）该程序实现表达式的求值问题： 从键盘读入一个合法的算术表达式，利用算符优先关系，实现对算术四则 混合运算的求值，输出正确的结果。 3 概要设计 31 抽象数据类型定义 设定栈抽象数据类型的定义采用两个栈的入栈与出栈的操作来进行 “运算符 和操作数的配对” 。程序中主要用到以下抽象数据类型： 1）ADT Stack 数据对象：D ai | ai ElemSet, i=2,.,n, n0 数据关系：R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作： （1）InitStack( struct
4、 sqstack elmtype stackMAXSIZE; int top; ; （2）运算符号类型 char ch7=+,-,*,/,(,),#; （3）运算符号优先级类型 int f17=3,3,5,5,1,6,0;/*栈内元素优先级*/ int f27=2,2,4,4,6,1,0;/*栈外元素优先级*/ 42 主要模块的算法描述 该程序主要由主函数模块、表达式求值模块、表达式转换模块三个个部分组 成。 （1）主函数及表达式求值模块 void main() int result; result=EvaluateExpression(); /*对EvaluateExpression()进行
5、调用 */ （2）表达式求值模块 主 函 数 只 调 用了EvaluateExpression()函 数;而 其 他 的函 数 则 由 EvaluateExpression()调用了，因此使得主函数十分简洁明了。其中求值函数流 程图如下： 5 图 4.2 表达式求值模块流程图 Y Y Y Y N N N N N Y 定义 char c C!=# isdigit(c) SUM=0 K ERROR! isdigit(c) 判断!j sum=sum*10-(c-0) sum=sum*10+(c-0) C=GetChar() Push( int top; st; 5 测试分析 51 程序运行结果： 7
6、 52 程序调试与体会 运用栈的基本操作顺利的解决表达式求值及转换问题， 主要利用栈的先进后 出结构，执行出栈进栈操作并在出栈时进行配对并输出配对情况，而整个过程不 需要不需要移动元素使程序在空间复杂度上降到最小， 采用指针的移动大大加快 了程序的执行效率。并且对输入进行了改进，以防止用户随意输入时出现的各种 意想不到的错误。系统整体上比较完美，无论是输入、输出，还是整个系统的界 面，都非常美观、简洁、大方 6 课程设计总结 通过这段时间的课程设计，本人对计算机的应用、数据结构的作用以及 C 语言的使用都有了更深的了解。在理论学习和上机实践的各个环节中，通过自主 学习和请教陈智、成娅辉老师，我收获了不少。当然也遇到不少问题，也正是因 为这些问题引发的思考给我带来了收获。 从当初不喜欢上机写程序到现在能主动
