• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C++实现简单的表达式类型

OC/C/C++ 水墨上仙 2805次浏览

前缀输入,中缀输出,若带字母,则为字母赋值,最后计算表达式的值。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
typedef enum
{
	INT, CHAR
} DataType;//CHAR=1表示存贮字符,INT=0表示存储运算数据
typedef union
{
	 char vchar;
     int num;
} ElemType;
//二叉树节点结构体
typedef struct BiTNode
{
	DataType type;//data中存储的数据的类型
	ElemType data;//数据域
	struct BiTNode *lchild, *rchild; //左右孩子指针域
} BiTNode, *BiTree;
//全局变量
char preExpr[100];//表达式
int isExist = 0;//表达式是否已经构造
int beCounted = 0;//表达式中的常数运算行为是否发生
//顺序栈功能的实现
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACK_INCREMENT 10 //存储空间分配增量
#define SElemType BiTree//元素类型
typedef struct 
{
	SElemType *base;//栈底指针
	SElemType *top;//栈顶指针
	int stackSize;//当前已分配的存储空间 以元素为单位
} SqStack;
//构造一个空栈S
int InitStack(SqStack *S) 
{
	(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!(*S).base) exit(1);
	(*S).top = (*S).base;
	(*S).stackSize = STACK_INIT_SIZE;
	return 0;
}
//若栈不空 则用e返回S的栈顶元素 并返回1 否则返回0
int GetTop(SqStack S,SElemType *e) 
{
	if(S.top == S.base) return 0;
	*e = *(S.top - 1);
	return 1;
}
//插入元素e为新的栈顶元素
int Push (SqStack *S,SElemType e) 
{
	if((*S).top - (*S).base >= (*S).stackSize) {//栈满 追加存储空间
		(*S).base = (SElemType *)realloc((*S).base,((*S).stackSize + STACK_INCREMENT)*sizeof(SElemType));
		if(!(*S).base) exit(1);//存储分配失败
		(*S).top = (*S).base + (*S).stackSize;
		(*S).stackSize += STACK_INCREMENT;
	}
	*(*S).top++ = e;
	return 1;
}
//若栈不空 则删除S的栈顶元素 用e返回其值 并返回1 否则返回0
int Pop(SqStack *S, SElemType *e) 
{
	if((*S).top == (*S).base) return 0;
	*e = * --(*S).top;
	return 1;
}
//若栈S为空栈,则返回1,否则返回0
int StackEmpty(SqStack S)
{
	if(S.top==S.base)
		return 1;
	else
		return 0;
}
//函数声明
void list();
int getPreExpr();
void AsNode(BiTree *E,int i);
int ReadExpr(BiTree *E);
int Primary(char a,char b);
void WriteExpr(BiTree E);
void Assign(BiTree *E,char V,int c,int *flag);
int Check_Variable(BiTree E);
float Operate(int a, char ope, int b);
float Value(BiTree E);
//主函数
int main()
{
	char choice;
	BiTree E,E2;//二叉树
	float value_result;
	while(1)
	{
		list();//输出功能列表
		printf("请输入你的选择:");
		choice = getch();
		switch(choice)
		{
			case '1':
				printf("\n【提示】\n算术表达式内可以含有变量(a~z),常量(0~9)和二元运算符(+, -, *, /)");
				fflush(stdin);//清理缓冲区
				if(getPreExpr())
					if(ReadExpr(&E))
					{
						isExist=1;
						printf("表达式构造成功!\n");
					}
				printf("按任意键返回:");
				getch();
				break;
			case '2':
				if(isExist==1)//检查是否已经构造表达式
				{
					printf("\n带括弧的中缀表达式为:");
					WriteExpr(E);
				}
				else
					printf("\n没有成功构造表达式!");
				printf("\n按任意键返回:");
				getch();
				break;
			case '3':
				if(isExist==1)//检查是否已经构造表达式
				{
					char next;
					do
					{
						int Assign_flag=0;
						int c;
						char V;
						printf("\n表达式E为:");
						WriteExpr(E);
						fflush(stdin);//清理缓冲区
						//获取输入
						printf("\n请输入需要赋值的变量:");
						V=getchar();
						//判断输入的是不是字符
						if((V>='a' && V<='z') || (V>='A' && V<='Z'))
						{
							printf("");
						}
						else
						{
							printf("请输入字母!");
							next = 'y';
							continue;//从头重新输入
						}
						printf("请输入需要赋给该变量的值:",V);
						scanf("%d",&c);
						Assign(&E,V,c,&Assign_flag);
						//判断是否赋值成功
						if(Assign_flag)
						{
							printf("赋值成功!\n赋值后的表达式为:");
							WriteExpr(E);
						}
						else
							printf("赋值失败!可能表达式中没有此变量!");
						printf("\n是否继续赋值?<y/n>");
						next = getch();
					}while(next=='y' || next=='Y');
				}
				else
				{
					printf("\n没有成功构造表达式!");
					printf("\n按任意键返回:");
					getch();
				}
				break;
			case '4':
				if(isExist==1)//检查是否已经构造表达式
				{
					printf("\n算术表达式为:");
					WriteExpr(E);
					if(Check_Variable(E))//确保没有未知量
					{
						value_result = Value(E);
						printf("\n其值为:");
						printf("%.2f",value_result);
					}
					else
						printf("\n表达式中仍存在没有赋值的变量!");
				}
				else
					printf("\n没有成功构造表达式!");
				printf("\n按任意键返回:");
				getch();
				break;
			case '0':
				printf("\n感谢使用,再见!\n按任意键退出:");
				getch();
				exit(0);
				break;
		}
		system("cls");//清屏
	}
	return 0;
}
//功能列表
void list()
{
	printf("------------------表达式类型的实现-----------------\n");
	printf("           1.输入前缀表示式并构造表达式\n");
	printf("           2.用带括弧的中级表示式输出表达式\n");
	printf("           3.对表达式中的变量赋值\n");
	printf("           4.对算术表达式求值\n");
	printf("----------------------------------------------------\n");
}
//获取前缀表达式
int getPreExpr()
{
	printf("\n请输入前缀表示式:");
	gets(preExpr);//从键盘输入一串字符串作为前缀表达式
	if(strlen(preExpr) == 1)//输入的表达式字符串长度为1
		//输入的表达式只有一个运算符
		if(preExpr[0] == '+' || preExpr[0] == '-' || preExpr[0] == '*' || preExpr[0] == '/')
		{
				printf("输入错误!表达式只有一个运算符!");
				return 0;
		}
		//输入的表达式只有一个数字或字符
		else if((preExpr[0] >= '0' && preExpr[0] <= '9') || (preExpr[0] >= 'a' && preExpr[0] <= 'z') || (preExpr[0] >= 'A' && preExpr[0] <= 'Z'))
		{
			printf("输入成功!表达式只有一个字符!");
			return 1;
		}
		else
		{
			printf("输入错误!输入无法识别");
			return 0;
		}
	else
		return 1;
}
//将字符或数字存为二叉树结点
void AsNode(BiTree *E,int i)
{
	if(preExpr[i]>='0' && preExpr[i]<='9')//为数字
	{
		//将字符型数字转换成字符串以满足atoi函数的参数要求
		char value[2];
		value[0] = preExpr[i];
		value[1] = '\0';
		//将字符型数字转换成整形数字
		(*E)->data.num = atoi(value);
		(*E)->type = INT;
	}
	else//为字符
	{
		(*E)->data.vchar = preExpr[i];
		(*E)->type = CHAR;
	}
}
//以前缀表示式构造表达式
int ReadExpr(BiTree *E)
{
	SqStack S;
	int i,len;//len为表达式的长度
	BiTree p,q;
	(*E) = (BiTree)malloc(sizeof(BiTNode));//申请二叉树的根结点的空间
    (*E)->lchild = NULL;
    (*E)->rchild = NULL;
	len = strlen(preExpr); //len赋值为表达式的长度
	if(len == 1)//表达式长度为1时,二叉树只有根结点
	{
		AsNode(E,0);//将第一个输入字符存入二叉树的结点中
	}
	else
	{
		AsNode(E,0);//将第一个输入字符存入二叉树的结点中
		InitStack(&S);//初始化栈
		q=(*E);
		Push(&S,q);//入栈
		Push(&S,q);//入栈,根结点入栈两次是为判断先序输入的表达式是不是正确的表达式
		for(i=1; i<len && !StackEmpty(S); i++)
		{
				p=(BiTree)malloc(sizeof(BiTNode));
				AsNode(&p,i);//将exprstring[i]存入二叉树的结点中
				p->lchild = NULL;
				p->rchild = NULL;
				//为运算符,运算符入栈,根据是否为空来选择成为左孩子还是右孩子
				if(preExpr[i]=='+' || preExpr[i]=='-' || preExpr[i]=='*' || preExpr[i]=='/')
				{
					if(!q->lchild)//左孩子空 成为左孩子
					{
						q->lchild=p;
						Push(&S,p);
						q=p;
					}
					else//右孩子空 成为右孩子
					{
						q->rchild=p;
						Push(&S,p);
						q=p;
					}
				}
				else//不是运算符,运算符出栈
				{
					if(!q->lchild)
					{
						q->lchild=p;
						Pop(&S,&q);
					}
					else
					{
						q->rchild=p;
						Pop(&S,&q);
					}
				}
		}
		//栈空且i>=len,说明输入的表达式是正确的
		if(StackEmpty(S) && i >= len)
		{
			return 1;
		}
		else
		{
			printf("\n输入的表达式有误!");
			return 0;
		}
	}
}
//如果两个字符是运算符,比较两个运算符的优先级 输出是否a比b优先
int Primary(char a,char b)
{
	//判断是否为运算符
	if((a=='*' || a=='-' || a=='+' || a=='/') && (b=='*' || b=='-' || b=='+' || b=='/'))
	{
		//a为乘法或除法运算符 优先于加减运算符
		if(a=='*' || a=='/')
		{
			if(b == '*' || b == '/')
				return 0;
			else
				return 1;
		}
		else
			return 0;
	}
	else
		return 0;
}
//用带括弧的中缀表达式输出表达式
void WriteExpr(BiTree E)
{
	//树不为空 中序遍历
	if(E)
	{
		//递归左子树
		if(E->lchild && E->lchild->type == CHAR)//E的左孩子不为空且为字符
		{
			//双亲运算符比孩子运算符优先
			if(Primary(E->data.vchar,E->lchild->data.vchar))
			{
				//带括弧输出左子树
				printf("(");
				WriteExpr(E->lchild);
				printf(")");
			}
			else
				WriteExpr(E->lchild);//不带括弧输出左子树
		}
		else WriteExpr(E->lchild);//直接输出左子树
		//访问输出根结点的值
		if(E->type == INT)
		 	printf("%d",E->data.num);
		else
			printf("%c",E->data.vchar);
		//递归右子树
		if(E->rchild && E->rchild->type == CHAR)//E的右孩子不为空且为字符
		{
			//双亲运算符比孩子运算符优先
			if(Primary(E->data.vchar,E->rchild->data.vchar))
			{
				//带括弧输出右子树
				printf("(");
				WriteExpr(E->rchild);
				printf(")");
			}
			else
				WriteExpr(E->rchild);//不带括弧输出右子树
		}
		else
			WriteExpr(E->rchild);//直接输出右子树
	}
}
//实现对表达式中的所有变量V的赋值(V=c) 参数flag为表示是否赋值过的标志
void Assign(BiTree *E,char V,int c,int *flag)
{
	//二叉树存在 先序递归遍历
	if(*E)
	{
		if((*E)->type == CHAR && (*E)->data.vchar == V)//找到要赋值的变量
		{
			(*E)->type = INT; //修改元素类型
			(*E)->data.num = c;
			*flag = 1;//标志已赋值
		}
		//递归左子树
		Assign(&((*E)->lchild),V,c,flag);
		//递归右子树
		Assign(&((*E)->rchild),V,c,flag);
	}
}
//检查表达式是否还存在没有赋值的变量 先序递归遍历
int Check_Variable(BiTree E)
{
	//树不为空且元素为字符型
	if(E && E->type == CHAR)
	{
		//存在非运算符
		if(E->data.vchar != '*' && E->data.vchar != '-' && E->data.vchar != '+' && E->data.vchar != '/')
			return 0;
		//递归左子树
		if(Check_Variable(E->lchild))
		{
			Check_Variable(E->rchild);//递归右子树
		}
	}
	else
		return 1;
}
//基本运算求值 ope:运算符
float Operate(int a, char ope, int b)
{
	switch(ope)
	{
		case '+': return (a+b); break;
		case '-': return (a-b); break;
		case '*': return (a*b); break;
		case '/': return (a/b); break;
    	default : return 0;
	}
}
//对算术表达式求值
float Value(BiTree E)
{
	if(E)//树不为空
	{
		//若为叶子结点(即数字)则返回结点的值
		if(!E->lchild && !E->rchild && E->type == INT)
			return E->data.num;
		//非叶子结点则继续递归求值
		return Operate(Value(E->lchild),E->data.vchar,Value(E->rchild));
	}
}


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C++实现简单的表达式类型
喜欢 (0)
加载中……