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\n", v);
else
printf("ERROR\n");
return 0;
}
ElementType EvalPostfix( char *expr )
{
ElementType Final_v; //存储最后要返回的值
ElementType value; //存储中间的部分产物
ElementType num=0.0;
int i=-1,flag=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.0,i--); //从“.”的后面那个数开始
}
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.0,i--); //从“.”的后面那个数开始
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;
}
}