jiangsi554 于 2014.05.12 22:47 提问

/*核心函数*/
double Nibolansuanfa(char *str,stack *s)
{
initstack(&s);//初始化栈
char st[20],tc,xy;//st[20]里面放数字字符串
int j=0,i=0,yxcount=0;
double d;
while(str[j]!='\0')
{

``````/*数字字符拷贝*/
if(Isnum(str[i]))
{
while(Isnum(str[i]))
{
st[i]=str[j];//将数字字符串放到st数组
i++;
j++;
}
/*数字字符转换并进数字栈*/
i=0;
d=atof(st);
pushdb(s,d);
st[20]=0;
continue;
}
/*非数字字符进字符栈*/
else if(!IsRxz(str[j])&&!Isnum(str[j]))
{
pushchar(s,str[j]);
j++;
}

else if(Isysf(str[j]))
{
tc=popchar(s);
pushchar(s,tc);
Cmpysf(str[j],tc);
if(Cmpysf(str[j],tc))
YsStackdb(str[j],s);
else pushchar(s,str[j]);
j++;
}

else if(IsRxz(str[j]))//遇到右限制处理
{
if(str[j]==')')//遇到小括号
while((tc=popchar(s))!='(')
{
if(Isysf(tc))
{
xy=popchar(s);
pushchar(s,xy);
if(Isysf(xy))
{
if(Cmpysf(tc,xy))
YsStackdb(tc,s);
else pushchar(s,tc);
}
j++;
}
else
{
printf("中缀表达式格式错误！");
exit(0);
}
}
if(str[j]==']')//遇到中括号
while((tc=popchar(s))!='[')
{
if(Isysf(tc))
{
xy=popchar(s);
pushchar(s,xy);
if(Isysf(xy))
{
if(Cmpysf(tc,xy))
YsStackdb(tc,s);
else pushchar(s,tc);
}
j++;
}
else
{
printf("中缀表达式格式错误！");
exit(0);
}
}
if(str[j]=='}')//遇到大括号
while((tc=popchar(s))!='{')
{
if(Isysf(tc))
{
xy=popchar(s);
pushchar(s,xy);
if(Isysf(xy))
{
if(Cmpysf(tc,xy))
YsStackdb(tc,s);
else pushchar(s,tc);
}
j++;
}
else
{
printf("中缀表达式格式错误！");
exit(0);
}
}
}
else
{
printf("中缀表达式格式错误！");
exit(0);
}

}
if(--(s->topdb)==s->bottomdb)
return popdb(s);
else return 0;
``````

}

/*全部完整程序*/

#include
#include
#include
#include

#define STACKSIZE 100
/*运算符优先级数据结构*/
struct Yxsz
{
char ysf;
int yxj;
}
ysz[]={{'(',6},{')',0},{'[',6},{']',1},{'{',6},{'}',2},{'#',3},{'^',3},{'*',4},{'/',4},{'+',5},{'-',5}};

/*char类型与double类型的双栈结构*/
typedef struct
{
char *topchar;
char *bottomchar;
int charStackSize;
double *topdb;
double *bottomdb;
int doubleStackSize;
}stack;

/*初始化栈*/
void initstack(stack s)
{
s->bottomchar=(char
)malloc(STACKSIZE*sizeof(char));
if(!s->bottomchar)
exit(0);
s->topchar=s->bottomchar;
s->charStackSize=STACKSIZE;
s->bottomdb=(double *)malloc(STACKSIZE*sizeof(double));
if(!s->bottomdb)
exit(0);
s->topdb=s->bottomdb;
s->doubleStackSize=STACKSIZE;
}

/*字符入栈*/
void pushchar(stack s,char a)
{
if(s->topchar-s->bottomchar>=STACKSIZE)
{
s->bottomchar=(char
if(!s->bottomchar)
exit(0);
}
*(s->topchar)=a;
s->topchar++;
}

/*数字入栈*/
void pushdb(stack *s,double b)
{
if(s->topdb-s->bottomdb>=STACKSIZE)
{
if(!s->bottomdb)
exit(0);
}
*(s->topdb)=b;
s->topdb++;
}

/*字符出栈*/
char popchar(stack s)
{
char i;
if(!s&&s->topchar==s->bottomchar)
exit(0);
i=
(--s->topchar);
return i;
}

/*数字出栈*/
double popdb(stack s)
{
double i;
if(!s&&s->topdb==s->bottomdb)
exit(0);
i=
(--s->topdb);
return i;
}

/*清空栈*/
int Cealenstack(stack *s)
{
if(!s)
return 0;
s->topchar=s->bottomchar;
s->topdb=s->bottomdb;
return 1;

}

/*销毁栈*/
void Destorystack(stack *s)
{
int lenchar=stackcharLen(s),lendb=stackdblen(s);

``````if(!s)
exit(0);
while(lenchar)
{
*(--s->topchar)=NULL;
lenchar--;
}
while(lendb)
{
*(--s->topdb)=0;
lendb--;
}
``````

}

/*计算字符栈长度*/
int stackcharLen(stack *s)
{
return(s->topchar-s->bottomchar);
}

/*计算数字栈长度*/
int stackdblen(stack *s)
{
return (s->topdb-s->bottomdb);
}

/*以下为程序核心*/

/*将中缀字符串转换成后缀然后求值这个函数有点复杂，定义在主函数下面*/
double Nibolansuanfa(char *str,stack *s);

/*字符是右限制符号*/
int IsRxz(char i)
{
if(i==')'||i==']'||i=='}')
return 1;
else return 0;
}
/*字符是运算符*/
int Isysf(char i)
{
if(i=='*'||i=='/'||i=='^'||i=='#'||i=='+'||i=='-')
return 1;
else return 0;
}

/*字符是数字字符*/
int Isnum(char i)
{
if(i>='0'&&i<='9'||i=='.')
return 1;
else return 0;
}

/*比较栈里上下两个运算符的优先级如果前一个优先级比后一个大或者同级返回前一个字符，别的返回0*/
char Cmpysf(char a,char b)
{
int j=0,i=0;
while(ysz[j].ysf!=a)
j++;
while(ysz[i].ysf!=b)
i++;
if(ysz[j].yxj<=ysz[i].yxj)
return a;
else return 0;
}

/*遇到运算符直接在数字栈里面处理并计算*/
void YsStackdb(char i,stack s)
{
int k,j;
switch(i)
{
case '#':
k=popdb(s);
j=popdb(s);
pushdb(s,pow(j,1.0/k));
break;
case '^':
k=popdb(s);
j=popdb(s);
pushdb(s,pow(j,k));
break;
case'
':
k=popdb(s);
j=popdb(s);
pushdb(s,j*k);
break;
case'/':
k=popdb(s);
j=popdb(s);
pushdb(s,j/k);
break;
case'+':
k=popdb(s);
j=popdb(s);
pushdb(s,j+k);
break;
case'-':
k=popdb(s);
j=popdb(s);
pushdb(s,j-k);
break;
}
return;
}

/*主函数*/
int main(void)
{
stack *sk;
char str[100];
printf("请输入一个中缀表达式:");
scanf("%s",str);
printf("结果:%lf\n",Nibolansuanfa(str,sk));
return 0;
}

/*核心函数*/
double Nibolansuanfa(char *str,stack *s)
{
initstack(&s);//初始化栈
char st[20],tc,xy;//st[20]里面放数字字符串
int j=0,i=0,yxcount=0;
double d;
while(str[j]!='\0')
{

``````/*数字字符拷贝*/
if(Isnum(str[i]))
{
while(Isnum(str[i]))
{
st[i]=str[j];//将数字字符串放到st数组
i++;
j++;
}
/*数字字符转换并进数字栈*/
i=0;
d=atof(st);
pushdb(s,d);
st[20]=0;
continue;
}
/*非数字字符进字符栈*/
else if(!IsRxz(str[j])&&!Isnum(str[j]))
{
pushchar(s,str[j]);
j++;
}

else if(Isysf(str[j]))
{
tc=popchar(s);
pushchar(s,tc);
Cmpysf(str[j],tc);
if(Cmpysf(str[j],tc))
YsStackdb(str[j],s);
else pushchar(s,str[j]);
j++;
}

else if(IsRxz(str[j]))//遇到右限制处理
{
if(str[j]==')')//遇到小括号
while((tc=popchar(s))!='(')
{
if(Isysf(tc))
{
xy=popchar(s);
pushchar(s,xy);
if(Isysf(xy))
{
if(Cmpysf(tc,xy))
YsStackdb(tc,s);
else pushchar(s,tc);
}
j++;
}
else
{
printf("中缀表达式格式错误！");
exit(0);
}
}
if(str[j]==']')//遇到中括号
while((tc=popchar(s))!='[')
{
if(Isysf(tc))
{
xy=popchar(s);
pushchar(s,xy);
if(Isysf(xy))
{
if(Cmpysf(tc,xy))
YsStackdb(tc,s);
else pushchar(s,tc);
}
j++;
}
else
{
printf("中缀表达式格式错误！");
exit(0);
}
}
if(str[j]=='}')//遇到大括号
while((tc=popchar(s))!='{')
{
if(Isysf(tc))
{
xy=popchar(s);
pushchar(s,xy);
if(Isysf(xy))
{
if(Cmpysf(tc,xy))
YsStackdb(tc,s);
else pushchar(s,tc);
}
j++;
}
else
{
printf("中缀表达式格式错误！");
exit(0);
}
}
}
else
{
printf("中缀表达式格式错误！");
exit(0);
}

}
if(--(s->topdb)==s->bottomdb)
return popdb(s);
else return 0;
``````

}