重学数据结构006——中缀表达式转后缀表达式

我们在数学中常见的计算式，例如2+（3*4）叫做中缀表达式。表达式中涉及到了多个运算符，而运算符之间是有优先级的。计算机在计算并且处理这种表达式时，需要将中缀表达式转换成后缀表达式，然后再进行计算。

中缀表达式转后缀表达式遵循以下原则：

1.遇到操作数，直接输出；

2.栈为空时，遇到运算符，入栈；

3.遇到左括号，将其入栈；

4.遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出；

5.遇到其他运算符'+''-''*''/'时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈；

6.最终将栈中的元素依次出栈，输出。

经过上面的步骤，得到的输出既是转换得到的后缀表达式。

举例：a+b*c+(d*e+f)*g ---------> abc*+de*f+g*+

遇到a，直接输出：

遇到+，此时栈为空，入栈：

遇到b，直接输出：

遇到*,优先级大于栈顶符号优先级，入栈：

遇到c，输出：

遇到+，目前站内的*与+优先级都大于或等于它，因此将栈内的*，+依次弹出并且输出，并且将遇到的这个+入栈：

遇到(,将其入栈：

遇到d，直接输出：

遇到*，由于*的优先级高于处在栈中的(，因此*入栈：

遇到e，直接输出：

遇到+，栈顶的*优先级高于+，但是栈内的(低于+，将*出栈输出，+入栈：

遇到f，直接输出：

遇到),弹出栈顶元素并且输出，直到弹出(才结束，在这里也就是弹出+输出，弹出(不输出：

遇到*，优先级高于栈顶+，将*入栈：

遇到g，直接输出：

此时已经没有新的字符了，依次出栈并输出操作直到栈为空：

明白了这个过程，现在就需要用代码实现了。对于各种运算符的优先级，可以使用整数来表示运算符的级别。可以定义一个函数来返回各种符号的优先级数字：

/*****************************************************************
*根据字符该字符是否在栈中，返回该字符的优先级。
*这里只处理+、-、*、/、(、)这些符号。
*需要注意的是：如果(在栈中，它的优先级是最低的，不在栈中则是最高的
*@paramc:需要判断的字符
*@paramflag:字符是否在栈中，0表示在栈中，1表示不在栈中
*****************************************************************/
intGetPrecedence(charc,intflag)
{
if(c=='+'||c=='-')
{
return1;
}
elseif(c=='*'||c=='/')
{
return2;
}
elseif(c=='('&&flag==0)
{
return0;
}
elseif(c=='('&&flag==1)
{
return3;
}
else
{
fprintf(stderr,"Inputcharisinvalid!\n");
return-1;
}
}

还可以定义一个函数来判断当前遇到的是运算符还是操作数：

/****************************************************************
*判断一个字符是不是运算符
*如果是合法的运算符+、-、*、/、(、)则返回0，否则返回1
****************************************************************/
intIsOperator(charc)
{
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')')
{
return0;
}
else
{
return1;
}
}

完整代码：

#include<stdio.h>
#include<stdlib.h>
#defineElementTypechar

typedefstructNode*PtrToNode;
typedefPtrToNodeStack;
typedefstructNode
{
ElementTypeElement;
PtrToNodeNext;
};

intIsEmpty(StackS);
StackCreateStack();
voidDisposeStack(StackS);
voidMakeEmpty(StackS);
voidPush(ElementTypeX,StackS);
ElementTypeTop(StackS);
voidPop(StackS);

//判断栈是否为空
intIsEmpty(StackS)
{
returnS->Next==NULL;
}
//创建链栈
StackCreateStack()
{
StackS=malloc(sizeof(structNode));
if(S==NULL)
{
printf("Noenoughmemory!");
returnNULL;
}
S->Next=NULL;
MakeEmpty(S);
returnS;
}
//清空栈
voidMakeEmpty(StackS)
{
if(S==NULL)
{
printf("UseCreateStackFirst!");
}
else
{
while(!IsEmpty(S))
{
Pop(S);
}
}
}
//进栈
voidPush(ElementTypeX,StackS)
{
PtrToNodeTmp;
Tmp=malloc(sizeof(structNode));
if(Tmp!=NULL)
{
Tmp->Element=X;
Tmp->Next=S->Next;
S->Next=Tmp;
}
else
{
printf("Outofspace!");
}
}
//出栈
voidPop(StackS)
{

if(IsEmpty(S))
{
printf("TheStackisEmpty!");
}
else
{
PtrToNodeTmp=S->Next;
S->Next=Tmp->Next;
free(Tmp);
}
}
//返回栈顶元素
ElementTypeTop(StackS)
{
if(IsEmpty(S))
{
printf("Thestackisempty!");
return0;
}
else
{
returnS->Next->Element;
}
}

/*****************************************************************
*根据字符该字符是否在栈中，返回该字符的优先级。
*这里只处理+、-、*、/、(、)这些符号。
*需要注意的是：如果(在栈中，它的优先级是最低的，不在栈中则是最高的
*@paramc:需要判断的字符
*@paramflag:字符是否在栈中，0表示在栈中，1表示不在栈中
*****************************************************************/
intGetPrecedence(charc,intflag)
{
if(c=='+'||c=='-')
{
return1;
}
elseif(c=='*'||c=='/')
{
return2;
}
elseif(c=='('&&flag==0)
{
return0;
}
elseif(c=='('&&flag==1)
{
return3;
}
else
{
fprintf(stderr,"Inputcharisinvalid!\n");
return-1;
}
}

/****************************************************************
*判断一个字符是不是运算符
*如果是合法的运算符+、-、*、/、(、)则返回0，否则返回1
****************************************************************/
intIsOperator(charc)
{
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')')
{
return0;
}
else
{
return1;
}
}

charOutput[50];
//中缀表达式转成后缀表达式
char*InfixToPostfix(char*ch,StackS)
{

intindex=0;
charc;
while((c=*ch)!='\0')
{
//不是运算符，将该字符放进输出字符数组中。
if(IsOperator(c)==1)
{
Output[index++]=c;
ch++;
}
//是运算符
else
{
//如果此时栈为空，运算符进栈
if(IsEmpty(S))
{
Push(c,S);
ch++;
continue;
}
else
{
if(c==')')
{
while(!IsEmpty(S)&&Top(S)!='(')
{
Output[index++]=Top(S);
Pop(S);
}
Pop(S);
ch++;
continue;
}
else
{
intoutPrecedence=GetPrecedence(c,1);
while(!IsEmpty(S)&&GetPrecedence(Top(S),0)>=outPrecedence)
{
Output[index++]=Top(S);
Pop(S);
}
Push(c,S);
ch++;
continue;
}
}
}
}
while(!IsEmpty(S))
{
Output[index++]=Top(S);
Pop(S);
}
Output[index]='\0';
returnOutput;
}



intmain(void)
{
StackS=CreateStack();
char*charSequence="1+2*3+(4*5+6)*7";
chartmp;
char*out=InfixToPostfix(charSequence,S);


while((tmp=*out)!='\0')
{
printf("%c",tmp);
out++;
}
printf("\n");
return0;
}