本人数据结构课程设计做的是算术表达式求值,但是程序运行起来一直无限循环。请各位大神求助!万分感谢。明天就要交了。
#include
#include
#include
#define OK1 1
#define OK2 1.0
#define TRUE 1
#define ERROR1 0
#define ERROR2 0.0
#define FALSE 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
char OPSET[7]={'+','-','*','/','(',')','#'};
char Prior[7][7] = { // 算符间的优先关系
'>','>','<','<','<','>','>',
'>','>','<','<','<','>','>',
'>','>','>','>','<','>','>',
'>','>','>','>','<','>','>',
'<','<','<','<','<','=',' ',
'>','>','>','>',' ','>','>',
'<','<','<','<','<',' ','='
};
typedef struct //运算符栈
{
char *base; //在栈构造之前和销毁之后,base的值为NULL
char *top; //栈顶指针
int stacksize; //当前已分配的存储空间,以元素为单位
}SqStack1;
typedef struct //操作数栈
{
float *base; //在栈构造之前和销毁之后,base的值为NULL
float *top; //栈顶指针
int stacksize; //当前已分配的存储空间,以元素为单位
}SqStack2;
void InitStack1(SqStack1 &S1){
//构造一个空栈
S1.base = (char *) malloc(STACK_INIT_SIZE * sizeof(char));
if (!S1.base) exit(OVERFLOW); //存储分配失败
S1.top = S1.base;
S1.stacksize = STACK_INIT_SIZE;
}
char GetTop1(SqStack1 S1){
//若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR;
char e;
if (S1.top == S1.base) return ERROR1;
e = *(S1.top - 1);
return e;
}
char Push1(SqStack1 &S1, char e){
//插入元素e为新的栈顶元素
if(S1.top - S1.base >= S1.stacksize) {//栈满,追加存储空间
S1.base = (char *) realloc(S1.base, (S1.stacksize + STACKINCREMENT) * sizeof(char));
if (!S1.base) exit(OVERFLOW);//存储分配失败
S1.top = S1.base + S1.stacksize;
S1.stacksize += STACKINCREMENT;
}
*S1.top++ = e;
return OK1;
}
char Pop1(SqStack1 &S1){
//若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
char e;
if (S1.top == S1.base) return ERROR1;
e = *--S1.top;
return e;
}
void DispStack1(SqStack1 &S1){//从栈底到栈顶依次输出各元素
char e,*p;
if(S1.top==S1.base) printf(" ");
else{
p=S1.base;
while(p<S1.top){
e=*p;
p++;
printf("%c",e);
}
}
}
void InitStack2(SqStack2 &S2){
//构造一个空栈
S2.base = (float *) malloc(STACK_INIT_SIZE * sizeof(float) );
if (!S2.base) exit(OVERFLOW); //存储分配失败
S2.top = S2.base;
S2.stacksize = STACK_INIT_SIZE;
}
float GetTop2(SqStack2 S2){
//若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR;
float e;
if (S2.top == S2.base) return ERROR2;
e = *(S2.top - 1);
return e;
}
float Push2(SqStack2 &S2, float e){
//插入元素e为新的栈顶元素
if (S2.top - S2.base >= S2.stacksize) {
//栈满,追加存储空间
S2.base = (float *) realloc(S2.base, (S2.stacksize + STACKINCREMENT) * sizeof(float) );
if (!S2.base) exit(OVERFLOW);//存储分配失败
S2.top = S2.base + S2.stacksize;
S2.stacksize += STACKINCREMENT;
}
*S2.top++ = e;
return OK2;
}
float Pop2(SqStack2 &S2){
//若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
float e;
if (S2.top == S2.base) return ERROR2;
e = *--S2.top;
return e;
}
void DispStack2(SqStack2 &S2){ //从栈底到栈顶依次输出各元素
float e,*p;
if(S2.top==S2.base) printf(" ");
else{
p=S2.base;
while(p<S2.top){
e=*p;
p++;
printf("%f",e);
}
}
}
char Precede(char OP1,char OP2){
//判断运算符优先级
int i=0,j=0;
while(OPSET[i]!=OP1){
i++;
}
while(OPSET[j]!=OP2){
j++;
}
return Prior[i][j];
}
float Operate(float a, char theta, float b) {
//运算
float s;
switch(theta){
case '+': s= a+b;break;
case '-': s= a-b;break;
case '*': s= a*b;break;
case '/': if(b!=0) s= a/b;break;
default : s= 0.0;
}
return s;
}
float EvaluateExpression(){
char c;
float t,e;
int n=0,i=1,j=0,k=0,l=0;
char ch[STACK_INIT_SIZE];
int s=1,flag=0,flag2=0;
float p1,p2;
char ch1;
SqStack1 S1; InitStack1(S1);
SqStack2 S2; InitStack2(S2);
Push1(S1,'#');
printf("请输入不含变量的表达式(以'#'结尾):\n");
c=getchar();
ch[0]=c;
printf("\n对表达式求值操作过程如下:");
printf("\n____________________________________________________________\n");
printf("步骤\t运算符栈S1\t操作数栈S2\t输入字符\t\t主要操作");
while(c!='#'||GetTop1(S1)!='#'){
printf("\n____________________________________________________________\n");
printf("%d\t",i++);
DispStack1(S1); printf("\t\t");
DispStack2(S2); printf("\t\t");
if(flag==1){
k--; flag=0;
}
if(flag2){
k=k+flag2; flag2=0;
}
for(l=0;l
for(j=k;ch[j]!='\0';j++) printf("%c",ch[j]);
if(ch[k]!='#'&&flag!=1){
k++; flag=0;
}
as:
if(!(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#')){
//输入的字符如果不是运算符号,则继续输入直到输入的是运算符为止,将非运算符转换成浮点数
if(!(c=='.')&&n>=0){
e=(float)c-48;
n++;
if(n==1) t=e;
else if(n>1)
t=t*10+e;
c=ch[s++];
}
if(n==-1){
e=(float)c-48;
t=t+e/10;
c=ch[s++];
}
if(c=='.'){
n=-1;
c=ch[s++];
}
if((c>='0'&&c<='9')||c=='.'){
flag2++;
goto as;
}
if(c<'0'||c>'9'){
Push2(S2,t);
}
printf("\t\tPush2(S2,%f)",t);
}
else{//输入的是运算符
n=0;//非运算型数据计数器清零
switch(Precede(GetTop1(S1),c)){//比较运算符的优先级
case '<': //栈顶元素优先级低,则入栈且继续输入
Push1(S1,c);
printf("\t\tPush1(S1,%c)",c);
c=ch[s++];
break;
case '=': //栈顶元素优先级相等,脱括号并接收下一字符
Pop1(S1);
printf("\t\tPop1(S1)");
c=ch[s++];
break;
case '>': //栈顶元素优先级高,则退栈并将运算结果入栈
p1=Pop2(S2);
p2=Pop2(S2);
ch1=Pop1(S1);
Push2(S2,Operate(p2,ch1,p1));
printf("\t\tOperate(%f,%c,%f)",p2,ch1,p1);
flag=1;
break;
}
}
}
printf("\n____________________________________________________________\n");
printf("%d\t#\t\t%f\t\t",i,GetTop2(S2));
for(j=0;j<k;j++) printf(" ");
printf("#\t\tRETURN(GETTOP(S2))");
printf("\n____________________________________________________________\n");
if(S2.top-1==S2.base)//显示表达式最终结果
printf("表达式的结果为:%f",GetTop2(S2));
else printf("\n表达式出错!\n");
}
void main(){
EvaluateExpression();
}