#define STACK_INIT_SIZE 100 
#define STACKINCREMENT 10 
#include "stdlib.h"
#include "iostream.h"
#include"stdio.h"
typedef struct   //構(gòu)造寄存運(yùn)算符的棧
{char *base;
 char *top;
 int length;
}OptrStack;

int InitStack1(OptrStack &r)    //構(gòu)造一個(gè)空棧
{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      //構(gòu)造寄存操作數(shù)或運(yùn)算結(jié)果的棧
{double *base;
 double *top;
 int length;
}OpndStack;

int InitStack2(OpndStack &d)      //構(gòu)造一個(gè)空棧
{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)               //判斷運(yùn)算符的優(yōu)先級(jí)//
{
	 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)            //判斷字符是數(shù)字還是運(yùn)算符，是運(yùn)算符返回1，否則返回0//
{
	if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='=')
		return 1;
	else
		return 0;
}
 
double operate(double a, char theta, double b)          //算術(shù)運(yùn)算//
{
	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         //構(gòu)造一個(gè)結(jié)構(gòu)體來(lái)存放讀入的數(shù)字串//
{
	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("本程序僅提供加，減，乘，除，括號(hào)運(yùn)算，如超出運(yùn)算范圍，請(qǐng)您諒解！！\n");
	printf("請(qǐng)輸入您的算術(shù)表達(dá)式：:");
    InitStack1(s);       //構(gòu)造一個(gè)存放運(yùn)算符的堆棧，壓入‘=’//
	Push1(s,'=');
    InitStack2(t);   //構(gòu)造一個(gè)存放數(shù)字串的堆棧//   
	c=getchar();
	while(c!='='||GetTop1(s,theta)!='=')     //讀入的不是‘=’并且棧頂元素也不是‘=’//
	{
		x=In(c);
		if(x!=1)          //讀入的是數(shù)字//
		{
			i=0;
		   p=(struct chardata *)malloc(sizeof(struct chardata));   //開(kāi)辟內(nèi)存空間來(lái)存放數(shù)字串//
		   while(x!=1)              //如果是數(shù)字則循環(huán)讀入，直到讀入的是運(yùn)算符為止//
		   {
		    p->ch[i]=c;
			i=i+1;
			c=getchar();
			x=In(c);
		   }	                 //如果是字符則把已讀入的數(shù)字串轉(zhuǎn)化為實(shí)數(shù)，入棧，并釋放內(nèi)存空間//
		    f=atof(p->ch);
		    Push2(t,f);
			free(p);
		}
		else           //讀入的是運(yùn)算符//
		{
			
            switch(precede(GetTop1(s,e),c))       //比較當(dāng)前的運(yùn)算符和棧頂?shù)倪\(yùn)算符的優(yōu)先級(jí)//
			{
			case'<':                //棧頂元素優(yōu)先級(jí)低，讀入的運(yùn)算符入棧//
				Push1(s,c);
			    c=getchar();
				break;
			case'=':           //脫括號(hào)并接受下個(gè)字符//
				Pop1(s,z);
				c=getchar();
				break;
			case'>':       //退棧并將運(yùn)算結(jié)果入棧//
				Pop1(s,theta);
				Pop2(t,b);
				Pop2(t,a);
				Push2(t,operate(a,theta,b));
				break;
			}
		}
	}
	printf("您的算術(shù)表達(dá)式的結(jié)果是: %f\n",GetTop2(t,d));//輸出結(jié)果//
	printf("運(yùn)算完畢，謝謝您的使用！！\n");
}