数据结构课程设计 表达式类型的实现包含测试数据和课程设计报告完美版

【问题的描述】 一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式Expression的操作。 【基本要求】 【一】【必做部分】 假设算术表达式Expression内可以含有变量（a-z）,常量（0-9）和二元运算符（+，-，*，/，^（乘幂））。实现以下操作： （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）以表达式的原书写形式输入，支持大于0的正整数常量； （2）增加常数合并操作MergeConst(E)——合并表达式E中所有常数运算。例如，对表达式E=(2+3-a)*(b+3*4)进行合并常数的操作后，求得E=(5-a)*(b+12) 【测试数据】 1) 分别输入0；a;-91;+a*bc;+*5x2*8x;+++*3^*2^x2x6并输出。 2) 每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。 3) 还有很多测试的数据，详细请见附上的文件Test.txt。

	#include“expression.h“
	/*全局变量*/
	int save_number[31];/*在按原表达式输入形式中，输入的常量保存到数组save_number中，常量最多为30个，0单元不用*/
	char Expr_String[30];/*存放表达式的字符串*/
	
	/*以字符序列的形式输入语法正确的前缀表达式，保存到字符串string*/
	/*参数flag=0表示输出的提示信息是“请输入正确的前缀表示式：“*/
	/*flag=1表示输出的提示信息为“请以表达式的原书写形式输入正确表示式：“*/
	Status Input_Expr（char *stringint flag）
	{
		if（flag==0）printf（“\n请输入正确的前缀表示式：“）;
		else printf（“\n请以表达式的原书写形式输入正确表示式：“）;
		flushall（）;/*清理缓冲区*/
		gets（string）;/*从键盘输入一串字符串作为表达式*/
		if（strlen（string）==1）/*输入的表达式字符串长度为1*/
			if（string[0]==‘+‘||string[0]==‘-‘||string[0]==‘*‘||string[0]==‘/‘||string[0]==‘^‘）/*输入的表达式只有一个运算符*/
				{ printf（“\n表达式只有一个字符，为运算符，错误！“）;return ERROR;}
			else if（（string[0]>=‘0‘&&string[0]<‘9‘）||（string[0]>=‘a‘&&string[0]<=‘z‘）||（string[0]>=‘A‘&&string[0]<=‘Z‘））
				/*输入的表达式只有一个数字或字符*/
				{ printf（“\n表达式只有一个字符！“）;return OK;}
			else {printf（“\n输入的字符不是运算符也不是变量常量，错误！“）;return ERROR;}
		return OK;
	}

	/*判断字符string[i]，如果是‘0‘-‘9‘常量之间，二叉树结点存为整型；否则，存为字符型*/
	void judge_value（BiTree *Echar *stringint i）
	{
			if（string[i]>=‘0‘&&string[i]<=‘9‘）/*为常量*/
				{（*E）->data.tag=INT;（*E）->data.num=string[i]-48;}
			else if（string[i]>=1&&string[i]<=20）/*为常量，常量存于数组save_number中*/
				{（*E）->data.tag=INT;（*E）->data.num=save_number[string[i]];}
			else/*为变量*/
				{（*E）->data.tag=CHAR;（*E）->data.c=string[i];}
	}

	/*以正确的前缀表示式并构造表达式E*/
	Status ReadExpr（BiTree *Echar *exprstring）
	{
		SqStack S;
		int ilen;/*len为表达式的长度*/
		BiTree pq;
		（*E）=（BiTree）malloc（sizeof（BiTNode））;/*申请二叉树的根结点的空间*/
		（*E）->lchild=NULL;
		（*E）->rchild=NULL;
		len=strlen（exprstring）;/*len赋值为表达式的长度*/
		if（len==1）/*表达式长度为1时，二叉树只有根结点*/	
			judge_value（Eexprstring0）;/*将exprstring[0]存入二叉树的结点中*/
		else 
		{
			judge_value（Eexprstring0）;/*将exprstring[0]存入二叉树的结点中*/
			InitStack（&S）;/*初始化栈*/
			q=（*E）;
			Push（&Sq）;/*入栈*/
			Push（&Sq）;/*入栈，根结点入栈两次是为判断先序输入的表达式是不是正确的表达式*/
			for（i=1;i			{
				p=（BiTree）malloc（sizeof（BiTNode））;
				judge_value（&pexprstringi）;/*将exprstring[i]存入二叉树的结点中*/
				p->lchild=NULL;
				p->rchild=NULL;
				if（exprstring[i]==‘+‘||exprstring[i]==‘-‘||exprstring[i]==‘*‘||exprstring[i]==‘/‘||exprstring[i]==‘^‘）
				{/*为运算符，运算符入栈，左孩子不空，向左孩子走，否则，如果右孩子不空，向右孩子走*/
					if（!q->lchild）	{q->lchild=p;Push（&Sp）;q=p;}
					else	{q->rchild=p;Push（&Sp）;q=p;}
				}
				else/*不是运算符，运算符出栈*/
				{
					if（!q->lchild）	{q->lchild=p;Pop（&S&q）;}
					else	{q->rchild=p;Pop（&S&q）;}
				}
			}
			if（StackEmpty（S）&&i>=len）	return OK;/*栈空且i>=len，说明输入的表达式是正确的*/
			else	/*输入的表达式是错误的*/
			{
				printf（“\n输入的表达式有误！“）;
				return ERROR;
			}
		}
	}

	/*如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR*/
	Status Pri_Compare（char c1char c2）
	{
		if（（c1==‘^‘||c1==‘*‘||c1==‘-‘||c1==‘+‘||c1==‘/‘）&&（c2==‘^‘||c2==‘*‘||c2==‘-‘||c2==‘+‘||c2==‘/‘））
		{/*c1和c2为运算符*/
			if（c1==‘^‘）/*c1为指数运算符，则当c2不为‘^‘时，c1比c2优先*/
			{
				if（c2!=‘^‘） return OK;
				else return ERROR;
			}
			else if（c1==‘*‘||c1==‘/‘）/*c1为乘法或除法运算符，则当c2为‘+‘或

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

    ..A.SH.      4608  2008-07-12 14:13  数据结构课程设计-表达式类型的实现\Thumbs.db

     文件       1654  2008-07-04 16:39  数据结构课程设计-表达式类型的实现\测试\测试数据.txt

    ..A.SH.     38400  2008-07-04 15:52  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\Thumbs.db

     文件     654890  2008-07-04 13:51  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\主菜单界面.bmp

     文件      99582  2008-07-04 15:44  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\合并常数操作 多次合并1.bmp

     文件     100206  2008-07-04 15:45  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\合并常数操作 多次合并2.bmp

     文件      97030  2008-07-04 15:45  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\合并常数操作 多次合并3.bmp

     文件     432694  2008-07-04 15:42  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\合并常数操作1.bmp

     文件     189198  2008-07-04 14:09  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试前缀表达式输入 -91.bmp

     文件     230094  2008-07-04 14:10  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试前缀表达式输入 变量.bmp

     文件     561570  2008-07-04 14:06  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试前缀表达式输入 常量.bmp

     文件     191754  2008-07-04 14:12  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试前缀表达式输入 较为复杂表达式.bmp

     文件     179534  2008-07-04 15:15  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试前缀表达式输入 输出带括弧.bmp

     文件     143190  2008-07-04 14:17  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试前缀表达式输入 错误前缀表达式1.bmp

     文件     143414  2008-07-04 14:19  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试前缀表达式输入 错误前缀表达式2.bmp

     文件     194614  2008-07-04 14:55  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试原表达式输入 BUG1.bmp

     文件     155970  2008-07-04 15:09  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试原表达式输入 出错处理1.bmp

     文件     156214  2008-07-04 15:11  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试原表达式输入 出错处理2.bmp

     文件     158774  2008-07-04 15:14  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试原表达式输入 出错处理3.bmp

     文件     159270  2008-07-04 15:20  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试原表达式输入 出错处理4.bmp

     文件     176694  2008-07-04 15:03  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试原表达式输入 简化括弧.bmp

     文件     309814  2008-07-04 14:42  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试构造复合表达式1.bmp

     文件     286774  2008-07-04 14:44  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试构造复合表达式2.bmp

     文件     563254  2008-07-04 14:45  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试构造复合表达式3.bmp

     文件     107238  2008-07-04 14:40  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试求算数表达式的值 带有变量.bmp

     文件     311886  2008-07-04 14:36  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试求算数表达式的值1.bmp

     文件     105014  2008-07-04 14:38  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试求算数表达式的值2.bmp

     文件     258210  2008-07-04 14:27  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试赋值操作1.bmp

     文件     261174  2008-07-04 14:29  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试赋值操作2.bmp

     文件     227538  2008-07-04 14:32  数据结构课程设计-表达式类型的实现\测试\部分测试的截图\测试赋值操作3.bmp

............此处省略12个文件信息