compute.cpp

数据结构常用的算法

#define STACK_SIZE  100
#define STACKINCREMENT   10
#include"stdlib.h"
#include"stdio.h"
typedef struct             
{
     char *base;
	 char *top;
	 int  stacksize;
}Stack1;

int InitStack1(Stack1 &S)           
{
	S.base=(char *)malloc(STACK_SIZE*sizeof(char));
    if(!S.base) 
    return 0;
    S.top = S.base ;
	S.stacksize=STACK_SIZE;
    return 1;
}

char GetTop1(Stack1 S,char &e)           
{
	if(S.top==S.base)
	return 0;
	e=*(S.top-1);
	return(e);
}

int Push1(Stack1 &S,char e)           
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(char *)realloc(S.base,
			(S.stacksize+STACKINCREMENT)*sizeof(char));
		if(!S.base) 
		return 0;
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
	return 1;
}

char Pop1(Stack1 &S, char &e)        
{
	if(S.top==S.base)
	return 0;
	e=*--S.top;
	return(e);
}

typedef struct{            //定义一个存放数字串的堆栈类型//
    double *base;
	double *top;
	int stacksize;
} Stack2;

int InitStack2(Stack2 &T)                
{
	T.base=(double *)malloc(STACK_SIZE*sizeof(double));
	if(!T.base)
	return 0;
	T.top=T.base;
	T.stacksize=STACK_SIZE;
	return 1;
}

double GetTop2(Stack2 T,double &e)             
{
	if(T.top==T.base)
	return 0;
	e=*(T.top-1);
	return(e);
}

int Push2(Stack2 &T,double e)               
{
	if(T.top-T.base>=T.stacksize)
	{
		T.base=(double *)realloc(T.base,
			(T.stacksize+STACKINCREMENT)*sizeof(double));
		if(!T.base) 
		return 0;
		T.top=T.base+T.stacksize;
		T.stacksize+=STACKINCREMENT;
	}
	*T.top++=e;
	return 1;
}
double Pop2(Stack2 &T, double &e)            
{	if(T.top==T.base)
	return 0;
	e=*--T.top;
	return(e);
}

char precede(char p,char q)             
{
	 char c;
     if(p=='+')
		switch(q)
	 {
		case'+':
		case'-':
		case')':
		case'=':
		    c='>';
		    break;
		case'*':
		case'/':
		case'(':
		    c='<';
		    break;
		default:
		return 0;
		break;
	}
	if(p=='-')
		switch(q)
	{
		case'+':
		case'-':
		case')':
		case'=':
		    c='>';
		    break;
		case'*':
		case'/':
		case'(':
		    c='<';
		    break;
        default:
		return 0;
		break;
	}
	if(p=='*')
	switch(q)
	{
		case'+':	
		case'-':
	    case'*':
	    case'/':		
	    case')':
		case'=':
            c='>';
    	    break;
	    case'(':
		    c='<';
		    break;
        default:
		return 0;
		break;
	}
	if(p=='/')
		switch(q)
	{
        case'+':	
		case'-':
	    case'*':
	    case'/':		
	    case')':
		case'=':
           c='>';
    	   break;
	    case'(':
		   c='<';
		   break; 
		default:
		return 0;
		break;
	}
     if(p=='(')
		switch(q)
	 {  
        case'+':	
		case'-':
	    case'*':
	    case'/':		
	    case'(':
	        c='<';
    	    break;
	    case')':
		    c='=';
		    break;
		default:
		return 0;
		break;
	 }
    if(p==')')
		switch(q)
	 {  
        case'+':	
		case'-':
	    case'*':
	    case'/':		
	    case')':
        case'=':
	       c='>';
		   break;
	    default:
		return 0;
		break;
	 }
     if(p=='=')
		switch(q)
	 {  
        case'+':	
		case'-':
	    case'*':
	    case'/':		
	    case'(':
           c='<';
		   break;
		case'=':
		   c='=';
		   break;
	    default:
		return 0;
		break;
	 }
	 return(c);
}

int In(char c)            //判断字符是数字还是运算符，是运算符返回1，否则返回0//
{
	if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='=')
		return 1;
	else
		return 0;
}
 
double operate(double a, char theta, double b)          //算术运算//
{
	double z;
	switch(theta)
	{
	    case'+':
		z=a+b;
		break;
     	case'-':
		z=a-b;
		break;
	    case'*':
		z=a*b;
		break;
		case'/':
		z=a/b;
		break;
	}
	return(z);
}

struct chardata         
{
	char ch[10];
};

void main()
{
	char c,e,z,theta;
    double a,b,d,f;
	int i,x;
	chardata *p;
	Stack1 S;
	Stack2 T;
	printf("请输入您的算术表达式:");
    InitStack1(S);       //构造一个存放运算符的堆栈，压入‘=’//
	Push1(S,'=');
    InitStack2(T);   
	c=getchar();
	while(c!='='||GetTop1(S,theta)!='=')     
	{
		x=In(c);
		if(x!=1)          
		{
			i=0;
		   p=(struct chardata *)malloc(sizeof(struct chardata));   
		   while(x!=1)              
		   {
		    p->ch[i]=c;
			i=i+1;
			c=getchar();
			x=In(c);
		   }	                 
		    f=atof(p->ch);
		    Push2(T,f);
			free(p);
		}
		else           
		{
			
            switch(precede(GetTop1(S,e),c))    
			{
			case'<':                
				Push1(S,c);
			    c=getchar();
				break;
			case'=':           
				Pop1(S,z);
				c=getchar();
				break;
			case'>':       
				Pop1(S,theta);
				Pop2(T,b);
				Pop2(T,a);
				Push2(T,operate(a,theta,b));
				break;
			}
		}
	}
	printf("您的算术表达式的结果是: %f\n",GetTop2(T,d));
}