表达式求值实验报告分析.doc

淮 海 工 学 院 计算机工程学院 课程设计报告 设计名称： 数据结构课程设计 选题名称： 表达式求值 姓 名： 学 号： 专业班级： 系 （院）： 计算机工程学院 设计时间： 设计地点： 软件工程实验室、教室 指导教师评语： 签名： 年 月 日  1．课程设计目的 1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，[问题描述]一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。[基本要求]（1） 从键盘读入一个合法的算术表达式，输出正确的结果。（2） 显示输入序列和栈的变化过程。SqStack_f{ 数据对象：D={ 数据关系：R1={|,,i=2,…，n} 约定端为栈顶，端为栈底。 基本操作： InitStack_f(S) 操作结果：构造一个空栈S。 GetTop_f(S,e) 初始条件：栈S已存在。 操作结果：用e返回S的栈顶元素。 Push_f(S，ch) 初始条件：栈S已存在。 操作结果：插入元素ch为新的栈顶元素。 Pop_f(S,e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。 }ADT SqStack_f 2、设定“操作符”的栈的抽象数据类型定义： ADT SqStack_c{ 数据对象：D={ 数据关系：R1={|,,i=2,…，n} 约定端为栈顶，端为栈底。 基本操作： InitStack_c(S) 操作结果：构造一个空栈S。 GetTop_c(S,e) 初始条件：栈S已存在。 操作结果：用e返回S的栈顶元素。 Push_c(S，ch) 初始条件：栈S已存在。 操作结果：插入元素ch为新的栈顶元素。 Pop_c(S,e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。 }ADT SqStack_c 3、本程序包含六个模块 1）主程序模块 void main( ) { 初始化； while(命令==“继续”) { 接受数据； 处理数据； 接受命令； ｝ ｝ 2）栈模块——实现栈抽象数据类型 3）判断运算符优先级模块——判断运算符的优先级别 4）后缀表达式转换模块——将中缀表达式转换为后缀表达式，方便操作 5）无括号表示式求值运算模块——根据后缀表达式求值，并输出中间和最终结果 6）运算结果输出模块——以正确形式输出表达式的值 三 详细设计 1、主程序中需要的全程量 #define TTACK_INIT_SIZE 100 //初始分配最大空间量 #define STACKINCREMENT 10 //（默认）增补空间量 2、结点类型、指针类型 typedef struct{ float *base; //存储实型数据元素的一位数组 float *top; //栈顶指针 int stacksize; //栈数组容量 }SqStack_f; //有序存储实型的顺序表类型 typedef struct{ char *base; //存储字符数据元素的一位数组 char *top; //栈顶指针 int stacksize; //栈数组容量 }SqStack_c; //有序存储字符型的顺序表类型 void InitStack_f(SqStack_f *s) void