表达式求值概要.docx

目录 1、 前言 2、 需求分析 2.1主要任务 2.2主要功能 2.2.1功能需求 2.2.2功能分析 3、概要设计 3.1数据结构说明 3.2各模块设计说明 4、详细设计 4.1流程图 4.2各模块算法分析 4.3数据测试 5、测试与分析 5.1遇到的问题 5.2运行结果 5.3测试结果 6、心得体会 ? 附录：源代码 一、 前言 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同 的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。 算法输出：表达式运算结果。 算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算 二、 需求分析 2.1主要任务 以字符序列的形式从键盘输入不含变量的整数算术四则表达式（可以有小括号）； 检查表达式的正确性 将其转换为二叉树的存储表示； 通过后序遍历得到其后缀表达式序列，输出该序列； 利用后缀表达式进行求值运算，输出求值结果 如输入：3*(5+33)-16 二叉树如下： 后缀表达式序列为：3|5|33|+|*|16|-| 2.2主要功能 2.2.1功能需求 （1）、以字符序列的形式从键盘输入不含变量的整数算术四则表达式（可以有小括号）； （2）、检查表达式的正确性； （3）、将其转换为二叉树的存储表示； （4）、通过后序遍历得到其后缀表达式序列，输出该序列； （5）、利用后缀表达式进行求值运算，输出求值结果。 2.2.2功能分析 上述功能在代码编写时可采用以下的方式： （1）、字符序列形式输入表达式可用一个char型数组存储； （2）、正确性检测包括是否有非法字符的输入、是否遗漏括号或者数字； （3）、递归建立二叉树（数字与运算符的处理关系）； （4）、后序遍历并打印二叉树； （5）、利用后缀表达式递归输出结果。 三、 概要设计 哈夫曼树： 哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。只有度为0和2的结点的二叉树成为正则二叉树。哈夫曼树就是这样。根据二叉树的性质，一颗有n个叶子的哈夫曼树共有2n-1个叶子结点，可以用一个大小为2n-1的一维数组存放哈夫曼树的各个节点。由于每个结点同时还包括其双亲信息和孩子信息，所以用一个静态三叉链表来存储哈夫曼树。 哈夫曼树存储方式（示例） Weight Lchild Rchild parent 2 -1 -1 4 3 -1 -1 4 6 -1 -1 5 9 -1 -1 6 5 0 1 5 11 4 2 6 20 3 5 -1 C++代码部分： struct HNode//哈夫曼树结点 { int weight; int parent; int lchild; int rchild; }; 哈夫曼编码表： 对于确定的某段待编码字符，编码表的长度可以确定。为了做到待编码字符和编码的一一对应，我们采用结构数组，每条记录存储待编码字符和编码两部分。由于结构数组有其自身存储的优越性，比起定义一个哈夫曼编码表类更能直观地表示出字符与编码之间的一一对应的关系。 哈夫曼编码表 Codea code[] A 00 B 01 C 10 D 11 C++代码部分： struct HCode//哈夫曼编码表 { char ch; int code[120]; }; 频率记录表： 初始化列表采用结构数组存储方式。每条记录存储待编码字符a和字符出现频度b两个部分。其中第一条记录的b用来标记列表长度，方便后期使用初始化列表。 频率记录表 A B 3 A 1 B 4 C 2 C++代码部分： struct node//频率记录表 { char a; int b; }; 3.1、数据结构说明 1、数据结构定义 typedef struct BiThrNode{ double data; char op; BiThrNode *lchild, *rchild; } BiThrNode; data：存储数据； char：存储运算符+-*/或“X”，其中X表示此处存储的是数据，无运算符； BiThrNode *lchild, *rchild：指向左右孩子的指针。 2、各函数内的数据定义及作用 序号 数据名称 所属函数 功能描述 1 char shizi[MAX] main 存储输入的表达式 2 int len main 存储输入