数据结构实验四：四则运算表达式概要.doc

HUNAN UNIVERSITY 课程实验报告 题 目： 四则运算 学生姓名 学生学号 专业班级 指导老师 李 晓 鸿 完 成 日 期 2 0 1 5年 12 月 10日 一、需求分析 1．程序的功能 本程序要求首先输入一组数据进行四则运算，输入的数据是按照中缀表达式的结构输入的，完成初始化后，把中缀表达式用后缀表达式(逆波兰表达式)输出，同时输出计算结果。 输入的形式 输入一个平时所用的正常的四则运算表达式（不需要特别注意输入式子是否正确），输入的数字的范围是（0至2^16）的小数或者整数,输入的符号限于（+-*/^） 输出的形式 程序的输出就是转化后的后缀表达式以及计算的结果，输出结果间用空格隔开； 测试数据 ①正常的输入 输入 21+23*（12-6） 输出 后续表达式为 21 23 12 6 - * + 计算结果为 159 ②输入有两个符号的错误情况 输入 6*3++4*（14-8） 输出 非括号运算符不能直接接非括号运算符 ERROR ③输入有小数的情况 输入 2.0*(11.2-5.3)+2.5 后续表达式为 2.0 11.2 5.3 - * 2.5 + 计算结果为 14.3 ④有整数小数的情况 输入 2/（3.0+5）*3 输出 后续表达式为 2 3.0 5 + / 3 * 计算结果为0.75 ⑤错误的输入 输入 2a+3 输出 a为非法字符 error 二、概要设计 1.抽象数据类型 本题目中，首先需要按顺序读取数字和操作符，将它们分别保存到两个数据结构中，如果最先保存的操作符优先级不大于接下来保存的操作符，将一直不被调用直到上一级操作符被调用，满足先进后出的数据结构，所以用栈来保存操作符。 对于保存的数字，每次调用操作符时，同时将最后保存的两位数字调用，满足先进后出的数据结构，所以用栈来保存数字。 由于需要用后缀表达式输出，按照进栈出栈的顺序，我们将符号作为节点，数字作为左右子树，依次相连成为一颗二叉树，通过后续遍历将二叉树输出。 算法的基本思想 ①．本题目在之后的操作中需要将数字和操作符进入不同的栈，所以我们在程序设计之前需要先设计函数判断读取的字符是数字还是操作符。 ②.本题中需要设计函数对操作符的优先级进行比较，即‘）’的优先级大于‘*’‘/’的优先级大于‘+’‘-’的优先级大于‘（’的优先级。 ③．对输入的式子进行顺序扫描，依次将数字和操作符依次进栈，当操作符进栈且前一个元素不为空时进行判断，将要进栈的操作符I与上一个操作符进行优先级比较，上一个操作符优先级级别大于操作符I，则弹出上一个操作符，同时弹出两个操作数建立二叉树，操作符做根节点，将二叉树的的结点存进数字栈，操作符I进操作符栈;若上一个操作符优先级级别小于或等于操作符I，操作符I进操作符栈。 ④．当式子扫描完毕，对于操作符栈剩下的元素，一次出栈，同时数字栈出两个元素，操作符作为结点，两个元素作为左右子树，再将节点存进数字栈，重复以上操作，知道操作符栈中没有元素。 ⑤．当操作符栈中没有元素，此时已经建好了一棵二叉树，我们通过后续遍历输出二叉树，同时进行计算。输出遍历二叉树每个结点的值，输出计算结果。 3．ADT ADT BinNode 数据对象：包含结点的值，同时包含结点的左右指针 数据关系：每个结点都有各自的值 若结点左右指针为空，则该节点称为叶子结点 基本操作： int val() //返回结点的数值 Void setVal（const Elem）//设置节点的值 inline BinNode* left()const //获取左结点 inline BinNode* right()const //获取右结点 void setLeft(Node* it) //设置左结点 void setRight(Node* it) //设置右结点 Bool isLeaf（） //判断叶子结点 ADT BinTree 数据对象D：D是BinNode类的数据元素的集合 数据关系R： 若D为空集，则称为