数据结构实验二——算术表达式求值实验报告

《数据结构实验二——算术表达式求值实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、0b6aed190979e624d420a2aa77163aa5.doc《数据结构与数据库》实验报告实验题目算术表达式求值学院：化学与材料科学学院专业班级：09级材料科学与工程系PB0920603姓名：李维谷学号：PB09206285邮箱：liwg@mail.ustc.edu.cn指导教师：贾伯琪实验时间：2010年10月10日一、需要分析问题描述：第33页共33页0b6aed190979e624d420a2aa77163aa5.doc表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式

2、结合栈的应用实现对算术表达式进行四则混合运算。问题分析：在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。算法规定：输入形式：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实

3、验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。测试数据：正确输入：12*（3.6/3+4^2-1）#输出结果：194.4第33页共33页0b6aed190979e624d420a2aa77163aa5.doc无定义运算：12*（3.6/（2^2-4）+1）#输出结果：表达式出错，除数为0，无意义错误输入：12+s#输出结果：ERROR！一、概

4、要设计拟采用两种类型的展分别对操作数和操作符进行操作。程序中将涉及下列两个抽象数据类型：1、设定“操作数”的栈的抽象数据类型定义：ADTSqStack_f{数据对象：D={数据关系：R1={<>

5、,,i=2,…，n}约定端为栈顶，端为栈底。基本操作：InitStack_f(&S)操作结果：构造一个空栈S。GetTop_f(&S,&e)初始条件：栈S已存在。操作结果：用e返回S的栈顶元素。Push_f(&S，ch)初始条件：栈S已存在。操作结果：插入元素ch为新的栈顶元素。Pop_f(&S,&e)第33页共33页0b6aed190979e624d420a2aa77163aa5.doc初始

6、条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。}ADTSqStack_f2、设定“操作符”的栈的抽象数据类型定义：ADTSqStack_c{数据对象：D={数据关系：R1={<>

7、,,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返回其值。}ADTSqStack_c

8、3、本程序包含六个模块第33页共33页0b6aed190979e624d420a2aa77163aa5.doc1）主程序模块voidmain(){初始化；while(命令==“继续”){接受数据；处理数据；接受命令；｝｝2）栈模块——实现栈抽象数据类型3）判断运算符优先级模块——判断运算符的优先级别4）后缀表达式转换模块——将中缀表达式转换为后缀表达式，方便操作5）无括号表示式求值运算模块——根据后缀表达式求值，并输出中间和最终结果6）运算结果输出模块——以正确形式输出表达式的值一、详细设计1、主程序中需要的全程量#defineTTACK_INIT_SIZE100//初始分配最大空间量

9、#defineSTACKINCREMENT10//（默认）增补空间量第33页共33页0b6aed190979e624d420a2aa77163aa5.doc2、结点类型、指针类型typedefstruct{float*base;//存储实型数据元素的一位数组float*top;//栈顶指针intstacksize;//栈数组容量}SqStack_f;//有序存储实型的顺序表类型typedefstruct{char*base;//存储字符数据元素