数据结构课程设计报告--利用线性表进行算式计算.doc

数据结构课程设计报告 班 级： 计算机0801 姓 名： 学 号： 完 成 日 期： 2010 . 7 . 9 利用线性表进行算式计算 一：问题描述： 在计算机中，算术表达式由常量、变量、运算符号和括号组成，由于不同的运算符具有不同的优先级，又要考虑到括号，因此，算术表达式的求值不可能严格地从左往右进行，因而在程序设计时，借助栈实现。 算法要点：设置运算符栈和运算数队列辅助分析算符优先关系，在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。 二：需求分析 1、输入的形式和输入值的范围 一个算术表达式，由常量、变量、运算符和括号组成（以字符串的形式输入）。为简化，规定操作数只能为整数，操作符为“+”、“-”、“*”、“/”、“%”，用“#”开始且用“#”结束，优先级为：括号--%--*,/--+,-。 2、输出的形式 即输出表达式运算结果，本算法中输出的形式为The end is：..... 3、程序所能达到的功能 界面上出现一个文本框，输入一个表达式（以“#”开始并以“#”结束，此表达式包括“+”、“-”、“*”、“/”、“%”、括号以及整数），点击回车，显示结果。 4、测试结果 正确的输入一个表达式是指输入一个正确的表达式即不能连续输入两个运算符（括号除外），切以“#”开始以“#”结束，点击回车界面上出现The end is：……即此表达式的结果。 输入表达式错误有两种形式： （1）、所输入的表达式未以“#”开始则点击回车，系统会提示“RROE!Please begin with #“，“且下面输出”Continue?(y/n):“，若输入Y或者y，则再次进入主界面输入表达式，若输入N或者n,则跳出系统。 （2）、所输入的表达式错误，即连续输入两个运算符，此时系统会提示“ERROE!Please input another time!“， 三：概要设计 主程序的流程图为 四：详细设计 1、本系统中所用到的抽象数据类型有栈的抽象数据类型以及队列的抽象数据类型。 栈的抽象数据类型定义： ADT Stack{ 数据对象：D={ai| ai ∈ElemSet,i=1,2,3……n,n≥0} 数据关系：R1={ ai-1, ai ∈D,i=2,3……n} 基本操作： InitStack（S） 操作结果：构造一个空栈 DestoryStack（S） 初始条件：栈S已存在。 操作结果：栈S被销毁。 ClearStack（S） 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmpty（S） 初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回TRUE,否则返回FALSE。 StackLength（S） 初始条件：栈S已存在。 操作结果：返回S的元素个数，即栈的长度。 GetTop（S，e） 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push（S，e） 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop（S，e） 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 StackTraverse（S，visit()） 初始条件：栈S已存在且非空。 操作结果：从栈底到栈顶一次对S的每个元素调用函数visit（）。一旦visit（）失败，则操作失败。 }ADT stack 队列的抽象数据类型定义： ADT Queue{ 数据对象：D={ai| ai ∈ElemSet,i=1,2,3……n,n≥0} 数据关系：R1={ ai-1, ai ∈D,i=2,3……n} 约定其中ai端为队列头，an端为队列尾 基本操作： InitQueue（Q） 操作结果：构造一个空队列Q。 DestoryQueue（Q） 初始条件：队列Q已存在。 操作结果：队列Q被销毁。 ClearQueue（Q） 初始条件：队列Q已存在。 操作结果：将Q清为空队列。 QueuekEmpty（Q） 初始条件：队列Q已存在。 操作结果：若队列Q为空栈，则返回TRUE,否则返回FALSE。 QueueLength（Q） 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。 GetHead（Q，e） 初始条件：队列Q已存在且非空。 操作结果：用e返回Q的队头元素。 EnQueue（Q，e） 初始条件：队列Q已存在。 操作结果：插入元素e为新的队尾元素。 DeQueue（Q，e） 初始条件：队列Q已存在且非空。 操作结果