#include<malloc.h>
#include<stdio.h>
#include<process.h>
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
//typedef char SElemType;//
//typedef char Status;//
struct SqStack{
int *base;
int *top;
int stacksize;
};
int InitStack(SqStack &S){
S.base = (int *)malloc(STACK_INIT_SIZE*sizeof(int));
if(!S.base) return ERROR;
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
int Push(SqStack &S,char e){
if(S.top-S.base>=S.stacksize){
S.base = (int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
if(!S.base)exit(0);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
int Pop(SqStack &S,char &e){
if(S.top == S.base) return ERROR;
e=*--S.top;
return OK;
}
int GetTop(SqStack S){
char e;
if(S.top == S.base) return ERROR;
e = *--S.top;
return e;
}
int Transfor(char c)
{ //返回字符c对应优先关系表中的行列号
int k;
switch(c)
{
case '+':k=0;break;
case '-':k=1;break;
case '*':k=2;break;
case '/':k=3;break;
case '(':k=4;break;
case ')':k=5;break;
case '#':k=6;break;
}
return k;
}
char JudgePrecede(char c1,char c2){
//优先级判断
int i,j;
char pre[7][7]={{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=',' '},
{'>','>','>','>',' ','>','>'},
{'<','<','<','<','<',' ','='}
};
i=Transfor(c1);
j=Transfor(c2);
return(pre[i][j]);
}
int IfOperator(char c){
//判断c是否为运算符
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#')
{
return(1);
}
else
{
return(0);
}
}
char Operate(char a,char theta,char b)
{
char c;
a=a-48;
b=b-48;
switch(theta)
{
case'+':c=a+b+48;break;
case'-':c=a-b+48;break;
case'*':c=a*b+48;break;
case'/':c=a/b+48;break;
}
return c;
}
char EvaluateExpression(){
SqStack OPTR,OPND;
char a,b,c,x,theta;
InitStack(OPTR);
Push(OPTR,'#');
InitStack(OPND);
c=getchar();
while(c!='#'||GetTop(OPTR)!='#'){
if(!IfOperator(c))
{
Push(OPND,c);
c=getchar();
}
else
switch(JudgePrecede(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;
}
}
return GetTop(OPND);
}
void main()
{
printf("请输入算术表达式(中间值及最终结果要在0~9之间),并以#结束\n");
printf("%c\n",EvaluateExpression());
}