#include<string.h>
#include<stdio.h>
#include <stdlib.h>

#define OVERFLOW 0
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct SqStack
{ char *base;
char *top;
int stacksize;
}SqStack;

void InitStack (SqStack &S)
{
S.base = (char *) malloc(STACK_INIT_SIZE * sizeof(char) );
if ( ! S.base )
exit (OVERFLOW); // 为栈 S 分配存储空间失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
}

int Push(SqStack &S,char ch) //Push() subfunction
// 将元素 e 插入到栈 S 中，成为新的栈顶元素
{
if(S.top-S.base >S.stacksize) //Stack == full?
{ S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT*sizeof(char)));
if(!S.base)
{
printf("Failure to reallocate the Memory units!");
exit(OVERFLOW);
}
S.top=S.base+S.stacksize; //To modify pointer of Stack top
S.stacksize+=STACKINCREMENT; //To modify the size of stack
}//end of if
*S.top++=ch; //先将 e 送入栈顶指针所指向的单元，再将栈顶指针加 1 //S.top++ and push e into stack S
return (OK);
}//end of Push() subfunction

int Pop(SqStack &S,char &ch)
{
if(S.top==S.base)
{
printf("下溢 !");
return (ERROR);
}
ch=*--S.top;
// 先令栈顶指针减 1，再将栈顶指针所指向的单元内的值赋给 e
return(OK);

char OP[10]={'+','-','*','/','(',')','#'};
int precede[7][7]={
1,1,2,2,2,1,1,
1,1,2,2,2,1,1,
1,1,1,1,2,1,1,
1,1,1,1,2,1,1,
2,2,2,2,2,3,0,
1,1,1,1,0,1,1,
2,2,2,2,2,0,3};

int In(char c,char *op)
{
int i=0;
while(i<7)
if(c==op[i++])
return 1;
return 0;
}

char Precede(char op,char c)
{
int pos_op;
int pos_c;
int i;
for(i=0;i<7;i++)
{
if(op==OP[i]) pos_op=i;
if(c==OP[i]) pos_c=i;
}
switch(precede[pos_op][pos_c])
{
case 1: return '>';
case 2: return '<';
case 3: return '=';
}
}

char Operate(int a,char theta,int b)
{
switch(theta)
{
case '+':return a+b-'0';
case '-':return a-b+'0';
case '*':return (a-'0')*(b-'0')+'0';
case '/':return (a-'0')/(b-'0')+'0';
}
}

char EvaluateExpression()
{
SqStack *OPND,*OPTR;
char c,x,theta;
char a,b;
InitStack(&OPTR); Push(OPTR,'#');
InitStack(&OPND);
c=getchar();
while(c!='#'||GetTop(*OPTR)!='#')
{
if(!In(c,OP))
{Push(OPND,c);c=getchar();}
else
switch(Precede(GetTop(*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;
}
}
c=GetTop(*OPND);
DestroyStack(OPTR);
DestroyStack(OPND);
return c;
}

main()
{
char i;
printf("\n\n\n\nOnly within 0..9 evaluation,input a expression end with symbol #:\n");
i=EvaluateExpression();
printf("\nThis expression's result is: ");
printf("%d\n\n\n\n",i-'0');

}