问题描述
- 有关数据结构的编程题目
- 4-1 Evaluate Postfix Expression (10分)
Write a program to evaluate a postfix expression. You only have to handle four kinds of operators: + - x and /.我的代码如下，但还是有一个测试点没有过，求大神们帮忙~急急急~~~：
#include
#include
#include
typedef double ElementType;
#define Infinity 1e8
#define Max_Expr 30 /* max size of expression */ElementType EvalPostfix( char *expr );
int main()
{
ElementType v;
char expr[Max_Expr];
gets(expr);
v = EvalPostfix( expr );
if ( v<Infinity )
printf(""%f
"" v);
else
printf(""ERROR
"");
return 0;
}ElementType EvalPostfix( char *expr )
{
ElementType Final_v; //存储最后要返回的值
ElementType value; //存储中间的部分产物
ElementType num=0.0;
int i=-1flag=1;typedef struct StackRecord *Stack;struct StackRecord { int Capacity; /* maximum size of the stack array */ int Top; ElementType *Array; /* space for the two stacks */};Stack S;S=(Stack)malloc(sizeof(struct StackRecord));if(S==NULL) printf(""Out of space!"");S->Array=( ElementType *)malloc(sizeof(ElementType)*30);S->Top=-1; //创建一个空栈while(((*expr)>47&&(*expr)<58)||(*expr)=='-'||(*expr)=='.'){ while((*expr)!=' '&&(*expr!=0)){ if((*expr)=='-'){ flag=0; //若检测到负号，flag变为0 expr++; if((*expr)<48||(*expr)>57) { //说明‘-’是减号而非负号 expr--; flag=1; if((*(expr+1))<48||(*(expr+1))>57) //'-'后面跟了非数字的符号 return Infinity; goto B; } } if((*expr)!='.') //整数部分的计算 num=num*10+(int)((*expr)-48); else if((*expr)!='-'){ //小数部分计算 expr++; num=num+((int)(*expr)-48)*pow(10.0i--); //从“.”的后面那个数开始 } expr++; } if(flag) S->Array[++S->Top]=num; else S->Array[++S->Top]=num*(-1); flag=1; num=0.0; expr++; //任何操作数、操作符之间都有一个空格}if(S->Top<1){ //前两个一定是数字而非操作符 if(S->Top==0) return S->Array[S->Top]; else return Infinity;//not a legal postfix expression}flag=1;while((*expr)!=NULL){ //在第一次，遇到的一定是运算符
B: switch (*expr){
case '+':
value=S->Array[S->Top--];
value+=S->Array[S->Top--];
expr++;
if((*expr)==NULL)
goto A;
expr++; //加两次，跳过空格
if((*expr)==NULL)
goto A;
break;case '-': value=S->Array[S->Top--]; value=S->Array[S->Top--]-value; expr++; if((*expr)==NULL) goto A; expr++; if((*expr)==NULL) goto A; break;case '*': value=S->Array[S->Top--]; value*=S->Array[S->Top--]; expr++; if((*expr)==NULL) goto A; expr++; if((*expr)==NULL) goto A; break;case '/': if(S->Array[S->Top]==0) return Infinity;//not a legal postfix expression value=S->Array[S->Top--]; value=S->Array[S->Top--]/value; expr++; if((*expr)==NULL) goto A; expr++; if((*expr)==NULL) goto A; break;default: return Infinity;//not a legal postfix expression}//push:A: S->Array[++S->Top]=value; //将过程中产生的结果压入栈
if((*expr)==NULL)
break;//Push:while(((*expr)>47&&(*expr)<58)||((*expr)=='-'&&(*(expr+1)>47&&*(expr+1)<58))||(*expr)=='.'){ while((*expr)!=' '){ if((*expr)=='-'){ flag=0; //若检测到负号，flag变为0 expr++; if((*expr)==' ') { //说明‘-’是减号而非负号 expr--; flag=1; goto B; } } if((*expr)!='.') //整数部分的计算 num=num*10+(int)((*expr)-48); else //小数部分计算 num=num+((int)(*expr++)-48)*pow(10.0i--); //从“.”的后面那个数开始 expr++; } if(flag) S->Array[++S->Top]=num; else S->Array[++S->Top]=num*(-1); num=0.0; expr++; //任何操作数、操作符之间都有一个空格}}
if(S->Top!=0)
return Infinity;
else{Final_v=S->Array[S->Top]; return Final_v;}
}
解决方案
解决方案二：
为什么显示会是这样……