數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式我們?cè)跀?shù)學(xué)中常見的計(jì)算式，例如2+（3*4）叫做中綴表達(dá)式。表達(dá)式中涉及到了多個(gè)運(yùn)算符，而運(yùn)算符之間是有優(yōu)先級(jí)的。計(jì)算機(jī)在計(jì)算并且處理這種表達(dá)式時(shí)，需要將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，然后再進(jìn)行計(jì)算。中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式遵循以下原則：1.遇到操作數(shù)，直接輸出；2.棧為空時(shí)，遇到運(yùn)算符，入棧；3.遇到左括號(hào)，將其入棧；4.遇到右括號(hào)，執(zhí)行出棧操作，并將出棧的元素輸出，直到彈出棧的是左括號(hào)，左括號(hào)不輸出；5.遇到其他運(yùn)算符'+''-''*''/'時(shí)，彈出所有優(yōu)先級(jí)大于或等于該運(yùn)算符的棧頂元素，然后將該運(yùn)算符入棧；6.最終將棧中的元素依次出棧，輸出。經(jīng)過上面的步驟，得到的輸出既是轉(zhuǎn)換得到的后綴表達(dá)式。舉例：a+b*c+(d*e+f)*g--------->abc*+de*f+g*+遇到a，直接輸出：遇到+，此時(shí)棧為空，入棧：數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第1頁。遇到b，直接輸出：數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第1頁。遇到*,優(yōu)先級(jí)大于棧頂符號(hào)優(yōu)先級(jí)，入棧：遇到c，輸出：遇到+，目前站內(nèi)的*與+優(yōu)先級(jí)都大于或等于它，因此將棧內(nèi)的*，+依次彈出并且輸出，并且將遇到的這個(gè)+入棧：數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第2頁。數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第2頁。遇到d，直接輸出：遇到*，由于*的優(yōu)先級(jí)高于處在棧中的(，因此*入棧：遇到e，直接輸出：數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第3頁。數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第3頁。遇到f，直接輸出：遇到),彈出棧頂元素并且輸出，直到彈出(才結(jié)束，在這里也就是彈出+輸出，彈出(不輸出：遇到*，優(yōu)先級(jí)高于棧頂+，將*入棧：數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第4頁。數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第4頁。此時(shí)已經(jīng)沒有新的字符了，依次出棧并輸出操作直到棧為空：明白了這個(gè)過程，現(xiàn)在就需要用代碼實(shí)現(xiàn)了。對(duì)于各種運(yùn)算符的優(yōu)先級(jí)，可以使用整數(shù)來表示運(yùn)算符的級(jí)別?？梢远x一個(gè)函數(shù)來返回各種符號(hào)的優(yōu)先級(jí)數(shù)字：/******************************************************************根據(jù)字符該字符是否在棧中，返回該字符的優(yōu)先級(jí)。*這里只處理+、-、*、/、(、)這些符號(hào)。*需要注意的是：如果(在棧中，它的優(yōu)先級(jí)是最低的，不在棧中則是最高的*@paramc:需要判斷的字符*@paramflag:字符是否在棧中，0表示在棧中，1表示不在棧中*****************************************************************/intGetPrecedence(charc,intflag){ if(c=='+'||c=='-') { return1; } elseif(c=='*'||c=='/') { return2; } elseif(c=='('&&flag==0) {數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第5頁。數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第5頁。 } elseif(c=='('&&flag==1) { return3; } else { fprintf(stderr,"Inputcharisinvalid!\n"); return-1; }}/*****************************************************************判斷一個(gè)字符是不是運(yùn)算符*如果是合法的運(yùn)算符+、-、*、/、(、)則返回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;數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第6頁。數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第6頁。intIsEmpty(StackS);StackCreateStack();voidDisposeStack(StackS);voidMakeEmpty(StackS);voidPush(ElementTypeX,StackS);ElementTypeTop(StackS);voidPop(StackS);//判斷棧是否為空intIsEmpty(StackS){ returnS->Next==NULL;}//創(chuàng)建鏈棧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); } }}//進(jìn)棧數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第7頁。voidP數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第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; }}數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第8頁。/**數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第8頁。*根據(jù)字符該字符是否在棧中，返回該字符的優(yōu)先級(jí)。*這里只處理+、-、*、/、(、)這些符號(hào)。*需要注意的是：如果(在棧中，它的優(yōu)先級(jí)是最低的，不在棧中則是最高的*@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; }}/*****************************************************************判斷一個(gè)字符是不是運(yùn)算符*如果是合法的運(yùn)算符+、-、*、/、(、)則返回0，否則返回1****************************************************************/intIsOperator(charc){ if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')') { return0; } else {數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第9頁。數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第9頁。 }}charOutput[50];//中綴表達(dá)式轉(zhuǎn)成后綴表達(dá)式char*InfixToPostfix(char*ch,StackS){ intindex=0; charc; while((c=*ch)!='\0') { //不是運(yùn)算符，將該字符放進(jìn)輸出字符數(shù)組中。 if(IsOperator(c)==1) { Output[index++]=c; ch++; } //是運(yùn)算符 else { //如果此時(shí)棧為空，運(yùn)算符進(jìn)棧 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 {數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第10頁。 intoutPrecedence=GetPrecedence(c,1);數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式全文共11頁，當(dāng)前為第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