树结构的应用：表达式类型的实现

蔚落 2022-03-01 06:12 152阅读 0赞

#include <iostream>
    #include<cmath>
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    using namespace std;
    struct BiTNode					//结点的数据
    {
    	bool tag;			//true为数字，false为字符		
    	int num;
    	char c;
    	BiTNode *lchild,*rchild;
    };
    
    struct SqStack										//顺序栈
    {
    	BiTNode *base;									// 在栈构造之前和销毁之后，base的值为NULL 
    	int stacksize;									//当前已分配的存储空间，以元素为单位 
    	int top1;
    	BiTNode **address;                        //存储当前最顶端数据的地址,在构造二叉树的时候会有地址的存储返回子树的根节点
    
    	int InitStack(int n)					// 构造一个空栈S
    	{  
    		base=new BiTNode[n];
    		stacksize=n;
    		address=new BiTNode *[n];
    		top1=0;             //从0开始存数据
    		return OK;
    	}
    
    	int StackEmpty()						// 若栈S为空栈，则返回TRUE，否则返回FALSE 
    	{ 
    		if(top1==0)   
    			return TRUE;
    		else  
    			return FALSE;
    	}
    
    	int Push(BiTNode *e)						// 插入元素e为新的栈顶元素
    	{  
    		*(base+top1)=*e;
    		address[top1]=e;
    		top1++;
    		return OK;
    	}
    
    	BiTNode* Pop()						// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR/
    	{ 
    		if(top1<0) return ERROR;
    		top1--;
    		return address[top1];
    	}
    };
    
    BiTNode *tree;									//定义树
    SqStack Stack;								 //定义栈,在建立二叉树的的时候作为中间变量，存储部分子树的根节点
    
    void judge_value(BiTNode *t,char exprstring)		//判断字符string[i],加引用是为了在调用函数的时候改变原来t的值
    {
    
    	if(exprstring>='0'&&exprstring<='9')		//为常量
    	{
    		t->tag=true;
    		t->c='#';                              //有数字的时候，字符赋值为#
    		t->num=exprstring-48;
    	}
    	else									//为变量
    	{
    		t->tag=false;
    		t->num=-1;                          //当是字符形式，则数字赋值为-1
    		t->c=exprstring;
    	}
    }
    
    int ReadExpr(char *exprstring,int len)				//以字符序列的形式输入语法正确的前缀表示式并构造表达式
    {
    	int i;								//len为表达式的长度 
    	BiTNode *p,*q;
    	tree=new BiTNode;					//申请二叉树的根结点的空间 
    	tree->lchild=NULL;
    	tree->rchild=NULL;
    	if(len==1)											//表达式长度为1时，二叉树只有根结点 	
    		judge_value(tree,exprstring[0]);			//将exprstring[0]存入二叉树的结点中 
    	else 
    	{
    		judge_value(tree,exprstring[0]);		//同理
    		Stack.InitStack(len);					//初始化栈 
    		q=tree;
    		Stack.Push(tree);									//入栈 
    		Stack.Push(tree);										//入栈，根结点入栈两次是为判断先序输入的表达式是不是正确的表达式 
    		for(i=1;i<len&&!Stack.StackEmpty();i++)
    		{
    			p=new BiTNode;
    			judge_value(p,exprstring[i]);						//将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;
    					Stack.Push(p);
    					q=p;
    				}
    				else	
    				{
    					q->rchild=p;
    					Stack.Push(p);
    					q=p;
    				}
    			}
    			else						//不是运算符，运算符出栈 
    			{
    				if(!q->lchild)	
    				{
    					q->lchild=p;
    					q=Stack.Pop();
    				}
    				else	
    				{
    					q->rchild=p;
    					q=Stack.Pop();
    				}
    			}
    		}
    		if(Stack.StackEmpty()&&i>=len)	return OK;                      //只有栈为空的时候才把二叉树构造成功
    		else	
    		{
    			cout<<"                      输入的字符串无法构造成表达式！"<<endl;
    			return ERROR;
    		}
    	}
    	return OK;
    }
    int Compare(char c1,char c2)				//比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR 
    {		
    	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为'+'或'-'，c1比c2优先 
    		{
    			if(c2=='^'||c2=='*'||c2=='/') return ERROR;
    			else return OK;
    		}
    		else return ERROR;					//其余，c1不比c2优先 
    	}
    	else return ERROR;				//c1和c2不是运算符 
    }
    	
    
    void WriteExpr(BiTNode *Tree)						//用带括弧的中缀表示式输出表达式
    {
    	if(Tree)										//树不为空 
    	{												//先递归左子树 
    		if(Tree->lchild&&!Tree->lchild->tag)		//二叉树的左孩子不为空，且左孩子为字符 
    		{
    			if(Compare(Tree->c,Tree->lchild->c))    //Tree->c的优先级大于Tree->lchild->c必须带有并输出（） 
    			{
    				cout<<"(";
    				WriteExpr(Tree->lchild);
    				cout<<")";
    			}
    			else									//否则，不带括弧输出左子树 	
    				WriteExpr(Tree->lchild);			
    		}
    		else 										//否则，输出左子树 
    			WriteExpr(Tree->lchild);				
    			
    		if(Tree->tag)								//访问输出根结点的值 
    		{
    			cout<<Tree->num;
    		}
    		else
    			cout<<Tree->c;
    			
    		if(Tree->rchild&&!Tree->rchild->tag)				//后递归右子树,树的右孩子不为空，且右孩子为字符 
    		{
    			if(Compare(Tree->c,Tree->rchild->c))			//Tree->c比Tree->rchild->c优先 
    			{
    				cout<<"(";
    				WriteExpr(Tree->rchild);
    				cout<<")";
    			
    			}													//带括弧输出右子树 
    			else 
    				WriteExpr(Tree->rchild);							//否则，不带括弧输出右子树 
    		}
    		else 
    			WriteExpr(Tree->rchild);//否则，输出右子树 
    	}
    }
    //赋值语句
    
    void Assign(BiTNode *Tree,char V,int c,int *flag)
    {
    	if(Tree)
    	{
    		if(Tree->tag==false&&Tree->c==V)		//如果找到要赋值的变量，赋值 
    		{
    			Tree->tag=true;
    			Tree->num=c;
    			*flag=1;
    		}
    		Assign(Tree->lchild,V,c,flag);//递归左子树 
    		Assign(Tree->rchild,V,c,flag);//递归左子树 
    	}
    }
    
    int Check(BiTNode *Tree)                   //检查二叉树中是否还存在没有赋值的变量，以便求算数表达式的值 
    {
    	if(Tree&&Tree->tag==false)            //二叉树不为空,并且根节点为字符
    	{		
    		if(Tree->c!='*'&&Tree->c!='^'&&Tree->c!='-'&&Tree->c!='+'&&Tree->c!='/')return ERROR;        //是字符但不是运算符
    		if(Check(Tree->lchild))               //递归左子树 
    			Check(Tree->rchild);              //递归右子树 	
    	}
    }
    
    int Calculate(int n1,char opr,int n2)             //运算符计算，返回计算结果值
    {
    	int result;
    	switch(opr)                                   //匹配多种情况
    	{
    		case '+':
    			result=n1+n2;
    			return result;
    			break;
    		case '-':
    			result=n1-n2;
    			return result;
    			break;
    		case '*': 
    			result=n1*n2;
    			return result;
    			break;
    		case '/':
    			result=n1/n2;
    			return result;
    			break;
    		case '^':
    			result=pow(n1,n2);
    			return result;
    			break;
    		default:break;
    	}	
    }
    int Value(BiTNode *Tree)                   //计算返回整个表达式的值
    {
    	if(Tree)							//二叉树不为空 
    	{
    		if(!Tree->lchild&&!Tree->rchild&&Tree->tag) return (Tree->num);    //结点的左孩子和右孩子为空，为叶子结点，返回结点的值 
    		return Calculate(Value(Tree->lchild),Tree->c,Value(Tree->rchild));   //运算求值，后根遍历的次序对表达式求值 
    	}
    }
    void main()
    {
    	char Expr_string[1000];                           //存放刚开始输入的字符串
    	int n,ttt=1;
    	while(ttt)
    	{
    con:	cout<<"                 是否还要计算，是请按1，否请按0:";
    		cin>>ttt;
    		system("cls");
    		flushall();                              //输入之前清理缓冲区
    		cout<<"                       请输入前缀表达式：";
    		cin.getline(Expr_string,1000);                //从键盘输入一串字符串作为表达式
    		n=strlen(Expr_string);
    		if(n==1)                                 //输入的表达式字符串长度为1
    		{
    			if(Expr_string[0]=='+'||Expr_string[0]=='-'||Expr_string[0]=='*'||Expr_string[0]=='/'||Expr_string[0]=='^')//输入的表达式只有一个运算符 
    			{ 
    				cout<<"                       表达式只有一个运算符，错误！"<<endl;
    				goto con;
    			} 
    			else 
    				if((Expr_string[0]>='0'&&Expr_string[0]<'9')||(Expr_string[0]>='a'&&Expr_string[0]<='z')||(Expr_string[0]>='A'&&Expr_string[0]<='Z'))
    				{ 
    					cout<<"                       表达式只有一个字符"<<endl;
    					goto con;
    				}
    				else 
    				{
    					cout<<"     输入的字符不是运算符也不是变量或常量，错误！"<<endl;
    					goto con;
    				}
    		}
    		if(ReadExpr(Expr_string,n))
    		{
    				cout<<"                       二叉树构造成功！"<<endl;
    				cout<<"                       中缀表达式为：";
    				WriteExpr(tree);
    				cout<<endl;
    			int s=0,Assign_flag=0,t=Check(tree);              //s记录有几个变量
    			while(!t)                  //检验表达式中是否有变量，如果有的话就重新赋予整数值,跳出循环式则整个表达式完整
    			{
    				if(t)cout<<"                       表达式不存在未赋值的变量！"<<endl;
    				else
    				{
    					int c;char V;
    					cout<<"                       表达式中存在变量未赋值！"<<endl;
    					cout<<"                       请输入要赋值的值：";	cin>>V;
    					cout<<"                       请输入要将赋值为：";	cin>>c;
    					Assign(tree,V,c,&Assign_flag);                 //把所有的要赋予的值全在Assign赋值完成
    					if(Assign_flag)	
    					{
    						cout<<"                       赋值成功!"<<endl;
    					}
    					else
    					{
    						cout<<"表达式里没有"<<V<<",请重新输入!"<<endl;
    					}
    				}
    				t=Check(tree);
    			}
    			cout<<"                       整个表达式赋值成功!"<<endl;
    			cout<<"                       表达式为:";
    			WriteExpr(tree);
    			cout<<endl;
    			int result=Value(tree);
    			cout<<"                       算数表达式的值为: ";
    			WriteExpr(tree);
    			cout<<"="<<result<<endl;
    		}
    		else
    			goto con;
    	}
    }

测试数据：

0  
a  
\-91  
\+a\*bc  
\+\*5^x2\*8x  
\+++\*3^x3\*2^x2x6  
\-^+5a32  
\--+++\*3^x3\*2^x2x6