栈:
中缀到后缀的转换。我们只允许操作+,*,(,)。
中缀表达式:a+b*c+(d*e+f)*g,后缀表达式:abc*+de*f+g*+
程序如下,stack.h如上篇博文中所示:
#include
#include
#include
#include"stack.h"
char*infix_to_postfix(char*str)
{
inti,j=0;
intSIZE=strlen(str);
if(str==NULL)
{
printf("emptystring!!!\n");
returnNULL;
}
Stacks=CreateStack(SIZE);
char*tmpstr=malloc(sizeof(char)*(SIZE+1));
if(tmpstr==NULL)
{
printf("tmpstrisempty!\n");
returnNULL;
}
for(i=0;i
{
if(str[i]=='+')
{
while(!IsEmpty(s)&&Top(s)!='(')
{
tmpstr[j++]=TopAndPop(s);
}
Push('+',s);
}
elseif(str[i]=='*')
{
while(!IsEmpty(s)&&Top(s)=='*')
{
tmpstr[j++]=TopAndPop(s);
}
Push('*',s);
}
elseif(str[i]=='(')
{
Push(str[i],s);
}
elseif(str[i]==')')
{
while(Top(s)!='(')
{
tmpstr[j++]=TopAndPop(s);
}
Pop(s);
}
else
{
tmpstr[j++]=str[i];
}
}
while(!IsEmpty(s))
{
tmpstr[j++]=TopAndPop(s);
}
returntmpstr;
}
intmain()
{
charss[]="a+b*c+(d*e+f)*g";
char*goal=infix_to_postfix(ss);
printf("thestringis:%s\n",goal);
return0;
}
在上面的程序中的if(str[i]=='+')语句后面加上如下两个语句并修改相应的*对应的else if语句,就可以在表达式中使用+,-,*,、,(,)了。
elseif(str[i]=='-')
{
while(!IsEmpty(s)&&Top(s)!='(')
{
tmpstr[j++]=TopAndPop(s);
}
Push('-',s);
}
elseif(str[i]=='/')
{
while(!IsEmpty(s)&&(Top(s)=='*'||Top(s)=='/'))
{
tmpstr[j++]=TopAndPop(s);
}
Push('/',s);
elseif(str[i]=='*')
{
while(!IsEmpty(s)&&(Top(s)=='*'||Top(s)=='/'))
{
tmpstr[j++]=TopAndPop(s);
}
Push('*',s);
}