#include"conio.h"

#include "stdio.h"

#include "stdlib.h"

#define STACK_INIT_SIZE 100

#define STACKINCREMENT  10

typedef char  SElemType;

typedef int    Status;

#define  OK        1 

#define  OVERFLOW  0

#define  ERROR     0

typedef struct{

	SElemType *base;

	SElemType *top;

	int stacksize;

}SqStack;



Status InitStack(SqStack &s){//构造一个空栈

        s.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));

		if(!s.base)exit(OVERFLOW);

		s.top=s.base;

		s.stacksize=STACK_INIT_SIZE;

		return OK;

}//InitStack

SElemType Getop(SqStack s){//若栈不空,则返回用e返回s栈元素

	    SElemType e;

		if(s.top==s.base)return ERROR;

		e=*(s.top-1);

		return e;

}//Getop

Status Push(SqStack &s,SElemType e){//插入元素e为新的栈顶元素

	   if(s.top-s.base>=s.stacksize){//栈满,追加存储空间

		   s.base=(SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SEle

mType));

		   if(!s.base)exit(OVERFLOW);//存储分配失败

		   s.top=s.base+s.stacksize;

		   s.stacksize+=STACKINCREMENT;

	   }

	   *s.top++=e;

	   return OK;

}//Push

Status Pop(SqStack &s,SElemType &e){//若栈不空,则删除s的栈顶元素,用e 返回其值,并

返回OK,否则返回ERROR

	   if(s.top==s.base)return ERROR;

	   e=*--s.top;

	   return OK;

}//Pop





char Precede(char e,char c){//比较运算任符的优先权

	if(e=='+')

	{	if(c=='+'||c=='-'||c==')'||c=='#')

			return '>';

	      return '<';

	}

	else if(e=='-')

	{ 

		if(c=='+'||c=='-'||c==')'||c=='#')

			return '>';

		   return '<';

	}

	else if(e=='*')

	{

		if(c=='(')

			return '<';

         return '>';

	}

	else if(e=='/')

	{

		if(c=='(')

			return '<';

      return '>';

	}

	else if(e=='(')

	{

		if(c==')')

			return '=';

		else if(c=='+'||c=='-'||c=='*'||c=='/'||c=='(')

			return '<';

	}

	else if(e==')')

	{

		if(c=='+'||c=='-'||c=='*'||c=='/'||c==')'||c=='#')

    return '>';

	}

	else if(e=='#')

	{	if(c=='#')

			return '=';

		     else if(c=='+'||c=='-'||c=='*'||c=='/'||c=='(')

			return '<';

	}

return 0;

}



int  Operate(char b,char theta,char a) {//运算

    int  temp;

//	b-=48;a-=48;

	 if(theta=='+')

	 temp =b+a;

	else if(theta=='*')

		temp=b * a;

	else if(theta=='-')

		temp=b-a;

	else if(theta=='/')

		temp=b/a;



	return temp;

}



char OP[]={'+','-','*','/','(',')','#'};

int In(char c,char OP[])//比较是否为运算符

{   int i;

     for(i=0;i<=6;i++)

	 if(c==OP[i])

		return 1;

	return 0;

}	

char EvluateExpression(){

	//算术表达式求值的算符优先算法.设OPTR和OPND分别为运算栈和运算数栈,

	//OP为运算任集合

	SqStack OPTR,OPND;char a,b,c,x,theta;

	InitStack(OPTR); Push(OPTR,'#');

	InitStack(OPND);c=getchar();

	 while(c!='#'||Getop(OPTR)!='#'){

		if(!In(c,OP)){Push(OPND,c-48);c=getchar();}//不是运算符则进栈

		else

			switch(Precede(Getop(OPTR),c)){

			case '<'://栈顶元素优先权低

				  Push(OPTR,c);c=getchar();break;

			case  '='://脱括号并接收下一字符

				  Pop(OPTR,x);c=getchar();break;

			case  '>'://退栈并将运算结果入栈

				  Pop(OPTR,theta);

				  Pop(OPND,b);Pop(OPND,a);

				  Push(OPND,Operate(a,theta,b));

				  break;

		}//switch

	}//while

	return Getop(OPND);

}//EvluateExpression

void main()

{  char temp;

   temp=EvluateExpression();

   printf("%d\n",temp);

   return;

}

/*本例子能实现如:9+6-5*2/1#

结果为5

实现四则运算.供大家学习作参考.