数据结构——四则运算-小数

逃离我推掉我的手 2022-04-22 02:22 199阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    
    #define STACT_INIT_SIZE 100 //存储空间初始分配量
    #define STACKINCREMENT 100  //存储空间分配增量
    
    typedef struct 
    {
    	float *base;      //栈底指针
    	float *top;       //栈顶指针
    	int  stacksize;  //当前已分配的存储空间。
    }SqStack;
    
    //函数原型：
    int InitStack(SqStack &s);                //构建空栈函数；
    float Push(SqStack &s,float m);           //元素入栈函数
    float Pop(SqStack &s);                    //元素出栈函数
    float In(char s[],int &n,char op[]);      //判断是否运算符函数
    float GetTop(SqStack &s);                 //取栈顶元素函数
    float EvaluateExpression(char s[],char c[7][7]);//运算函数
    float fond_op(char n);                    //寻找运算符函数
    char precede(float n,char m,char c[7][7]); //比较运算符优先级函数
    float Operate(float a,float theta, float b); //运算函数
    void shuoming();                           //说明程序功能
    
    //主函数
    int main()
    {
    	//存运算符优先级；
    	char c[7][7]={  {'>','>','<','<','<','>','>'},   
    					{'>','>','<','<','<','>','>'},
    					{'>','>','>','>','<','>','>'},
    					{'>','>','>','>','<','>','>'},
    					{'<','<','<','<','<','=',' '},
    					{'>','>','>','>',' ','>','>'},
    					{'<','<','<','<','<',' ','='}
    
    	};  
    	char s[100]={0};            //存储运算表达式
    	shuoming();
    
    	while(1)
    	{
    		printf("*********************************\n");
    		printf("请输入运算表达式:");
    		scanf("%s",s);              //将字符串读入
    		if(s[0]=='t') break;
    		//调用运算函数；
    	
    		printf("运算结果=%.4f\n\n",EvaluateExpression(s,c)); 
    	}
    	return 0;
    }
    
    //*************运算函数****************
    float EvaluateExpression(char s[100],char c[7][7])
    {
    	int i=0; //字符串循环变量；
    	float theta,a,b,x,y;
    	//存储字符串中可能出现的符号
    	//栈是float型指针，所以由0.0~6.0依次代表这些算符；
    	char op[7]={'+','-','*','/','(',')','#'};
    	SqStack optr;      //存运算符；
        InitStack(optr);   //构建运算符空栈；
    	Push(optr,6.0);    //将符号'#'压入optr栈底；
    	SqStack opnd;      //存运算数；
    	InitStack(opnd);   //构建运算数空栈 
    	//判断不是结束符'#' 和 栈已经空了
    	while(s[i]!='\0'&& (s[i]!='#' || GetTop(optr)!=6.0))
    	{
    		//判断s[i]是不是运算数，是运算数=y，不是运算数=-1.0
    		//i是参数引用，i会移到符号前面的一个操作数字符;
    		y=In(s,i,op);
    		if(y!=-(1.0)) //不是运算符则放进运算数栈中；
    		{
    			//printf("数字入栈:");
    			Push(opnd,y);
    			i++;                //i移到算符上；
    		}
    		else 
    		{
    			//取算符栈的栈顶元素和s[i]符号进行优先级比较
    			switch(precede(GetTop(optr),s[i],c))
    			{	
    			case '<':
    				{
    					//printf("算符入栈:");
    					Push(optr,fond_op(s[i]));			
    					i++;
    					break;
    				}
    			case '=':
    				{
    					x=Pop(optr);
    					i++;
    					break;
    				}
    			case '>':
    				{
    			    	theta=Pop(optr);
    					b=Pop(opnd);
    					a=Pop(opnd);
    					//printf("运算结果入栈:");
    					Push(opnd,Operate(a,theta,b));
    					break;
    				}
    			}
    		}
    	}
    	return Pop(opnd);
    }
    
    //**********构造空栈函数************
    int InitStack(SqStack &s)
    {
    	//请求分配STACT_INIT_SIZE个float类型的空间来作为栈；
        s.base=(float*)malloc(STACT_INIT_SIZE*sizeof(float));
    	if(!s.base) exit(0);  //判断申请空间内存是否成功；
    	s.top=s.base;          //将栈顶指针也指向栈底指针，表示空栈；
    	//将申请分配的栈当前的空间个数存进s.stacksize
    	s.stacksize=STACT_INIT_SIZE;   
    	return 1;
    }
    
    //************元素入栈函数***********
    float Push(SqStack &s,float m)
    {
    	float *new_p=NULL;
    	//printf("%f\n",m);
    	if(!s.base) exit(0); //判断栈是否存在
    	//判断是否没有内存来存新元素；
    	//若是内存不顾就用realloc（）函数重新申请内存；
    	//将新分配的内存地址放在new_p中，若申请成功再将new_p赋给栈底指针;
    	//避免原来的栈底指针丢失；
    	if(s.base-s.top>=s.stacksize)  
    	{
    	    new_p=(float*)realloc(s.base,(STACT_INIT_SIZE+STACKINCREMENT)*sizeof(float));
    		if(!new_p)
    		{
    			printf("重新申请内存分配失败！");
    			exit(0);
    		}
    	    s.base=new_p;
    		s.top=s.base+STACKINCREMENT; //用首地址加偏移量找到栈顶指针；
    		s.stacksize+=STACT_INIT_SIZE;//更新栈空间的大小；
    	}
    	(*s.top)=m; //将新元素压进栈顶；
    	s.top++;  //栈顶指针往上移；
        return 0;
    }
    
    
    //************元素出栈函数***********
    float Pop(SqStack &s)
    {
    	float m;
    	if(!s.base) exit(0); //判断栈是否存在；
    	if(s.top==s.base)    //判断是否是空栈
    	{
    		printf("栈已经为空了\n");
    		exit(0);
    	}
    	s.top--;   //让栈顶指针指向栈中最后一个元素
    	m=*s.top;  //把栈中最后一个元素存进m中；
    	return m;
    }
    
    //************取栈顶元素函数***********
    float GetTop(SqStack &s)
    {
    	if(!s.base) exit(0); //判断栈是否存在；
    	if(s.top==s.base)    //判断是否是空栈
    	{
    		printf("栈已经为空了\n");
    		exit(0);
    	}
    	return *(s.top-1);
    }
    
    //*********字符转数字函数***********
    float In(char s[],int &n,char op[])
    {
    	int i,j,flag=-1;
    	float x,p;
    	x=0.0;
    	p=(float)0.1;
    	for(i=0;i<7;i++)
    	{
    		//先判断传过来的第一个是不是算符
    		//是算符就不用进行下面的操作了
    		if(s[n]==op[i]) return -(1.0); //是字符；
    	}
    	//第一个不是算符，是操作数，将一个操作数转成浮点型数字，
    	x=(float)(s[n]-'0');
    	//printf("x=%f\n",x);
    	//再判断后面的字符是不是操作数，是操作数将他进行转换
    	for(i=n+1;(s[i]!='\0' && s[i]!='#');i++)
    	{
    		
    		for(j=0;j<7;j++)
    		{
    			if(s[i]==op[j])
    			{
    				flag=-1;
    				return x;
    			}
    		}
    		if(s[i]=='.' || flag==1)
    		{
    			flag=1;
    			if(s[i]!='.')
    			{
    				//printf("x=%f",x);
    				x=x+(s[i]-'0')*p;
    				p=float(p*0.1);
    		        //printf("浮点数转换=%f\n",x);
    			}
    		}
    		if(flag==-1) x=x*10+s[i]-'0';
    		n++;
    	}
    	return x;
    }
    
    
    //***********比较运算符优先级函数**********
    //	switch(precede(GetTop(optr),s[i],c))
    char precede(float n,char m,char c[7][7])
    {
    	int a,b;
    	float x;
    	a=(int)n;
    	x=fond_op(m);
    	b=(int)x;
    	return c[a][b];
    }
    
    
    //**********寻找运算符函数**********
    float fond_op(char n)
    {
    	float a;
    	if(n=='+') a=0.0;
    	else if(n=='-') a=1.0;
    	else if(n=='*') a=2.0;
    	else if(n=='/') a=3.0;
    	else if(n=='(') a=4.0;
    	else if(n==')') a=5.0;
    	else if(n=='#') a=6.0;
    	return a;
    }
    
    //*********运算函数************
    float Operate(float a,float theta, float b)
    {
    	float ans;
    	if(theta==0.0) ans=a+b;
    	if(theta==1.0) ans=a-b;
        if(theta==2.0) ans=a*b;
    	if(theta==3.0) ans=a/b;
    	return ans;
    }
    
    void shuoming()
    {
    
    	printf("\n     哈哈,欢迎来到小梅梅的计算课堂!\n");
    	printf("---------------------------------------------\n");
    	printf("|  程序功能:实现小数和整数四则混合运算;     |\n");
    	printf("|  操作方法:请输入要计算的运算表达式!       |\n");
    	printf("|  程序说明:1.运算表达式要正确!             |\n");
    	printf("|           2.运算表达式后加上'#'做结尾符   |\n");
    	printf("|           3.循环输入,输入字符t可退出程序! |\n");
    	printf("|           4.结果仅保留四位小数哟          |\n");
    	printf("|  小梅梅祝大家使用愉快!  O(∩_∩)O~        |\n");
    	printf("---------------------------------------------\n\n");
    }
    
    //测试案例：
    //3*(7-2)#    15.0000
    //22*(2-1)#    22.0000
    //4+2*3-10/5#   8.0000
    //40+160/40#    44.0000
    //95/(64-45)#  5.0000
    //85+14*(14+208/26)#  393.0000
    //(23+23)*24-597#  507.0000
    //424-437/19*16#  56.0000
    //18.1+(3-0.299/0.23)*1#  19.8000
    //42/(5.25/0.25)#  2.0000
    //(9-0.45)/(2.5+1.5*3)#  1.2214
    //0.85*199# 169.1500
    //18.9/7-(2/7-10/21)# 2.8905