数据结构课程设计—十进制四则运算计算器的设计与实现.docx

十进制四则运算计算器的设计与实现问题描述（1）题目描述：在以二叉树表示算术表达式的基础上，设计一个十进制的四则运算计算器。（2）基本要求：实现整数或浮点数的四则运算。（3）测试数据：12 - ( - 4 ) * ( ( 20 + 3 / 5 ) * 8 / 5 ) * ( - 4 ) #=-515.36- ( 22.7 - 4208.3 ) / ( ( 2.4 + 1.6 ) * 12 ) + 4.4 - 2.9 #=88.710 - ( - 3 ) * ( ( 21 + 3 / 5 ) * 8 / 3 ) * ( - 2 ) #=-335.6需求分析（1）程序实现的功能是从键盘输入有效的表达式，求出其值并输出（2）程序运行后，会提示用户输入表达式，并判断是否有效，并返回值概要设计为了实现程序功能，用二叉树存储表达式，然后从二叉树按后序遍历的方式取出数据，进行运算，运算时用堆栈存储数据。二叉链表的定义ADT BinaryTree{ //数据对象D：D是具有相同特性的数据元素的集合。 //数据关系R： // 若D=Φ，则R=Φ，称BinaryTree为空二叉树； // 若D≠Φ，则R={H}，H是如下二元关系； // （1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱； // （2）若D-{root}≠Φ，则存在D-{root}={D1,Dr}，且D1∩Dr =Φ； // （3）若D1≠Φ，则D1中存在惟一的元素x1，root,x1∈H，且存在D1上的关系H1 ?H；若Dr≠Φ，则Dr中存在惟一的元素xr，root,xr∈H，且存在上的关系Hr ?H；H={root,x1,root,xr,H1,Hr}； // （4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。 //基本操作： InitBiTree( T ) //操作结果：构造空二叉树T。DestroyBiTree( T ) // 初始条件：二叉树T已存在。 // 操作结果：销毁二叉树T。 CreateBiTree( T, definition ) // 初始条件：definition给出二叉树T的定义。 // 操作结果：按definiton构造二叉树T。 ClearBiTree( T ) // 初始条件：二叉树T存在。 // 操作结果：将二叉树T清为空树。 BiTreeEmpty( T ) // 初始条件：二叉树T存在。 // 操作结果：若T为空二叉树，则返回TRUE，否则返回FALSE。 BiTreeDepth( T ) // 初始条件：二叉树T存在。 // 操作结果：返回T的深度。 Root( T ) // 初始条件：二叉树T存在。 // 操作结果：返回T的根。 Value( T, e ) // 初始条件：二叉树T存在，e是T中某个结点。 // 操作结果：返回e的值。 Assign( T, e, value ) // 初始条件：二叉树T存在，e是T中某个结点。 // 操作结果：结点e赋值为value。 Parent( T, e ) // 初始条件：二叉树T存在，e是T中某个结点。 // 操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。 LeftChild( T, e ) // 初始条件：二叉树T存在，e是T中某个结点。 // 操作结果：返回e的左孩子。若e无左孩子，则返回“空”。 RightChild( T, e ) // 初始条件：二叉树T存在，e是T中某个结点。 // 操作结果：返回e的右孩子。若e无右孩子，则返回“空”。 LeftSibling( T, e ) // 初始条件：二叉树T存在，e是T中某个结点。 // 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”。 RightSibling( T, e ) // 初始条件：二叉树T存在，e是T中某个结点。 // 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。 InsertChild( T, p, LR, c ) // 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。 // 操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点的原有左或右子树则成为c的右子树。 D