jsq.cpp

是一种数据结构的算法

#define STACK_INIT_SIZE 100 
#define STACKINCREMENT 10 
#include "stdlib.h"
#include "iostream.h"
#include"stdio.h"
typedef struct   //构造寄存运算符的栈
{char *base;
 char *top;
 int length;
}OptrStack;

int InitStack1(OptrStack &r)    //构造一个空栈
{r.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
 if(!r.base)return 0;
 r.top=r.base;
 r.length=STACK_INIT_SIZE;
 return 1;
}

char GetTop1(OptrStack r,char &e)     //返回栈顶元素
{if(r.top==r.base)return 0;
 e=*(r.top-1);
 return (e);
}

int Push1(OptrStack &r,char e)     //插入元素e为新的栈顶元素
{if(r.top-r.base>=r.length){
	r.base=(char *)realloc(r.base,(r.length+STACKINCREMENT)*sizeof(char));
	if(!r.base)return 0;
	r.top=r.base+r.length;
	r.length+=STACKINCREMENT;
}
*r.top++=e;
return 1;
}

char Pop1(OptrStack &r,char &e)     //删除栈顶元素并用e返回其值
{if(r.top==r.base)return 0;
 e=*--r.top;
 return (e);
}


typedef struct      //构造寄存操作数或运算结果的栈
{double *base;
 double *top;
 int length;
}OpndStack;

int InitStack2(OpndStack &d)      //构造一个空栈
{d.base=(double *)malloc(STACK_INIT_SIZE*sizeof(double));
 if(!d.base)return 0;
 d.top=d.base;
 d.length=STACK_INIT_SIZE;
 return 1;
}

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

int Push2(OpndStack &d,double e)
{if(d.top-d.base>=d.length){
	d.base=(double *)realloc(d.base,(d.length+STACKINCREMENT)*sizeof(double));
	if(!d.base)return 0;
	d.top=d.base+d.length;
	d.length+=STACKINCREMENT;
}
*d.top++=e;
return 1;
}

double Pop2(OpndStack &d,double &e)
{if(d.top==d.base)return 0;
 e=*--d.top;
 return (e);
}

char precede(char p,char q)               //判断运算符的优先级//
{
	 char c;
     if(p=='+')
		switch(q)
	 {
		
		    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;
	OptrStack s;
	OpndStack t;
	printf("本程序仅提供加，减，乘，除，括号运算，如超出运算范围，请您谅解！！\n");
	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));//输出结果//
	printf("运算完毕，谢谢您的使用！！\n");
}