数据结构之中缀表达式转后缀表达式

数据结构之中缀表达式转后缀表达式我们在数学中常见的计算式，例如2+（3*4）叫做中缀表达式。表达式中涉及到了多个运算符，而运算符之间是有优先级的。计算机在计算并且处理这种表达式时，需要将中缀表达式转换成后缀表达式，然后再进行计算。中缀表达式转后缀表达式遵循以下原则：1.遇到操作数，直接输出；2.栈为空时，遇到运算符，入栈；3.遇到左括号，将其入栈；4.遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出；5.遇到其他运算符'+''-''*''/'时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈；6.最终将栈中的元素依次出栈，输出。经过上面的步骤，得到的输出既是转换得到的后缀表达式。举例：a+b*c+(d*e+f)*g--------->abc*+de*f+g*+遇到a，直接输出：遇到+，此时栈为空，入栈：数据结构之中缀表达式转后缀表达式全文共11页，当前为第1页。遇到b，直接输出：数据结构之中缀表达式转后缀表达式全文共11页，当前为第1页。遇到*,优先级大于栈顶符号优先级，入栈：遇到c，输出：遇到+，目前站内的*与+优先级都大于或等于它，因此将栈内的*，+依次弹出并且输出，并且将遇到的这个+入栈：数据结构之中缀表达式转后缀表达式全文共11页，当前为第2页。数据结构之中缀表达式转后缀表达式全文共11页，当前为第2页。遇到d，直接输出：遇到*，由于*的优先级高于处在栈中的(，因此*入栈：遇到e，直接输出：数据结构之中缀表达式转后缀表达式全文共11页，当前为第3页。数据结构之中缀表达式转后缀表达式全文共11页，当前为第3页。遇到f，直接输出：遇到),弹出栈顶元素并且输出，直到弹出(才结束，在这里也就是弹出+输出，弹出(不输出：遇到*，优先级高于栈顶+，将*入栈：数据结构之中缀表达式转后缀表达式全文共11页，当前为第4页。数据结构之中缀表达式转后缀表达式全文共11页，当前为第4页。此时已经没有新的字符了，依次出栈并输出操作直到栈为空：明白了这个过程，现在就需要用代码实现了。对于各种运算符的优先级，可以使用整数来表示运算符的级别。可以定义一个函数来返回各种符号的优先级数字：/******************************************************************根据字符该字符是否在栈中，返回该字符的优先级。*这里只处理+、-、*、/、(、)这些符号。*需要注意的是：如果(在栈中，它的优先级是最低的，不在栈中则是最高的*@paramc:需要判断的字符*@paramflag:字符是否在栈中，0表示在栈中，1表示不在栈中*****************************************************************/intGetPrecedence(charc,intflag){ if(c=='+'||c=='-') { return1; } elseif(c=='*'||c=='/') { return2; } elseif(c=='('&&flag==0) {数据结构之中缀表达式转后缀表达式全文共11页，当前为第5页。数据结构之中缀表达式转后缀表达式全文共11页，当前为第5页。 } 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>#defineElementTypechartypedefstructNode*PtrToNode;typedefPtrToNodeStack;typedefstructNode{ ElementTypeElement; PtrToNodeNext;数据结构之中缀表达式转后缀表达式全文共11页，当前为第6页。数据结构之中缀表达式转后缀表达式全文共11页，当前为第6页。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); } }}//进栈数据结构之中缀表达式转后缀表达式全文共11页，当前为第7页。voidP数据结构之中缀表达式转后缀表达式全文共11页，当前为第7页。{ 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; }}数据结构之中缀表达式转后缀表达式全文共11页，当前为第8页。/**数据结构之中缀表达式转后缀表达式全文共11页，当前为第8页。*根据字符该字符是否在栈中，返回该字符的优先级。*这里只处理+、-、*、/、(、)这些符号。*需要注意的是：如果(在栈中，它的优先级是最低的，不在栈中则是最高的*@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 {数据结构之中缀表达式转后缀表达式全文共11页，当前为第9页。数据结构之中缀表达式转后缀表达式全文共11页，当前为第9页。 }}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 {数据结构之中缀表达式转后缀表达式全文共11页，当前为第10页。 intoutPrecedence=GetPrecedence(c,1);数据结构之中缀表达式转后缀表达式全文共11页，当前为第10页。 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){ Stac