#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
实现四则运算.供大家学习作参考.
