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

十进制四则运算计算器的设计与实现1. 问题描述（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.62. 需求分析（1）程序实现的功能是从键盘输入有效的表达式，求出其值并输出（2）程序运行后，会提示用户输入表达式，并判断是否有效，并返回值3. 概要设计为了实现程序功能，用二叉树存储表达式，然后从二叉树按后序遍历的方式取出数据，进行运算，运算时用堆栈存储数据。（1） 二叉链表的定义ADT BinaryTree /数据对象D：D是具有相同特性的数据元素的集合。 /数据关系R： / 若D=，则R=，称BinaryTree为空二叉树； / 若D，则R=H，H是如下二元关系； / （1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱； / （2）若D-root，则存在D-root=D1,Dr，且D1Dr =； / （3）若D1，则D1中存在惟一的元素x1，H，且存在D1上的关系H1 ?H；若Dr，则Dr中存在惟一的元素xr，H，且存在上的关系Hr ?H；H=,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的右子树。 DeleteChild( T, p, LR ) / 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。 / 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。 PreOrderTraverse( T, visit() ) / 初始条件：二叉树T存在，Visit是对结点操作的应用函数。 / 操作结果：先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。 InOrderTraverse( T, visit() ) / 初始条件：二叉树T存在，Visit是对结点操作的应用函数。 / 操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。 PostOrderTraverse( T, visit() ) / 初始条件：二叉树T存在，Visit是对结点操作的应用函数。 / 操作结果：后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。 LevelOrderTraverse( T, visit() ) / 初始条件：二叉树T存在，Visit是对结点操作的应用函数。 / 操作结果：层次遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。 如果判断函数的返回值正确，则进行下面的步骤。ADT BinaryTree判断表达式主函数模块创建二叉树计算结果、输出（2） 本程序包含的模块 4. 详细设计(1) 二叉树的二叉链表类型定义typedef struct BitNodeElemType data;struct BitNode *Lchild,*Rchild;/二叉树的左右孩子和父母 BitNode；typedef BitNode *BitTree;(2) 树的结构定义class binarytree/树的类public:BinNode *root; /根节点binarytree(void)root=NULL; /构造函数void print(void)print(root);void print(BinNode *p)if(p!=NULL)print(p-left_child);print(p-right_child);coutdatadata)&!IsOperator(prt-left_child-data)&!IsOperator(prt-right_child-data)/计算二叉树结点的值并存入新的二叉树结点float num=0;float num1=atof(prt-left_child-data.c_str();float num2=atof(prt-right_child-data.c_str();if(prt-data=+)num=num1+num2;else if(prt-data=-)num=num1-num2;else if(prt-data=*)num=num1*num2;else if(prt-data=/)if(num2=0.0)coutdata=)num=pow(num1,num2);else if(prt-data=%)if(num2=0.0)cout除数为零!运算出错;return 0;elsenum=(long)num1%(long)num2;stringstream bob;bobdata=suzzy;prt-left_child=NULL;prt-right_child=NULL;else if(prt-left_child=NULL&prt-right_child=NULL);else evaluate(prt-left_child);evaluate(prt-right_child);evaluate(prt);return 1;void clear_help(void)clear_help(root);void clear_help(BinNode *rt)if(rt!=NULL)clear_help(rt-left_child);clear_help(rt-right_child);delete rt;判断表达式是否正确bool judge(string exp) /判断输入是否正确char check;int error=0,lb=0,rb=0,numofoperand=0,numofoperator=0;for(int m=0;m=0&expm-1=0&expm+1=9)error+;cout浮点型数据输入有误!lb)error+;cout右括号不可能大于左括号!endl;if(IsOperator(expm+1)&(expm+1=+|expm+1=-|expm+1=*|expm+1=/|expm+1=)numofoperator+;m+;if(expm=)rb+;else if(IsOperator(expm+1)|IsOperand(expm+1)error+;cout右括号后不可能直接跟数据或左括号!endl; else if(check=()lb+;if(IsOperator(expm+1)&expm+1=(|expm+1=-)/左括号右边只能是数字或者-号m+;m+;lb+;else if(IsOperator(expm+1)error+;cout左括号后运算符只能跟左括号!endl;else numofoperator+;if(IsOperator(expm+1)&expm+1=()m+;lb+;else if(IsOperator(expm+1)error+;cout非括号的运算符不能直接接非括号运算符!endl;elseerror+;coutcheck为非法字符!endl;if(error=0)&(lb=rb)&(numofoperand!=0)&(numofoperator!=0)return true;else return false;5. 调试分析（1） 程序将所有的二叉树的子树用binarytree进行创建子树，然后将子树的孩子结点和数据域进行计算，存入上一层树的孩子结点中，从而使算术比较节约时间。（2） 程序时空复杂度分析判断是否是合格字符的函数,所有用bool定义的函数的时间复杂度都是O(1)。构造二叉树binarytree（）时间复杂度为O(n) 。主函数main()是递归调用，时间复杂度为O(n) 。6. 使用说明程序运行后将提示输入一个有效的表达式并以“#”号结束，不要输入非数字和算符的字符，否则程序将报错退出。程序将判断输入的表达式是否合理，如果合理则进行创建二叉树，并且使用二叉树计算表达式的结果并输出。7. 测试第一组数据的计算结果！第二组数据的计算结果！第三组数据的计算结果！8. 遇到的问题及解决1. 首先是存储的问题：一开始想从左往右，依次将一个表达式存进去，但是最后发现只适用于单个表达式，不能通用，最后看到书上在二叉树的顺序存储结构中，将二叉树补满，其实每一个叶子结点也是一个孩子为空的双亲结点，于是就采用对每遇到的一个操作数或者操作符，创建子树，再将它作为孩子结点送给它的双亲结点。2. 在取出并且计算的过程中，我一开始的思路是“在二叉树中先序遍历，将数据和算符存在一个栈里面，然后判断是否有2个连续的数据，如果有，则进行计算，如果没有则继续压栈，直到二叉树遍历完后，栈中只剩下一个元素，即最后的计算结果”，但是发现栈中的元素都是一个类型，如果非要这样存，那就得设置一个指示符，判断取出的是算符，还是数据，这样设计起来有些麻烦。后来又采用的是彭波老师主编的数据结构教材，实验二的方法，采用堆栈进行计算，将从二叉树取出来的数据进行分类压栈，数据和算符分别压栈，判断优先权，最终计算出结果。再后来，我希望能从二叉树的叶子结点进行计算，然后在这个过程中修改二叉树的结构，将一个子树（双亲结点和其对应的叶子（2个孩子）结点）计算的结果存进上面双亲结点的孩子结点，从而在最终的到只有1个结点的二叉树，即最终计算结果。本程序是第二三中方式的结合，不过更偏向后者。9. 附录（带注释的源程序）#include #include #include #include #include using namespace std;bool IsOperator(string mystring) /判断字符串是否是运算符if(mystring = -|mystring = +|mystring = *|mystring = /)return true;else return false;bool IsOperator(char ops) /判断一个字符是否是运算符if(ops = +|ops= -|ops= *|ops= /|ops=(|ops=)return true;elsereturn false;bool IsOperand(char ch) /判断是否是数字if (ch=0)&(ch=9)|(ch=.)return true;elsereturn false;bool judge(string exp) /判断输入是否正确char check;int error=0,lb=0,rb=0,numofoperand=0,numofoperator=0;for(int m=0;m=0&expm-1=0&expm+1=9)error+;cout浮点型数据输入有误!lb)error+;cout右括号不可能大于左括号!endl;if(IsOperator(expm+1)&(expm+1=+|expm+1=-|expm+1=*|expm+1=/|expm+1=)numofoperator+;m+;if(expm=)rb+;else if(IsOperator(expm+1)|IsOperand(expm+1)error+;cout右括号后不可能直接跟数据或左括号!endl; else if(check=()lb+;if(IsOperator(expm+1)&expm+1=(|expm+1=-)/左括号右边只能是数字或者-号m+;m+;lb+;else if(IsOperator(expm+1)error+;cout左括号后运算符只能跟左括号!endl;else numofoperator+;if(IsOperator(expm+1)&expm+1=()m+;lb+;else if(IsOperator(expm+1)error+;cout非括号的运算符不能直接接非括号运算符!endl;elseerror+;coutcheck为非法字符!left_child);print(p-right_child);coutdatadata)&!IsOperator(prt-left_child-data)&!IsOperator(prt-right_child-data)/计算二叉树结点的值并存入新的二叉树结点float num=0;float num1=atof(prt-left_child-data.c_str();float num2=atof(prt-right_child-data.c_str();if(prt-data=+)num=num1+num2;else if(prt-data=-)num=num1-num2;else if(prt-data=*)num=num1*num2;else if(prt-data=/)if(num2=0.0)cout除数为零!运算出错;return 0;elsenum=num1/num2;stringstream bob;bobdata=suzzy;prt-left_child=NULL;prt-right_child=NULL;else if(prt-left_child=NULL&prt-right_child=NULL);else evaluate(prt-left_child);evaluate(prt-right_child);evaluate(prt);return 1;void clear_help(void)clear_help(root);void clear_help(BinNode *rt)if(rt!=NULL)clear_help(rt-left_child);clear_help(rt-right_child);delete rt;BinNode *build_node(string x)/创建一个临时结点BinNode *new_node;new_node=new BinNode(x);return (new_node);void copy(BinNode *&r1,BinNode* r2)/这里将单个的子树连接起来if(r2=NULL)r1=NULL;elser1=build_node(r2-data);copy(r1-left_child,r2-left_child);copy(r1-right_child,r2-right_child);/*int main()binarytree etree;/创建树stack NodeStack;/创建栈stack OpStack;string exp;/声明字符串char choice=y;/choice为选择是否继续运行程序的判断char c;/为下面创建二叉树进行取字符while(choice=y|choice=Y)cout请输入一个有效的表达式:endl;getline(cin,exp);cout endl-endl;if(judge(exp)/如果判断出表达式没有错误，则进行创建二叉树并计算cout表达式格式正确endl;for(int i=0;iexp.size();i+)c=expi;if(i=0 & c=-) /若开始为负，则把零压入运算数栈，把-压入运算符栈binarytree temp; temp.root=build_node(0); NodeStack.push(temp); OpStack.push(-); elseif(IsOperand(c)/若是操作数，则判断下一位是不是操作数，并且将整个数据创建一个子树并压栈string tempstring=;tempstring=tempstring+c;while(i+1right_child=temp_tree.root;/将临时结点放入新建子树的右孩子结点上，可以将个子树连接起来temp_tree.root=NULL;/置空临时树结点copy(temp_tree.root,NodeStack.top().root);/重复上面的步骤连接左孩子etree.root-left_child=temp_tree.root;NodeStack.pop();temp_tree.root=NULL;copy(temp_tree.root,etree.root);NodeStack.push(temp_tree);etree.root=NULL;OpStack.push(c);else if(c=() /若中间遇到括号，则判断下一位是否为-OpStack.push(c);if(expi+1=-)binarytree temp;temp.root=build_node(0); NodeStack.push(temp);OpStack.push(-);i+; else if(c=)/如果遇到右括号，则创建子树，直到与左括号匹配成功，这里和前一步骤的操作基本相同while(OpStack.top()!=()binarytree temp_tree;string thisstring=;thisstring=thisstring+OpStack.top();OpStack.pop();etree.root=build_node(thisstring);copy(temp_tree.root,NodeStack.top().root);NodeStack.pop();etree.root-right_child=temp_tree.root;temp_tree.root=NULL