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

数据结构实验二——算术表达式求值实验报告 . 《数据结构与数据库》 实验报告 实验题目 算术表达式求值 学 院：化学与材料科学学院 专业班级：09 级材料科学与工程系 PB0920603 姓 名：维谷 学 号：P 邮 箱：liwgmail.ustc.edu.cn 指导教师：贾伯琪 实验时间：2010 年 10 月 10 日 一、 需要分析 问题描述： . 数据结构实验二——算术表达式求值实验报告 . 表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个 典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通 过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算 符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左 到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读 入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数 值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈的栈顶数 据变化过程，最后得到运算结果。 算法规定： 输入形式：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形 式输入）。为使实验更完善，允许操作数为实数，操作符为 （、）、. （表示小数点）、 +、-、*、/ 、^ （表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输 出。 程序功能：对实数的加减乘除乘方运算能正确的运算出结果，并能正确对错误 输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12* （3.6/3+4^2-1 ）# 输出结果：194.4 . 数据结构实验二——算术表达式求值实验报告 . 无定义运算：12* （3.6/ （2^2-4 ）+1）# 输出结果：表达式出错，除数为 0，无意义 错误输入：12+s# 输出结果：ERROR ！ 二、 概要设计 拟采用两种类型的展分别对操作数和操作符进行操作。程序中将涉及下列两 个抽象数据类型： 1、设定“操作数”的栈的抽象数据类型定义： ADT SqStack_f{ 数据对象：D={ a a  R, i  N  } i i 数据关系：R1={ a , a | a , a  D ,i=2,…，n} i i 1 i 1 i