四则运算二叉树

数据结构 课程设计报告 设计题目：十进制四则运算计算器 实习目的 通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编 码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作 方法，为进一步的应用开发打好基础。 二问题描述 在以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。设 计要求实现整数浮点数的四则运算。 三需求分析 该程序实现的是实数型的四则运算，并在此运算上又加入了幂”运算，该程序用一二 叉树表示整个输入的算术表达式: (1)实现对结点的打印，便于结果分析； (2)实现对结点的统计； (3)实现中间结果的显示，可以看打印的结点，验证运算结果的正确与否。 四概要设计 系统用到的抽象数据类型定义： 2 1ADT node_type 数据对象 V：一个集合，该集合中的所有元素具有相同的特性 数据关系 R：R=VR VR=|P(x,y)(x,y 属于 V) 基本操作： （1）node_type(string k)； 操作结果：对结点进行初始化 ADT node_type 2ADT binary_tree 数据对象 D：一个集合，该集合中的所有元素具有相同的特性 数据关系 R：若 D 为空，则为空树。若 D 中仅含有一个数据元素，则 R 为空集， 否则 R=H，H 为如下二元关系： （1）在 D 中存在唯一的称为根的数据元素 root，它在关 系 H 中没有前驱 （2）除 root 以外，D 中每个结点在关系 H 下有且仅有一 个前驱。 基本操作： （1）print(node_type *r)CopyTimeTree(p,q)； 操作结果：对结点进行打印 （2）evaluate(node_type *prt)； 操作结果：对一二叉树进行计算 （3）counter()； 操作结果：计算一棵二叉树中的结点个数 ADT binary_tree 系统中子程序及功能要求： 1.ADT node_type build_node(string x)：建立一个结点 2.addition(char OperatorA,char OperatorB):判断两操作符是 否相等,若相等返回 True 3.TakesPrecedence(char OperatorA,char OperatorB):判别符号的 优先级。AB，返回为 TRUE 4.copy(ADT node_type * / bool IsOperator(string mystring) /验证操作符 if(mystring=“- “|mystring=“+“|mystring=“/“|mystring=“*“|mystring=“) return(true); 3 else return(false); bool IsOperator(char ops)/重载 if(ops=+|ops=-|ops=*|ops=/|ops=|ops=(|ops=) return(true); else return(false); bool IsOperand(char ch)/验证数据 if(ch=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=“/“) num=num1/num2; else if(prt-data=“) num=pow(num1,num2); coutdata=suzzy; prt-left_child=NULL; prt-right_child=NULL; else if(prt-left_child=NULL else evaluate(prt-left_child); evaluate(prt-right_child); evaluate(prt); void clear_help(node_type *rt) if(rt!=NULL) clear_help(rt-left_child); clear_help(rt-right_child); delete rt; void clear() /删除整个二叉树。 clear_help(root); / void count_help(node_type *rt,int int f1,f2; if(rt!=NULL) 5 count_help(rt-left_child,f1); count_help(rt-right_child,f2); a=f1+f2+1; int counter() /返回结点的个数 int a; count_help(root,a); return a; ; /二叉树类结束。 node_type *build_node(string x) /建立一个 结点 node_type *new_node; new_node=new node_type(x); return(new_node); void binary_tree:print(node_type *p)/打印 if(p!=NULL) print(p-left_child); print(p-right_child); coutdataB，返回为 TRUE。 if(OperatorA=() return false; else if(OperatorB=() return false; 6 else if(OperatorB=) return true; else if(addition(OperatorA,OperatorB) return false; else if(OperatorA=) return true; else if(OperatorB=) return false; else if(OperatorA=*)|(OperatorA=/) return true; else if(OperatorB=*)|(OperatorB=/) return false; else if(OperatorA=+)|(OperatorA=-) return true; else return false; void copy(node_type * else r1=build_node(r2-data); copy(r1-left_child,r2-left_child); copy(r1-right_child,r2-right_child); #endif /条件编绎结束 /calc.cpp/ #include #include #include #include “Tree.h“ #include bool isok(string exp) /此函数验证式子是否正确，即是否符合运算规则。 char check; int error=0; int lb=0; int rb=0; if(exp.size()=1 else if(IsOperator(exp0) 7 for(int m=0;mNodeStack; stackOpStack; string infix; char choice=y; system(“cls“); coutinfix; coutright_child=temp_tree.root; temp_tree.root=NULL; copy(temp_tree.root,NodeStack.top().root); etree.root- left_child=temp_tree.root; NodeStack.pop(); 10 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(infixi+1=-) binary_tree temp; temp.root=build_node(“0“); NodeStack.push(temp); OpStack.push(-); +i; else if(c=) while(OpStack.top()!=() binary_tree 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; 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); 11 etree.root=NULL; OpStack.pop(); while(!OpStack.empty() binary_tree 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; 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); if(!OpStack.empty() etree.root=NULL; coutdata: “; cinchoice; else cout: “; cinchoice; 12 return 0; 六测试分析（运行结果） 第一个表达式:10-（-3）*（21+3/5）*8/3）*（-2） ） 第二个表达式：-（32.7-3210.3）/(8.0+0.9)*8.9)+4.4 依次把运算符和操作数放入堆栈中，过程中依次把中间运算结果打印出来 最后显示出结果。(详细请看附录，这里不再一一详述。) 七总结（收获及体会） 此次课程设计收获颇多，总结起来有以下同点： 1.在小组的分工上，一定得合理安排，否则会造成工期的延迟，效率的降 低； 2.尽量利用系统定义的函数，尤其 C+面向对象的编程中，系统已经定义 了很多类，比如这次设计中使用到的 stack 类（堆栈类） ，这样就不用自己再定 义，减少了开发时间，提高了运行效率； 3.程序中用到了相当多的 IF-ELSE 的语句嵌套，使用时应注意语句的缩进 及括号的配对; 4程序的主函数中写得过程过多冗余，看上去有点不太清爽，这是应该提 高的一些地方。