#include<stdafx.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100
typedef int Status;
typedef char SElemType;
char Precede(char a,char b);
char EvaluateExpression();
int Operate(int a,char theta,int b);
typedef struct //定义顺序栈
{
char *base;
char *top;
int stacksize;
}SqStack;
/*栈函数/
int InitStack(SqStack &S)//初始化
{
S.base=(char*)malloc(sizeof(char)*MAXSIZE);
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=MAXSIZE;
return OK;
}
int Push(SqStack &S,char e)//入栈
{
if(S.top-S.base==S.stacksize) return ERROR;//栈满
*S.top=e; //元素e压入栈顶,栈顶指针加1;
S.top++;
return OK;
}
int Pop(SqStack &S,char &e)//出栈
{
if(S.top==S.base) return ERROR; //栈空
--S.top;//栈顶指针减一,将栈顶元素赋给e;
e=*S.top;
return OK;
}
int GetTop(SqStack S, char &e)
{
if (S.top == S.base) return ERROR; // 栈空
e = *(S.top - 1);
return OK;
}
int In(char e)//判断读入字符是否为运算符
{
if(e=='+'||e=='-'||e=='*'||e=='/'||e=='('||e==')'||e=='#')
return OK;//是
else
return ERROR; //不是
}
char precede(char a,char b)//比较运算符的优先级
{
char f;
if(a=='+'||a=='-')
{
if(b=='+'||b=='-'||b==')'||b=='#')
f='>';
else if(b==''||b=='/'||b=='(')
f='<';
}
else if(a=='*'||a=='/')
{
if(b=='+'||b=='-'||b=='*'||b=='/'||b==')'||b=='#')
f='>';
else if(b=='(')
f='<';
}
else if(a=='(')
{
if(b=='+'||b=='-'||b=='*'||b=='/'||b=='(')
f='<';
else if(b==')')
f='=';
}
else if(a==')')
{
if(b=='+'||b=='-'||b=='*'||b=='/'||b==')'||b=='#')
f='>';
}
else if(a=='#')
{
if(b=='+'||b=='-'||b==''||b=='/'||b=='(')
f='<';
else if(b=='#')
f='=';
}
return f;
}
int Operate(int a,char theta,int b)//运算结果
{
int c;
switch(theta) {
case '+': c = a + b; break;
case '-': c = a - b; break;
case '*':c= a * b; break;
case '/': c = a / b; break;
}
return c;
}
char EvaluateExpression()
{
SqStack OPND,OPTR;
int ch;
char a,b,theta;
char x;
InitStack(OPND);//操作数栈和运算结果
InitStack(OPTR);//运算符栈
Push(OPTR,'#');
ch=getchar();
while(ch!='#'||GetTop(OPTR)!='#')
{
printf("%c\n",ch);
if(!In(ch)) /如果为数字
{
ch=ch-48;
Push(OPND,ch);
ch=getchar();
}
else //如果不是数字
{
switch(Precede(GetTop(OPTR),ch))
{
case '<': //读入字符优先级高
Push(OPTR,ch);
ch=getchar();
break;
case '>': //读入字符优先级低
Pop(OPTR,theta);
Pop(OPND,b);
Pop(OPND,a);
Push(OPND,Operate(a,theta,b));
break;
case '=': //优先级相同
Pop(OPTR,x);
ch=getchar();
break;
}
}
}
return GetTop(OPND);
}
int main()
{
printf("请输入算术表达式,并以#结束\n");
printf("结果是: %d\n",EvaluateExpression());
return 0;
}