数据结构实验报告.doc

课程设计实验报告实验名称：表达式类型的实现编译环境：硬件:PC软件：VS2010问题描述 一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式Expression的操作。基本要求假设算术表达式Expression可以含有变量（az）、常量（09）和二元运算符（+，-，*，/，（乘幂）。实现以下操作。（1） ReadExpr(E)以字符序列的形式输入语法正确的前缀表示式并构造表达式E。（2） WriteExpr(E)用带括弧的前缀表示式输出表达式E。（3） Assign(V，c)实现对变量V的赋值(V=c)，变量的初值为0。（4） Value(E)对算术表达式E求值。（5） CompoundExpr(P，E1，E2)构造一个新的复合表达式(E1)P(E2)。选作内容：（1） 增加常数合并操作MergeConst(E)-合并表达式中E的所有常数运算。例如：表达式E=2+2*1-A进行合并常数的操作后，求得E=4-A （2）以表达式的原书写形式输入需求分析1以字符序列的形式输入语法正确的中缀表示式并构造表达式E。即要根据正确的前缀式建立一棵二叉树T。 2用带括弧的前缀表达式输出表达式E。即要求在前缀遍历二叉树的时候考虑运算符的优先级，在适当的位置输出括弧。3实现对变量V的赋值（Vc），变量的初值为0。那就在中缀遍历二叉树的过程中比较结点的值是否为V，找到V以后将c赋给V。4对算术表达式E求值。如果表达式中有变量的话，首先提示用户表达式中变量，建议先执行操作3（实现对变量V赋值），执行完后再回来执行表达式求值这一步骤。表达式求值利用递归，如果某个结点的值为运算符并且它的左右孩子结点的值为数据，那么就把（左孩子）（运算符）（右孩子）的结果赋给该结点。一层一层往上，最后只剩下一个根结点。此时根结点的值就是表达式E的值。5构造一个新的复合表达式（E1）P（E2）。只要先构造表达式E1的二叉树和E2的二叉树，然后利用P把这两棵二叉树连接起来构成一棵新的二叉树。6合并表达式E中所有常数运算。此原理类似于对表达式E求值，不同之处只在于该功能只对常数合并。概要设计1. 树的抽象数据类型定义:ADT Tree数据对象 D: D是具有相同特性的数据元素的集合。数据关系 R: 若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R=H,H是如下二元关系：(1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2) 若D-root,则存在D-root的一个划分D1,D2,Dm(m0),对任意jk(1=j,k=m)有DjDk = ，且对任意的i(1im),唯一存在数据元素XiDi，有H；(3) 对应于D-root的划分，H - 有唯一的一个划分H1,H2Hm(m0)，对任意jk(1=j,k=m)有DjDk = ，且对任意的i(1im)，Hi是Di上的二元关系，(Di,Hi)是一棵符合本定义的树，称为根的root的子树。基本操作: Double Expression (char *exp);功能： 算术表达式求值 double calculate (double opnd1,char op,double opnd2 ); 功能： 操作数四则运算 void push( char , char, double , ExpressionCalculateStack *); 功能：入栈 double pop ( char , ExpressionCalculateStack *); 功能：出栈 void GetNextNotation ( char *notation,char *exp); 功能：读下一个运算符或操作数 char GetTypeOfNotation( char *notation ); 功能：判定是运算符或是操作数int CompareOpPrior(char op2, char op1); 功能：运算符优先级别比较 BTNode *ReadExpr(char s,int i,int j)功能：读入表达式void WriteExpr(BTNode *b) 功能：/把输入的表达式转换为相应的二叉树，并以前缀表达式的形式输出char Seek(char s,int k)功能：判断是否有字母输入void CompoundExpr(char E1,char E2,char p)功能：复合表达式void Assign(char s,char i,char j)功能：对变量进行复制流程图：Mian函数对算术表达式求值查找式中的变量Seek以中缀方式输入表达式ReadExpr以前缀方式输出表达式WriteExpr对式中的变量进行复制Assign3菜单65412复合表达式对变量赋值，即执行步骤3NY是否有变量 常数合并程序清单：头文件（MyExpression.h）#include#include#include#include#include#define MaxSize 100typedef char ElemType;typedef struct node ElemType data; struct node *lchild; struct node *rchild;BTNode;#define MAX_EXP_LEN 128 /* 表达式最大长度 */#define MAX_NOTATION_NUM 32 /* 一个表达式中的最大算符个数 */#define MAX_NOTATION_LEN 20 /* 表达式中一个算符的最大字串长度 */#define NULL 0typedef struct stack /* 表达式计算堆栈 */ double OpdStackMAX_NOTATION_NUM; /* 操作数堆栈 */ char OpStackMAX_NOTATION_NUM; /* 运算符堆栈 */ int OpdStackTop, /* 操作数堆栈顶指针 */ OpStackTop; /* 运算符堆栈顶指针 */ ExpressionCalculateStack;#define OPND D /* 操作数类型标志 */#define OPTR R /* 运算符类型标志 */#define CONTINUE_READ_NEXT_NOTATION C /* 表达式扫描标志，继续扫描 */#define STOP_READ_NEXT_NOTATION S /* 表达式扫描标志，暂停扫描 */* 部分子函数声明如下 （主要是表达式求值函数）*/double Expression(char *exp); /* 算术表达式求值 */double calculate (double opnd1,char op,double opnd2 ); /* 操作数四则运算 */void push( char , char, double , ExpressionCalculateStack *); /* 入栈 */double pop ( char , ExpressionCalculateStack *); /* 出栈 */void GetNextNotation ( char *notation,char *exp); /* 读下一个运算符或操作数 */char GetTypeOfNotation( char *notation ); /* 判定是运算符或是操作数 */int CompareOpPrior(char op2, char op1); /* 运算符优先级别比较 */源代码文件（MyExpression.c）#includeMyExpression.h#includestdlib.hextern double Expression(char *oldexp) ;extern int CompareOpPrior(char op2, char op1);extern char GetTypeOfNotation( char *notation ) ;extern void GetNextNotation (char *notation,char *exp);extern double calculate(double opnd1,char op,double opnd2 );extern double pop(char type,ExpressionCalculateStack *s);extern void push(char type, char op,double opnd,ExpressionCalculateStack *s);BTNode *ReadExpr(char s,int i,int j) BTNode *p; int k,plus=0,posi; if(i=j) p=(BTNode *)malloc(sizeof(BTNode); p-data=si; p-lchild=NULL; p-rchild=NULL; return p; /以下是i!=j的情况if(i!=j) for(k=i;k=j;k+) if(sk=+|sk=-) plus+; posi=k; if(plus=0) for(k=i;kdata=sposi; p-lchild=ReadExpr(s,i,posi-1); p-rchild=ReadExpr(s,posi+1,j); return p;/ void WriteExpr(BTNode *b) /把输入的表达式转换为相应的二叉树，并以前缀表达式的形式输出if(b!=NULL) printf(%c,b-data);if(b-lchild!=NULL|b-rchild!=NULL) printf(); WriteExpr(b-lchild ); if(b-rchild!=NULL) printf(,); WriteExpr(b-rchild); printf();char Seek(char s,int k)/判断是否有字母输入 char a1=0; int i; for(i=0;i=A&si=a&si=z) return a0=1;void Assign(char s,char i,char j) for(int p=0;p=strlen(s)-1;p+) if(sp=i) sp=j;void CompoundExpr(char E1,char E2,char p)/复合表达式char NewEMaxSize,q1; int k=0,i; BTNode *bt1,*bt2,*T; if(p=+|p=-)/复合函数为+或-是应怎样复合 for( i=0;istrlen(E1);i+)NewEi=E1i;NewEstrlen(E1)=p;for( k=0;k=0&sk-1=0&sk+1=9) /判断是否为数字 /*FX=sk-1*sk+1; sk-1=FX;*/ sk-1=(sk-1-48)*(sk+1-48)+48; for(int i=k;i=0&sk-1=0&sk+1=9) sk-1=(sk-1-48)/(sk+1-48)+48; for(int i=k;i=0&sk-1=0&sk+1=9) sk-1=(sk-1-48)+(sk+1-48)+48; for(int i=k;i=0&sk-1=0&sk+1=9) sk-1=(sk-1-48)-(sk+1-48)+48; for(int i=k;istrlen(s);i+) si=si+2; printf(常数合并后为：%s,s);void MergeConst(char s)/常数合并 int i,j,n; for(i=0;istrlen(s);i+) if(si=*|si=/) Conbination(s,i); for(j=0;jstrlen(s);j+) if(sj=+|sj=-) Conbination(s,j); void main()double fx=0; BTNode *b; int i=0,j=0; char sMaxSize, yesORno,value,getvalue,GetDigitl=NULL,p,E17,E23,e1,e2; printf( nn 表达式类型实现的使用说明：nn); printf( 表达式暂时还不能进行括号操作，请不要输入括号，nn); printf( 数字的输入只能是一位数（0-9），字母的输入a-z或A-Znn); printf( 表达式输入时请按以下形式输入：A-S+Dnn); printf(*nn); printf( 1.输入表达式 2.输出表达式nn); printf( 3.对变量赋值 4.对表达式求值nn); printf( 5.复合表达式 6.常数合并nn); printf( 7.返回nn); printf(*nn); printf(请输入选择（1-7）); while(GetDigitl=getchar()!=7) switch(GetDigitl) case 1: printf(nn请以中缀表达式形式输入表达式，例如a+b*c/dnn); printf(你的输入);getchar(); gets(s); /以中缀表达式形式输入表达式 printf(n); printf(你输入的表达式为:%sn,s); b=ReadExpr(s,0,strlen(s)-1);printf(n请输入选择（1-7）n); break; case 2: printf(n对应的二叉树：);WriteExpr(b);printf(nn);printf(n请输入选择（1-7）n); break; case 3: while(yesORno=Seek(s,strlen(s)-1)=1)printf(表示式中有变量！n);getchar(); printf(需要赋值的变量：); value=getchar(); getchar(); printf(变量值：); getvalue=getchar(); Assign(s,value,getvalue); b=ReadExpr(s,0,strlen(s)-1); printf(n对应的二叉树：); WriteExpr(b);printf(n请输入选择（1-7）n); break; case 4: yesORno=Seek(s,strlen(s)-1); if(yesORno=1) printf(表达式中有未知变量，请选择3进行变量赋值n); else fx=Expression(s); /* 表达式求值 */ printf(n表达式的运算结果为: %f n,fx); printf(n请输入选择（1-7）n); break; case 5: printf(请从（+、-、*、/）中选择一个作为复合符号n);printf(你的选择是：);getchar();p=getchar();printf(n);printf(请输入要复合的第一个表达式：);getchar();gets(E1);printf(n);printf(请输入要复合的第二个表达式:);gets(E2);printf(n);CompoundExpr(E1,E2,p); printf(n请输入选择（1-7）n);break; case 6: MergeConst(s); printf(n请输入选择（1-7）n); break; /一下是表达式求值函数#includeMyExpression.hdouble Expression(char *oldexp) /表达式计算函数，输入的是表达式字符串 char notationMAX_NOTATION_LEN, / 存放当前符号扫描读入的符号 op1,op2, expMAX_EXP_LEN; / 存放当前操作表达式 char flag=CONTINUE_READ_NEXT_NOTATION; /判别是否继续扫描下去 int prior; /存放算符优先级别比较结果: op2op1 : 1 /op2=op1 : 0 double opnd1,opnd2; / 存放当前用于计算的2个操作数 ExpressionCalculateStack s; /定义堆栈s s.OpdStackTop=s.OpStackTop=0; strcpy(exp,oldexp); /把原表达式复制给当前操作表达式 strcat(exp,#); /把#接到exp后面，原exp最后面的0被取消 push(OPTR,#,0.0,&s); / 初始化表达式计算堆栈 while(1) if( flag=CONTINUE_READ_NEXT_NOTATION ) GetNextNotation (notation,exp); else /* 有运算结果进操作数栈后 */ flag=CONTINUE_READ_NEXT_NOTATION; if ( GetTypeOfNotation( notation )=OPND ) opnd2 = atof(notation); push(OPND,NULL,opnd2,&s); /操作数处理 else / 运算符处理 op2 = notation 0; op1 = (char) pop(OPTR,&s); / 运算符出栈 prior = CompareOpPrior(op2,op1); if ( prior 0 ) /op2 0 ) /op2 op2 opnd2 = pop(OPND,&s) ; opnd1 = pop(OPND,&s); opnd2 = calculate(opnd1,op1,opnd2 ); push( OPND, NULL,opnd2,&s); flag=STOP_READ_NEXT_NOTATION; /暂停读入下一个表达式符号 /使当前运算符与栈顶运算符再作一次比较 if(prior=0) /op2 = op1 的情况处理 if( op2=#)return pop(OPND,&s) ;/结束运算，将运算结果从堆栈中弹出 void push(char type, char op,double opnd,ExpressionCalculateStack *s) if(type=OPND) s-OpdStacks-OpdStackTop+= opnd; else s-OpStacks-OpStackTop+ = op;double pop(char type,ExpressionCalculateStack *s) if(type=OPND) / 是操作数栈 return s-OpdStack-s-OpdStackTop; else / 是运算符栈 return (double) (s-OpStack-s-OpStackTop);double calculate(double opnd1,char op,double opnd2 ) switch(op) case +: return opnd1+opnd2; case -: return opnd1-opnd2; case *: return opnd1*opnd2; case /: if( opnd2!=0.0) return opnd1/opnd2; else return 0.0; return 0.0;void GetNextNotation (char *notation,char *exp) / 读入下一个完整的符号:操作数或运算符 / 把一个完整的操作数或运算符保存到notation static int i=0; / 变量i为表达式扫描的当前位置,注意其类型 int j; char type,lasttype = GetTypeOfNotation( exp+i ); for( j=0; expi!=0 ; j+,i+ ) if( expi= )continue; notationj=expi; type=GetTypeOfNotation( notation+j ); if( type=OPTR & lasttype=OPTR ) i+, j+; break; /第一次读到的就是/运算符 if( type=OPTR & lasttype=OPND ) break; /由读到的不是运算符转为读到的是运算符 lasttype=type; notationj=NULL; if( notation0=#) i=0; /表达式扫描完毕 char GetTypeOfNotation( char *notation ) /判断一个字符是不是运算符 char opstr=+-*/()#; /运算符集 int i; if( notation0=0 ) return NULL; for (i=0; opstri!=0;i+) if( notation0=opstri) return OPTR; /R 即是运算符 return OPND; / D 即是操作数或小数点或其它如空格等 int CompareOpPrior(char op2, char op1) /2个先后出现的运算符优先级别比较：按P53表3.1/定 char opstr=+-*/()#; int i,j; int priortable77= / + - * / ( ) # 1, 1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1, -1, -1, -1, 0, I, 1, 1, 1, 1, I, 1, 1, -1, -1, -1, -1, -1, I, 0, ; for( i=0; opstri!=0; i+ ) if( op1=opstri ) break; for( j=0; opstrj!=0; j+ ) if( op2=opstrj ) break; return priortableij;测试分析与用户使用步骤：出初始界面如下数据测试，测试结果如下：选择操作1，操作结果如下，输入你想呀输入的表达式：输入表达式后，继续选择你要执行的操作选择2操作，此操作是将以中缀形式输入的表达式，构造成一棵树，然后以二叉树的先序遍历的形式输入其结果，其结果如下：执行完操作2后，继续选择你要的操作选择3操作是将表达式中的变量进行赋值，直到表达式中的所有变量都赋上确切的值位置为止，并以所对应的二叉树的先序遍历的形式输出其结果，其执行结果如下：执行完操作3后，即可执行4的操作，对表达式求值。若表达式中有变量，没有经过执行操作3而是直接执行操作4的话，程序会提醒用户先去执行操作3后，