第4个回答 2005-12-17
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define true 1
#define false 0
#define ok 1
#define error 0
#define overflow -2
#define STACK_INIT_SIZE 100
#define STACKINCERMENT 10
typedef int status;
typedef int operandtype;
typedef char operatortype;
typedef struct sqstack{
int *base;
int *top;
int stacksize;
}sqstack;
char a[8][8]={
{'\0','+','-','*','/','(',')','#'},
{'+','>','>','<','<','<','>','>'},
{'-','>','>','<','<','<','>','>'},
{'*','>','>','>','>','<','>','>'},
{'/','>','>','>','>','<','>','>'},
{'(','<','<','<','<','<','=','\0'},
{')','>','>','>','>','\0','>','>'},
{'#','<','<','<','<','<','\0','='}};
status in(char c) //判断c是否运算符函数
{ if(c<'0'||c>'9')
return true;
else
return false;
}
status initstack(sqstack &s) //初始化栈函数
{ s.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
if(!s.base) exit(overflow);
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return ok;
}
status gettop(sqstack s, int &e) //取栈顶元素函数
{ if(s.top==s.base)
return error;
e=*(s.top-1);
return ok;
}
status push(sqstack &s,int e) // 压栈函数
{ if(s.top-s.base>=s.stacksize){
s.base=(int *)realloc(s.base,(s.stacksize+STACKINCERMENT)*sizeof(int));
if(!s.base) exit(overflow);
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCERMENT;
}
*s.top++=e;
return ok;
}
status pop(sqstack &s,int &e) //出栈函数
{ if(s.top==s.base)
return error;
e=*--s.top;
return ok;
}
operatortype precede(operatortype c1,operatortype c2) //判断两个运算符优先级函数
{ int i,j;
for(i=0;i<8&&a[i][0]!=c1;i++); //从第0列查找操作符c1
if(i>=8){
printf("Operator error!/n");
exit(error);
}
for(j=0;j<8&&a[0][j]!=c2;j++); //从第0行查找操作符c2
if(j>=8){
printf("Operator error!/n");
exit(error);
}
return a[i][j];
}
status stackempty(sqstack s) //判断栈是否为空函数
{ if(s.base==s.top)
return true;
else
return false;
}
status check(char *str) //查看表达式括号是否匹配函数
{ int i=0,e;
sqstack s;
initstack(s);
while(str[i]!='#')
{ switch(str[i]){
case'(': push(s,str[i]); break;
case'[': push(s,str[i]); break;
case')': if(pop(s,e))
{ if(e=='(')
break;
else
return error;
}
else return error;
case']': if(pop(s,e))
{ if(e=='[')
break;
else
return error;
}
else return error;
}
i++;
}
if(stackempty(s))
return ok;
else
return error;
}
operandtype operate(operandtype a,operatortype thera,operandtype b) //求两个元素通过指定运算的结果函数
{ switch(thera){
case'+': return a+b;
case'-': return a-b;
case'*': return a*b;
case'/': if(b==0)
{ printf("Divide zero!\n"); //除数为0,程序结束
exit(overflow);
}
else
return a/b;
default: printf("Operator error!\n"); //操作符错误,程序结束
exit(error);
}
}
operandtype evaluate_expression(char *str) //求表达式值函数
{ int i=0,value,e,t,a,b,thera,buffer;
char c;
sqstack optr,opnd;
initstack(optr); initstack(opnd);
push(optr,'#');
c=str[i];
gettop(optr,e);
while(c!='#'||e!='#')
{ if(!in©){
buffer=c-'0';
do{ if(!in(str[i+1])){
buffer*=10;
buffer+=(str[i+1]-'0');
i++;
}
}while(!in(str[i+1]));
push(opnd,buffer);
i++;
c=str[i];
}
else
switch(precede(e,c)){
case'<': push(optr,c); c=str[++i];
break;
case'=': pop(optr,t); c=str[++i]; // 消去括号
break;
case'>': pop(optr,thera);
pop(opnd,b); pop(opnd,a);
push(opnd,operate(a,thera,b)); //求值并压栈
break;
}
gettop(optr,e);
}
gettop(opnd,value);
return value;
}
void main() //主函数
{ char str[STACK_INIT_SIZE],c;
int flag,t;
do{ flag=1;
while(flag)
{ printf("Input a string,end with #:\n");
scanf("%s",str); //str用来存放字符串
if(check(str))
flag=0;
else
{ flag=1;
printf("Input error,Retry!\n"); //符号不匹配则重新输入
}
}
t=evaluate_expression(str);
printf("The result:%d\n",t);
printf("Continue or not?(y/n):");
getchar();
c=getchar();
}while(c=='y'||c=='Y'); //实现多次输入
getch();
}