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