数据结构课程设计报告十进制二叉树四则运算计算器设计与实现

1、成绩 中国农业大学课程设计报告书（2010-2011学年夏季学期）设计题目：十进制四则运算计算器设计与实现 课程名称： 数据结构 任课教师： 彭 波 班级： 试验092 学号： 0958020205 姓名： 曹 津 课程设计报告书格式要求（封皮的背面）：1. 课程设计报告书采用统一封面，以左侧为准装订成册。2. 课程设计报告书一律使用标准a4复印纸打印或使用标准a4复印纸手写稿形式上交。3. 课程设计报告书打印的格式要求：课程设计标题（使用隶书二号字体加黑；一级标题、二级标题分别使用黑体三号、四号字体加黑）正文（使用宋体小四号，行距20磅）算法代码及源程序代码（使用times new roma

2、n五号）十进制四则运算计算器设计与实现1. 问题描述（1） 题目要求：利用二叉树表示算术表达式的基础上，设计实现一个十进制的四则运算计算器。（2） 基本要求：由用户输入中缀四则运算表达式，由程序计算所输入四则运算表达式的结果并输出。（3） 测试数据：12 - ( - 4 ) * ( ( 20 + 3 / 5 ) * 8 / 5 ) * ( - 4 ) #- ( 22.7 - 4208.3 ) / ( ( 2.4 + 1.6 ) * 12 ) + 4.4 - 2.9 #10 - ( - 3 ) * ( ( 21 + 3 / 5 ) * 8 / 3 ) * ( - 2 ) # 运行结果：-515.

3、36 88.7 -335.62. 需求分析（1） 本程序用于求出用户输入的任意合法四则运算表达式的值。（2） 程序运行后显示提示信息，由用户输入任意四则运算表达式，倘若所输入的表达式不合法程序将报错。（3） 用户输入四则运算表达式完毕，程序将输出运算结果。（4） 测试用的表达式须是由+、-、*、/运算符，括号“(”、“)”与相应的运算数组成。运算数可以是无符号浮点型或整型，范围在065535。3. 概要设计为了实现上述程序功能，应以字符串表示用户输入的表达式，进而将用户输入的表达式转化为二叉树形式存储供计算的类型。期间还须用到堆栈数据类型。（1） 二叉树的抽象数据类型定义adt binaryt

4、ree 数据对象：表达式运算数 num | 0 num 65535 表达式运算符 opr | + , - , * , / 数据关系：由一个根结点和两棵互不相交的左右子树构成，且树中结点具有层次关系。根结点必须为运算符，叶子结点必须为运算数。基本操作： initbitree(&t , &s) 初始条件：存在一四则运算前缀表达式s。 操作结果：根据前缀表达式s构造相应的二叉树t。 destroybitree(&t) 初始条件：二叉树t已经存在。 操作结果：销毁t。 value(&t) 初始条件：二叉树t已经存在。 操作结果：计算出t所表示的四则运算表达式的值并返回。adt binerytree（2

5、） 顺序栈的抽象数据类型定义adt stack 数据对象：具有相同类型及后进先出特性的数据元素集合。 数据关系：相邻数据元素具有前去和后继关系。 基本操作： initstack(&s) 初始条件：无 操作结果：构造一个空栈s。 destroystack(&s) 初始条件：栈s已经存在。 操作结果：销毁s。 stacklength(&s) 初始条件：栈s已经存在。 操作结果：返回s中元素个数。 gettop(s , &e) 初始条件：栈s已经存在且非空。 操作结果：用e返回s的栈顶元素。 push(&s , e) 初始条件：栈s已经存在。 操作结果：插入元素e为s的新栈顶元素。 pop(&s ,

6、 e) 初始条件：栈s已经存在且非空。 操作结果：删除s的栈顶元素，并用e返回其值。adt stack（3） 字符串的抽象数据类型定义adt string 数据对象：具有字符类型的数据元素集合。 数据关系：相邻数据元素具有前驱和后继关系。 基本操作： strlength(s) 初始条件：串s已经存在。 操作结果：返回s的元素个数。 strneg(s , f) 初始条件：串s已经存在且非空。 操作结果：求s的逆序并将结果保存在串f中。adt string（4） 本程序包含四个模块：主程序模块；二叉树单元模块（实现二叉树的抽象数据类型，包括结点和指针的定义）；顺序栈单元模块（实现顺序栈的抽象数据类

7、型，包含结点和指针的定义）；字符串单元模块(实现字符串的抽象数据类型)。四个模块之间调用关系如下： 4. 详细设计（1） 顺序栈类型。#define stack_size 100typedef struct char elemstack_size; int top;sqstack 基本操作实现的伪代码算法如下： void initstack (sqstack &s) /初始化顺序栈 s.elem=new elemtypestack_size; if(!s.elem) error(overflow!); s.top=-1; viod push (sqstack &s,char c) /顺序栈压栈

8、 if(s.top=(stack_size-1) error(stack overflow!); s.elem+s.top=c; elemtype pop (sqstack &s) /顺序栈出栈 if(s.top=-1) error(stack empty!); return s.elems.top-; int stacklength(sqstack &s) /求顺序栈长度 return (s.top+1); gettop(sqstack &s ,char e) /取栈顶元素 e=s.elemtop; （2） 字符串类型typedef struct /动态顺序串 char *ch; int l

9、ength;string基本操作实现的伪代码算法如下：int strlength(&s) /求串长 return s.length; void strneg(&s , &f) /求逆序串if(!s.length) error(“string empty!”); for(i=0 ; i=0 ; i-) /对输入串逆序扫描 if(str.chi=48&str.chi=precedence( gettop(s) ) ) push( s , str.chi ); break; else pop(s , e); output.chi=e; output.length+; if( str.chi=( )

10、/假如是左括号，栈中运算符逐个出栈并输出，直到遇到右括号。右括号出栈并丢弃。 while( gettop(s)!=) ) output.chi=pop(s); output.length+; while(s.top!=-1) /假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。 output.ch=output.ch-; output.ch=pop(s); return output;void creatbitree(&t , &s) /由中缀表达式生成表达式二叉树 string f; sqstack sq; /用以存放生成的二叉树结点 initstack(sq); f=convert(s

11、); /求得s的前缀表达式 for(i=f.length-1 ; i=0 ; i-) if( !isoperator(f.chi) ) t=new tnode; t-data=f.chi; t-lchild=null; t-rchild=null; push(sq , t) else t=new tnode; t-data=f.chi; t-lchild=pop( sq ); t-rchild=pop( sq ); push(sq , t); int calc(int a, char opr, int b) /计算 switch (opr) case +: return a + b; case

12、 -: return a - b; case *: return a * b; case /: return a / b; int value(tnode *t) if (t-lchild = null &t-rchild = null) return t-data; else return calc( value(t-lchild) , t-data , value(t-rchild) );（4） 主函数伪码算法。void main() face(); /输出界面及相关信息 do cout”please input an expression:”str; judgeexp(s); /判断输入

13、的表达式是否合法。 t=creatbitree(s);n=value(t); cout”the value of this expression is”nendl;coute; if(e=y) flag=1;else flag=0; while(flag) /main（5） 函数调用关系图。5. 调试分析（1） 程序中使用的字符串类型可直接引用c+自带的类型库，没必要自行定义。（2） 算法时间复杂度分析。对于由表达式字符串生成二叉树的操作，由于是对字符串顺序扫描根据扫描到当前字符的情况决定操作，以n代表输入的表达式字符串长度，则此算法时间复杂度为0(n)。对于二叉树求值操作，由结点数量决定时间

14、，n为结点个数，则其时间复杂度为o(n)。（3） 算法空间复杂度分析。构造两个顺序栈各需一个elemtype类型的stack_size为100的栈空间，空间复杂度为o(1)。各算法中使用的辅助空间均与元素个数无关，是为o(1)。6. 使用说明程序运行后用户根据提示输入要计算的四则运算表达式，整型数浮点数均可，注意不要带空格，尽量保证所输入的表达式是合法表达式。输入完毕后回车键确定，程序输出结果。7. 测试结果8. 附录（带注释的源程序）/*cstack.h*/#includeusing namespace std;#define stack_size 100typedef struct /字符

15、类型顺序栈 char elemstack_size; int top;cstackvoid initcstack(&s) /初始化顺序栈 s.elem=new charstack_size; if(!s.elem) error(overflow!); s.top=-1;void push_c(cstack &s , char e) /压栈 if( s.top=(stack_size-1) ) error(stack overflow!); s.elem+s.top=e;char pop_c(cstack &s) /出栈 if(s.top=-1) error(stack empty!); ret

16、urn s.elemtop-;char gettop(&s) /取栈顶元素 if(s.top=-1) error(stack empty!); return s.elemtop;int cstacklength(&s) /求栈中元素个数 return top+1;/*tstack.h*/#include#includetree.husing namespace std;#define stack_size 100typedef struct /二叉树结点类型顺序栈 tnode elemstack_size; int top;tstackvoid inittstack(&s) /初始化顺序栈 s

17、.elem=new charstack_size; if(!s.elem) error(overflow!); s.top=-1;void push_t(tstack &s , tnode t) /压栈 if( s.top=(stack_size-1) ) error(stack overflow!); s.elem+s.top=t;tnode pop_t(tstack &s) /出栈 if(s.top=-1) error(stack empty!); return s.elemtop-;/*string.h*/#includeusing namespace std;typedef struc

18、t /动态顺序串 char *ch; int len;stringsrting strneg(&str) /求逆序串 string f; for(i=0 ; ilength ; i+) f.chi = str.chstr.len-1-i; return fint strlen(&str) /求串长 int i; for(i=0 ; str.chi!=0 ; ) i+; return i;/*tree.h*/#include#includestring.h#includecstack.h#includetstack.husing namespace std;typedef struct /二叉树

19、结点 union data /数据域 char opr; /运算符 int opn; /运算数 struct tnode *lchid , *rchild; /指针域tnodetypedef tnode *bitree; /二叉树头结点int precedence(char opr) /判断运算符级别函数；其中* /的级别为2，+ -的级别为1； switch(opr) case+: case-: return 1; break; case*: case/: return 2; break; case(: case): case#: default: return 0; break; bool

20、 isoperator(char opr) /判断输入串中的字符是不是合法操作符 if(op=+|op=-|op=*|op=/) return true; else return false;string convert(string &str) /将一个中缀串转换为后缀串 int i; string output; /输出串 output.len=0; cstack s; initcstack(s); str.len=strlen(str); /求的输入的串长 for(i=str.len-1 ; i=0 ; i-) /对输入串逆序扫描 if(str.chi=48 & str.chi=prec

21、edence( gettop(s) ) ) push_c( s , str.chi ); break; else output.chstr.len-1-i=pop_c(s); output.len+; if( str.chi=( ) /假如是左括号，栈中运算符逐个出栈并输出 /直到遇到右括号。右括号出栈并丢弃。 while( gettop(s)!=) ) output.chstr.len-1-i=pop_c(s); output.len+; while(s.top!=-1) /假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。 output.ch+output.len-1=pop_c(s)

22、; return strneg(output); /输出output的逆序即为所求前缀表达式void creatbitree(&t , &str) /由中缀表达式生成表达式二叉树 string f; tstack s; /用以存放生成的二叉树结点 inittstack(s); f=convert(str); /求得s的前缀表达式 for(i=f.len-1 ; i=0 ; i-) if( !isoperator(f.chi) ) t=new tnode; t-data=f.chi; t-lchild=null; t-rchild=null; push_t(s , t) else t=new t

23、node; t-data=f.chi; t-lchild=pop_t( s ); t-rchild=pop_t( s ); push_t(s , t); int calc(int a, char opr, int b) /计算 switch (opr) case +: return a + b; case -: return a - b; case *: return a * b; case /: return a / b; int value(tnode *t) /求表达式二叉树的值 if (t-lchild = null &t-rchild = null) return t-data; e

24、lse return calc( value(t-lchild) , t-data , value(t-rchild) );/*judgeexp.h*/#include#includestring.h#includetree.husing namespace std;bool judegexp(string exp) /此函数验证式子是否正确，即是否符合运算规则。 char check; int error=0; int lb=0; int rb=0; if(strlen(exp)=1 & exp.ch0!=-) return false; else if( (isoperator(exp.c

25、h0)& exp.ch0!=- | isoperator( exp.chstrlen(exp)-1 ) ) & exp.ch0!=( & exp.chstrlen(exp)-1!=) ) /此处若不加，在遇到某些式子时，会出现非法操作。 return false; for(int m=0 ; mstrlen(exp) ; m+) check=exp.chm; if(m=0 & check=- & (isdigit(exp.ch1)!=0 | exp.ch1=( ) ) check=exp.ch+m; if( isoperand(check) ); /如果是数字，跳过，不管。 else if(isoperator(check) if( check=) ) rb+; if( isoperator(exp.chm+1)&(exp.chm+1=+|exp.chm+1=-|exp.chm+1=*|exp.chm+1=/|exp.chm+1=|