数据结构——整数四则运算

╰半夏微凉° 2022-04-22 02:22 176阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    
    #define STACT_INIT_SIZE 100 //存储空间初始分配量
    #define STACKINCREMENT 100  //存储空间分配增量
    
    typedef struct 
    {
    	int *base;      //栈底指针
    	int *top;       //栈顶指针
    	int  stacksize;  //当前已分配的存储空间。
    }SqStack;
    
    //函数原型：
    int InitStack(SqStack &s);      //构建空栈函数；
    int Push(SqStack &s,int m);    //元素入栈函数
    int Pop(SqStack &s);           //元素出栈函数
    int In(char s[],int &n,char op[]);      //判断是否运算符函数
    int GetTop(SqStack &s);        //取栈顶元素函数
    int EvaluateExpression(char s[],char c[7][7]);
    int fond_op(char n);            //寻找运算符函数
    char precede(int n,char m,char c[7][7]); //比较运算符优先级函数
    int Operate(int a,int theta, int b); //运算函数
    
    
    int main()
    {
    	char c[7][7]={  {'>','>','<','<','<','>','>'},
    					{'>','>','<','<','<','>','>'},
    					{'>','>','>','>','<','>','>'},
    					{'>','>','>','>','<','>','>'},
    					{'<','<','<','<','<','=',' '},
    					{'>','>','>','>',' ','>','>'},
    					{'<','<','<','<','<',' ','='}
    
    	};  
    
    	char s[100]={0};
    	printf("请属于正确的运算表达式(以'#'结尾):");
    	scanf("%s",s);    //将字符串读入；
    	printf("ans=%d\n",EvaluateExpression(s,c));
    	return 0;
    }
    
    //*************运算函数****************
    int EvaluateExpression(char s[100],char c[7][7])
    {
    	int i=0,z=0,y;
    	int theta,a,b,x;
    	char op[7]={'+','-','*','/','(',')','#'};// ok
    	SqStack optr;      //存运算符；
        InitStack(optr);  //构建运算符空栈； //ok
    	Push(optr,6);   //将符号'#'压入optr栈底；//ok
    	SqStack opnd;    //存运算数；
    	InitStack(opnd);  //构建运算数空栈  //ok
    	//判断不是结束符'#' 和 栈已经空了
    	while(s[i]!='\0'&& (s[i]!='#' || GetTop(optr)!=6))
    	{
    		y=In(s,i,op);
    		if(y!=-1) //不是运算符则放进运算数栈中；
    		{
    			//printf("数字入栈:");
    			Push(opnd,y);
    			i++;
    		}
    		else 
    		{
    			switch(precede(GetTop(optr),s[i],c))
    			{	
    			case '<':
    				{
    					Push(optr,fond_op(s[i]));
    					//printf("算符入栈:");
    					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 GetTop(opnd);;
    }
    
    //**********构造空栈函数************
    int InitStack(SqStack &s)
    {
    	//请求分配STACT_INIT_SIZE个char类型的空间来作为栈；
        s.base=(int*)malloc(STACT_INIT_SIZE*sizeof(int));
    	if(!s.base) exit(0);  //判断申请空间内存是否成功；
    	s.top=s.base;          //将栈顶指针也指向栈底指针，表示空栈；
    	//将申请分配的栈当前的空间个数存进s.stacksize
    	s.stacksize=STACT_INIT_SIZE;   
    	return 1;
    }
    
    //************元素入栈函数***********
    int Push(SqStack &s,int m)
    {
    	int *new_p=NULL;
    	if(!s.base) exit(0); //判断栈是否存在
    	//判断是否没有内存来存新元素；
    	//若是内存不顾就用realloc（）函数重新申请内存；
    	//将新分配的内存地址放在new_p中，若申请成功再将new_p赋给栈底指针;
    	//避免原来的栈底指针丢失；
    	if(s.base-s.top>=s.stacksize)  
    	{
    	    new_p=(int*)realloc(s.base,(STACT_INIT_SIZE+STACKINCREMENT)*sizeof(int));
    		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;
    }
    
    
    //************元素出栈函数***********
    int Pop(SqStack &s)
    {
    	int m;
    	if(!s.base) exit(0); //判断栈是否存在；
    	if(s.top==s.base)    //判断是否是空栈
    	{
    		printf("栈已经为空了\n");
    		exit(0);
    	}
    	s.top--;   //让栈顶指针指向栈中最后一个元素
    	m=*s.top;  //把栈中最后一个元素存进m中；
    	return m;
    }
    
    //************取栈顶元素函数***********
    int GetTop(SqStack &s)
    {
    	if(!s.base) exit(0); //判断栈是否存在；
    	if(s.top==s.base)    //判断是否是空栈
    	{
    		printf("栈已经为空了\n");
    		exit(0);
    	}
    	return *(s.top-1);
    }
    
    //************判断是否运算符函数***********
    int In(char s[],int &n,char op[])
    {
    	int i,j,x=0,t=0;
    	for(i=0;i<7;i++)
    	{
    		if(s[n]==op[i]) return -1; //是字符；
    	}
    	x=s[n]-'0';
    	for(i=n+1;(s[i]!='\0' && s[i]!='#');i++)
    	{
    		for(j=0;j<7;j++)
    		{
    			if(s[i]==op[j])
    			{
    				return x;
    			}
    		}
    		x=x*10+s[i]-'0';
    		n++;
    	}
    	return x;
    }
    
    
    //***********比较运算符优先级函数**********
    //	switch(precede(GetTop(optr),s[i],c))
    char precede(int n,char m,char c[7][7])
    {
    	int b;
    	b=fond_op(m);
    	return c[n][b];
    }
    
    
    //**********寻找运算符函数**********
    int fond_op(char n)
    {
    	int a;
    	if(n=='+') a=0;
    	else if(n=='-') a=1;
    	else if(n=='*') a=2;
    	else if(n=='/') a=3;
    	else if(n=='(') a=4;
    	else if(n==')') a=5;
    	else if(n=='#') a=6;
    	return a;
    }
    
    //*********运算函数************
    int Operate(int a,int theta, int b)
    {
    	int ans;
    	if(theta==0) ans=a+b;
    	if(theta==1) ans=a-b;
        if(theta==2) ans=a*b;
    	if(theta==3) ans=a/b;
    	return ans;
    }
    
    
    //3*(7-2)#    15
    //22*(2-1)#    22
    //4+2*3-10/5#   8
    //40+160/40    44
    //95/(64-45)#  5
    //85+14*(14+208/26)#  393
    //(23+23)*24-597#  507
    //424-437/19*16#  56