棧的應(yīng)用：表達(dá)式求值1

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)一：表達(dá)式求值》實(shí)驗(yàn)報(bào)告一、簡(jiǎn)介要求設(shè)計(jì)一個(gè)表達(dá)式求值的程序。該程序必須可以接受包含〔，〕，+，-，*，/，%，和^〔求冪運(yùn)算符，a^b=ab〕的中綴表達(dá)式，并求出結(jié)果。如果表達(dá)式正確，那么輸出表達(dá)式的結(jié)果；如果表達(dá)式非法，那么輸出錯(cuò)誤信息。輸入要求：程序從“input.txt”文件中讀取信息，在這個(gè)文件中如果有多個(gè)中綴表達(dá)式，那么每個(gè)表達(dá)式獨(dú)占一行，程序的讀取操作在文件的結(jié)尾處停止。輸出要求：對(duì)于每一個(gè)表達(dá)式，將其結(jié)果放在“output.txt”文件的每一行中。這些結(jié)果可能是值〔精確到小數(shù)點(diǎn)后兩位〕，也可能是錯(cuò)誤信息“ERRORININFIXNOTATION”。輸入例子：1+2+3-44.99+5.99+6.99*1.062^2.5^3(5.6-2)%35%(3.2-2.1)+1輸出例子：2.0018.3950535.16Errorininfixnotation.Errorininfixnotation.Errorininfixnotation.輸入的表達(dá)式是由操作數(shù)和運(yùn)算符以及改變運(yùn)算順序的圓括號(hào)連接而成的式子。由于不同的運(yùn)算符間存在優(yōu)先級(jí)，同一優(yōu)先級(jí)的運(yùn)算間又存在著運(yùn)算結(jié)合順序的問(wèn)題〔即左結(jié)合，還是右結(jié)合〕，所以簡(jiǎn)單的從左到右計(jì)算是不充分的。而后綴表達(dá)式〔后綴表達(dá)式是由一系列的運(yùn)算符、操作數(shù)組成，其中運(yùn)算符位于兩個(gè)操作數(shù)之后，如123*+〕那么很容易通過(guò)應(yīng)用棧實(shí)現(xiàn)表達(dá)式的計(jì)算，所以，我們要先把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，再進(jìn)行計(jì)算。二、算法說(shuō)明a、定義一個(gè)棧存放運(yùn)算符，將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式。根本過(guò)程如下：如果遇到空格，那么認(rèn)為是分隔符，不需處理。如遇到操作數(shù)，那么直接輸出。假設(shè)遇到左括號(hào)，那么將其壓入棧中。假設(shè)是遇到右括號(hào)，說(shuō)明括號(hào)的中綴表達(dá)式已經(jīng)掃描完畢，把括號(hào)中的運(yùn)算符退棧，并輸出。假設(shè)遇到是運(yùn)算符，當(dāng)該運(yùn)算符的優(yōu)先級(jí)別大于棧頂運(yùn)算符的優(yōu)先級(jí)別時(shí)，那么將它壓棧；當(dāng)該運(yùn)算符的優(yōu)先級(jí)別小于棧頂運(yùn)算符的優(yōu)先級(jí)別時(shí)，那么將棧頂運(yùn)算符退棧并輸出，再次比擬新的棧頂運(yùn)算符，按同樣方法處理，直到該運(yùn)算符大于棧頂運(yùn)算符的優(yōu)先級(jí)為止，然后將該運(yùn)算符壓棧。假設(shè)中綴表達(dá)式處理完畢，那么要把棧中存留的運(yùn)算符一并輸出。其中，不同運(yùn)算符優(yōu)先級(jí)的設(shè)置可以用一個(gè)數(shù)來(lái)代表其優(yōu)先級(jí)，優(yōu)先級(jí)越高，數(shù)值就越大。程序中，加減運(yùn)算符的優(yōu)先級(jí)是1，乘除法和取模運(yùn)算符的優(yōu)先級(jí)是2，求冪運(yùn)算符的優(yōu)先級(jí)是3，右括號(hào)是5，左括號(hào)是6，其他為0。運(yùn)算符優(yōu)先級(jí)關(guān)系如表1-1。.b、轉(zhuǎn)化后，用棧實(shí)現(xiàn)后綴表達(dá)式的計(jì)算。其根本過(guò)程是：當(dāng)輸入一個(gè)操作數(shù)時(shí)，它被壓入棧中，當(dāng)一個(gè)運(yùn)算符出現(xiàn)時(shí)，就從棧中彈出適當(dāng)數(shù)量的操作數(shù)，對(duì)該運(yùn)算進(jìn)行計(jì)算，計(jì)算結(jié)果再壓入棧中。對(duì)于常見(jiàn)的二元運(yùn)算符來(lái)說(shuō)，彈出的操作數(shù)只有兩個(gè)。處理完整個(gè)后綴表達(dá)式之后，棧頂上的元素就是表達(dá)式的結(jié)果值。整個(gè)計(jì)算過(guò)程不需要理解運(yùn)算的優(yōu)先級(jí)規(guī)那么。表1-1運(yùn)算符優(yōu)先級(jí)關(guān)系表+-*/()^+==<<<<<-==<<<<<*>>==<<</>>==<<<(>>>>=>>)>>>><=>^>>>><<=程序的整體算法過(guò)程分兩步：第一步，從“input.txt”文件中讀取中綴表達(dá)式，并應(yīng)用運(yùn)算符棧OpHolder把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，將輸出結(jié)果〔轉(zhuǎn)換后得到的后綴表達(dá)式〕存放在一個(gè)temp文件中。第二步，從temp文件中讀取后綴表達(dá)式，并應(yīng)用操作數(shù)棧Operands計(jì)算后綴表達(dá)式結(jié)果，將結(jié)果輸出到“output.txt”文件中。對(duì)于求冪運(yùn)算要特別注意，例如2^3^3要變成223^，因?yàn)榍髢邕\(yùn)算符是從右到左結(jié)合的。本程序中的棧采用前面所述的帶頭結(jié)點(diǎn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，涉及兩種類(lèi)型：用于存儲(chǔ)運(yùn)算符號(hào)的char類(lèi)型的鏈棧以及用于存儲(chǔ)操作數(shù)的float類(lèi)型的鏈棧。Char類(lèi)型的?！癢hereat”用來(lái)記錄后綴表達(dá)式中操作數(shù)和運(yùn)算符號(hào)的順序，以及決定需要多少次運(yùn)算。其中以A=Operand,B=Operator區(qū)分〔例如1+2轉(zhuǎn)換成12+，再Whereat中的形式應(yīng)該是AAB〕。三、測(cè)試結(jié)果四、結(jié)果分析與總結(jié)該程序包括了許多可能出現(xiàn)的情況。測(cè)試包括正確的表達(dá)式，錯(cuò)誤的表達(dá)式。因本程序曾加了輸出分類(lèi)局部，所以輸出的結(jié)果包括了運(yùn)算符錯(cuò)誤，操作數(shù)錯(cuò)誤，其他錯(cuò)誤。附錄：源代碼/*將中綴表帶式轉(zhuǎn)換為后綴表達(dá)式*/voidConvertToPost(FILE*In,StackWhereat,FILE*Temp){ StackOpHolder; charholder; charlastseen; intdigitcounter=0;//操作數(shù)的計(jì)數(shù)器 OpHolder=(PtrToNode)malloc(sizeof(structNode));//初始化 OpHolder->Next=NULL; holder=getc(In);//讀入 lastseen='@';//用來(lái)防止輸入格式錯(cuò)誤，例如兩個(gè)小數(shù)點(diǎn) putc('',Temp); while((holder!='\n')&&(holder!=EOF)){ if(holder=='')//空字符，跳過(guò){ digitcounter=0;//操作數(shù)計(jì)數(shù)器記0 } elseif(IsOperator(holder)==-1)//如果holder不是操作數(shù)或運(yùn)算符號(hào){ PrintError=3; //其他錯(cuò)誤 } elseif(IsOperator(holder)==0)//如果holder是操作數(shù){ if((lastseen==holder)&&(lastseen=='.'))//錯(cuò)誤處理{ PrintError=2; //操作數(shù)出錯(cuò) } else lastseen=holder; if(digitcounter==0){ Push('A',Whereat);//進(jìn)棧 digitcounter++; //計(jì)數(shù)器加一 putc('',Temp); } putc(holder,Temp);//將holder放入Temp文件 } else{ digitcounter=0; if((lastseen==holder)&&(lastseen!='(')&&(lastseen!=')')){//"("情況特殊對(duì)待PrintError=1;//運(yùn)算符出錯(cuò)} else lastseen=holder; if(IsEmpty(OpHolder)==1)//當(dāng)OpHolder為空{(diào) Push(holder,OpHolder);//將holder進(jìn)到棧OpHolder } elseif(OperatorValue(Top(OpHolder))==6)//OpHolder是"("的情況{ if(OperatorValue(holder)==5)//holder是")"的情況 Pop(OpHolder);//彈棧 else Push(holder,OpHolder); } elseif(OperatorValue(holder)==6)//holder是"〔"的情況{ Push(holder,OpHolder); } elseif(OperatorValue(holder)==5){//OpHolder是")"的情況 while((IsEmpty(OpHolder)!=1)&&(OperatorValue(Top(OpHolder))!=6)) { putc('',Temp); Push('B',Whereat);//B進(jìn)棧 putc(Top(OpHolder),Temp); Pop(OpHolder); } if(IsEmpty(OpHolder)==1)//錯(cuò)誤處理,括號(hào)不匹配{ PrintError=1; } else Pop(OpHolder); } elseif((OperatorValue(holder)==OperatorValue(Top(OpHolder))) &&(OperatorValue(holder)==3))//冪運(yùn)算情況{ Push(holder,OpHolder); } elseif((OperatorValue(holder)<OperatorValue(Top(OpHolder))) &&OperatorValue(Top(OpHolder))==3)//冪運(yùn)算情況{ putc('',Temp); Push('B',Whereat); putc(Top(OpHolder),Temp); Pop(OpHolder); while((IsEmpty(OpHolder)!=1)&&(OperatorValue(Top(OpHolder))==3)) { Push('B',Whereat); putc('',Temp); putc(Top(OpHolder),Temp); Pop(OpHolder); } Push(holder,OpHolder); }//如果當(dāng)前運(yùn)算符號(hào)的優(yōu)先級(jí)小于或者等于堆棧中的運(yùn)算符號(hào)的優(yōu)先級(jí),那么將其放入temp中，并且將堆棧中的運(yùn)算符號(hào)出棧，放入temp中，直到堆棧為空或者優(yōu)先級(jí)小于堆棧頂元素的優(yōu)先級(jí) elseif(OperatorValue(Top(OpHolder))>=OperatorValue(holder)){//棧不空且左括號(hào)外的棧頂優(yōu)先級(jí)大于holder優(yōu)先級(jí)while((IsEmpty(OpHolder)!=1)&&(OperatorValue(Top(OpHolder))>=OperatorValue(holder)) &&(OperatorValue(Top(OpHolder))!=6)) { putc('',Temp); putc(Top(OpHolder),Temp); Push('B',Whereat); Pop(OpHolder); } Push(holder,OpHolder); } elseif(OperatorValue(Top(OpHolder))<OperatorValue(holder)){//如果當(dāng)前運(yùn)算符號(hào)的優(yōu)先級(jí)大于堆棧中的運(yùn)算符號(hào)的優(yōu)先級(jí),那么將其壓入堆棧中Push(holder,OpHolder); } } holder=getc(In); //繼續(xù)讀入 } //While循環(huán)結(jié)束 while(IsEmpty(OpHolder)!=1){//最后如果堆棧中還有運(yùn)算符號(hào)，那么一并放到temp中 Push('B',Whereat); putc('',Temp); putc(Top(OpHolder),Temp); Pop(OpHolder); } MakeEmpty(OpHolder);//使?？?free(OpHolder);//釋放棧}/*計(jì)算后綴表達(dá)式*/voidCalculate(FILE*Change,StackWhereat,FILE*Temp){ FStackOperands; floatlooker; charOp; charspacefinder; floatanswer=0; floatNumA; floatNumB; Operands=(Ptr_Fn)malloc(sizeof(structFNode)); Operands->Next=NULL; while((IsEmpty(Whereat)!=1)&&PrintError==0){//循環(huán)直到Whereat空，或者遇到錯(cuò)誤 if(Top(Whereat)=='A'){ fscanf(Temp,"",&spacefinder); fscanf(Temp,"%f",&looker); //如果是A,那么是操作數(shù) FPush(looker,Operands); //將浮點(diǎn)數(shù)放入Operands Pop(Whereat); } elseif(Top(Whereat)=='B')//如果是B,那么是運(yùn)算符{ fscanf(Temp,"",&spacefinder); Op=getc(Temp); switch(Op) { //判斷是什么運(yùn)算符 case('^')://冪運(yùn)算 NumB=FTop(Operands); FPop(Operands); if(FIsEmpty(Operands))//錯(cuò)誤處理{ PrintError=3; } else{ NumA=FTop(Operands); FPop(Operands); if((NumA==0&&NumB<0)||((NumA<0)&&(NumB-(int)NumB!=0))) {//其他字符 PrintError=2;//操作數(shù)錯(cuò)誤 } else{ answer=pow(NumA,NumB); FPush(answer,Operands); } } break; case'%'://取模運(yùn)算 NumB=FTop(Operands); FPop(Operands); if(FIsEmpty(Operands))//錯(cuò)誤處理{ PrintError=3; } else{ NumA=FTop(Operands); FPop(Operands); if((NumA-(int)NumA!=0)||(NumB-(int)NumB!=0) ||(NumB==0))//是整數(shù)或0 { PrintError=2; } else{ answer=(int)NumA%(int)NumB; //xmodb FPush(answer,Operands); } } break; case'*'://乘法運(yùn)算 NumB=FTop(Operands); FPop(Operands); if(FIsEmpty(Operands)){ PrintError=3; } else{ NumA=FTop(Operands); FPop(Operands); answer=NumA*NumB; //x*y FPush(answer,Operands); } break; case'/'://除法運(yùn)算 NumB=FTop(Operands); FPop(Operands); if(FIsEmpty(Operands)){ PrintError=3; } else{ NumA=FTop(Operands); FPop(Operands); if(NumB==0){ PrintError=2; //分母不為0 } else{ answer=(float)(NumA/NumB); //x/y FPush(answer,Operands); } } break; case'+'://加法運(yùn)算 NumB=FTop(Operands); FPop(Operands); if(FIsEmpty(Operands)){ PrintError=3; } else{ NumA=FTop(Operands); FPop(Operands); answer=NumA+NumB; //x+y FPush(answer,Operands); } break; case'-'://減法運(yùn)算 NumB=FTop(Operands); FPop(Operands); if(FIsEmpty(Operands)){ PrintError=3; } else{ NumA=FTop(Operands); FPo