數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用—表達(dá)式求值課程設(shè)計

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告專業(yè)計算機科學(xué)與技術(shù)學(xué)生姓名班級B計算機學(xué)號指導(dǎo)教師完成日期2012年1月11日一、簡介 棧是一種運算受限的線性表，僅允許在表的一端進(jìn)行插入和刪除。對一個棧最基本的操作包括進(jìn)棧和出棧，即對棧的插入和刪除。表達(dá)式求值是程序設(shè)計語言編譯中的一個基本問題，它的實現(xiàn)是棧應(yīng)用的一個典型例子。本實驗的目的是設(shè)計一個表達(dá)式求值的程序。該程序必須可以接受包括(,),+,-,*,/,%和(求冪運算符)的中綴表達(dá)式，并求出結(jié)果。如果表達(dá)式正確，則輸出表達(dá)式的結(jié)果；如果表達(dá)式非法，則輸出錯誤信息。輸入要求：程序從“input.txt”文件中讀取信息，在這個文件中如果有許多個中綴表達(dá)式，則每個表達(dá)

2、式獨占一行，程序的讀取操作在文件的結(jié)尾處停止。輸出要求：對于每一個表達(dá)式，將結(jié)果放在“output.txt”文件中每一行中。這個結(jié)果可能是值，也可能是錯誤信息“ERROR IN INFIX NOTATION”二、算法設(shè)計程序的整體算法分兩步：1、 從“input。txt”文件中讀取中綴表達(dá)式，并應(yīng)用運算符棧OpHolder把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，將結(jié)果存放在一個temp文件中。2、 從temp文件中讀取后綴表達(dá)式，并應(yīng)用操作數(shù)棧Operands計算后綴表達(dá)式結(jié)果將結(jié)果輸出到“output.txt”文件中。為了實現(xiàn)算法，使用兩個工作棧。一個稱做OpHolder，用于寄存運算符；另一個稱做O

3、perands，用以寄存操作數(shù)或運算結(jié)果。算法的基本思想是：首先置操作數(shù)棧為空棧，表達(dá)式起始符“#”為運算符棧的棧底元素；依次讀入表達(dá)式中每個字符，若是操作數(shù)則進(jìn)OPND棧，若是運算符則和OPTR棧的棧頂運算符比較優(yōu)先權(quán)后作相應(yīng)操作，直至整個表達(dá)式求值完畢。具體算法如下：OperandType EvaluateExpression()InitStack(Operands); Push(Operands,'#')；InitStack(Operands);c=getchar();While(c!='#'|GetTop(Operands)!='#')i

4、f(!In(c,OP)Push(Operands,c);c=getchar();elseswitch(Precede(GetTop(Operands),c)case'<':Push(Operands,c);c=getchar();breakcase'=':Pop(Operands,x); c=getchar();break;case'>':Pop(Operands,theta);Pop(Operands,b); Pop(Operands,a);Push(Operands),Operate(a,theta,b);berakreturn

5、GetTop(OPND);三、測試與結(jié)果設(shè)計針對程序的input.txt文件，并將運行結(jié)果與期望測試結(jié)果進(jìn)行比較 輸入數(shù)據(jù)： 輸出數(shù)據(jù)：測試項目測試實例期望測試結(jié)果基本測試3.00 3.00 1+2+3-42.00 1 + 23.00 4.99+5.99+6.99*1.0618.39 (3*5*(4+8)%2)0.00 223256.00 22.5350535.16 (2-4)3-8.00 擴(kuò)展測試2.5-3.4/2+1*22.80 (2.5)*(3-2)+5.6-190%32(1+1)-19.90 1+2+36.00 1*2*36.00 (1+2)*3+4/(5+1*4)+3.2612.70

6、 3+4-6.7+88.30 2.9*1.2+0.5-4%3/2+4(5-5)4.48 23-(5+2)/7*9-1.00 50-322+4%2-7*(3)-52.00 (2)-3）-1.00 2.526.25 2(4.4-2.4)4.00 2(4.4-3.1)2.46 (2-4)*3-8.00 2-4)(5-8)-0.13 容錯測試1+2(ERROR IN INFIX NOTATION2/0ERROR IN INFIX NOTATION2%0ERROR IN INFIX NOTATION(2-4)3.1ERROR IN INFIX NOTATION2.5%2ERROR IN INFIX NO

7、TATION2%2.5ERROR IN INFIX NOTATION2+3)(-5ERROR IN INFIX NOTATION(2)-3)ERROR IN INFIX NOTATION(2)-3)ERROR IN INFIX NOTATION3.5/(1-1)ERROR IN INFIX NOTATION(5.6-2)%3ERROR IN INFIX NOTATION5%(3.2-2.1)ERROR IN INFIX NOTATION3.0.2+1ERROR IN INFIX NOTATION1+1ERROR IN INFIX NOTATION1#1ERROR IN INFIX NOTATI

8、ON2 2ERROR IN INFIX NOTATION+-+ERROR IN INFIX NOTATION四、分析與探討算術(shù)表達(dá)式有中綴表示法和后綴表示法，本程序輸入的表達(dá)式采用中綴表示法。在這種表達(dá)式中，二元運算符位于兩個操作數(shù)之間。因為計算機只能一個字符一個字符的掃描，要想知道那個運算符優(yōu)先，就必須對整個中綴表達(dá)式掃描一遍。而后綴表達(dá)式則很容易通過應(yīng)用棧實現(xiàn)表達(dá)式計算，這為實現(xiàn)表達(dá)式求值程序提供了一種直接的計算機制。后綴表達(dá)式很容易應(yīng)用棧進(jìn)行計算，但要處理的是中綴表達(dá)式。同樣，也可以應(yīng)用棧將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。此時，棧里要保存的是運算符，而在后綴表達(dá)式中，棧里保存的是操作數(shù)。應(yīng)用

9、棧將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式處理過程的關(guān)鍵是不同運算符優(yōu)先級的設(shè)置。在程序?qū)崿F(xiàn)中，可以用一個數(shù)來代表運算符的優(yōu)先級，優(yōu)先級數(shù)值較大，它的優(yōu)先級越高，這樣優(yōu)先級的比較就轉(zhuǎn)換成兩個數(shù)大小的比較。本程序的棧采用帶頭結(jié)點的鏈?zhǔn)酱鎯Y(jié)構(gòu)，涉及兩種類型：用于存儲運算符號的char類型的鏈棧以及用于存儲操作數(shù)的float類型的鏈棧。棧的操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)： LinkStack *CreatStack() /初始化棧，并將棧置空LinkStack *S;S=(LinkStack*)malloc(sizeof(LinkStack);if(S=NULL)FatalError("Out of s

10、pace!");S->next=NULL;return S;int Pop(LinkStack *S) /刪除棧頂元素，并返回之LinkStack *FirsCell;if(S->next=NULL)Error("Empty stack!");elseint tempFirsCell=S->next;S->next=S->next->next;temp=FirstCell->data;free(firstCell)；return temp；void Push(int X,LinkStack *S) /元素X進(jìn)棧LinkSt

11、ack *TmpCell;TmpCell=(LinkStack *)malloc(sizeof(LinkStack);if(TmpCell=NULL)FatalError("Out of space!");elseTmpCell->data=X;TmpCell->next=S->next;S->next=TmpCell;五：總結(jié) 在設(shè)計過程中出現(xiàn)了一個cannot convert from “void *”to“struct Node *”Conversion from “void *”to pointer to non_void requires

12、an explicit cast的錯誤，我通過查閱資料知道了這是由于，所有分配地址要加強制類型轉(zhuǎn)換，因為分配內(nèi)存后缺省內(nèi)存是void *.這個錯誤改正后，程序可以正常運行。通過這次課程設(shè)計，我對棧的特性有了清楚的認(rèn)識，我也深深體會到數(shù)據(jù)結(jié)構(gòu)真的并不只是書本上的一些知識，上機實踐對于這門科目來說真的很重要。平常簡簡單單的一個運算，也許自己通過加加減減就能得出結(jié)果，可是這些算法到底是怎么實現(xiàn)的？平常不會想到，通過實踐才發(fā)現(xiàn)其中集合了很多我們平時忽略的知識，所以，通過這次實踐，我也把書中很多知識鞏固了下，加深印象！總之，通過這次課程設(shè)計，我確實收益頗多！附錄 源代碼：#include <std

13、io.h>#include <stdlib.h>#include <math.h>int PrintError = 0;typedef struct Node *PtrToNode;typedef PtrToNode Stack;int IsEmpty(Stack S);void MakeEmpty(Stack S);void Push(char X,Stack S);char Top(Stack S);void Pop(Stack S);typedef struct Nodechar Element;PtrToNode Next;typedef struct F

14、Node *Ptr_Fn;typedef Ptr_Fn FStack;int FisEmpty(FStack S);void FPush(float X,FStack S);float FTop(FStack S);void FPop(FStack S);typedef struct FNodefloat Element;Ptr_Fn Next;void ConvertToPost(FILE *In, Stack Whereat,FILE *Temp);void Reverse(Stack Rev);void Calculate(FILE *Change, Stack Whereat,FILE

15、 *Temp);int main()FILE *InputFile, *OutputFile,*Temp;/*初始化變量*/Stack Whereat;char sample;InputFile = fopen("Input.txt","r");/*打開文件*/OutputFile = fopen("Output.txt","w");Whereat = malloc(sizeof(struct Node);Whereat->Next = NULL;if (!InputFile | !OutputFile) p

16、rintf("intput or output file(s) do not exist.n");return(1);sample = getc(InputFile); while ( sample != EOF)Temp = fopen("Temp.txt","w+"); /*生成Temp文件*/ungetc(sample,InputFile); ConvertToPost(InputFile,Whereat,Temp); /*中綴變后綴*/if (PrintError) /*錯誤處理*/fprintf(OutputFile,&qu

17、ot;Error in infix notation."); fscanf(InputFile,"n",&sample);PrintError = 0;else if (IsEmpty(Whereat) = 1) else if (IsEmpty(Whereat) != 1)Reverse(Whereat);if (Top(Whereat) = 'B') /*錯誤處理，*/ PrintError = 1; fclose(Temp);Temp = fopen("Temp.txt","r+");Calcu

18、late(OutputFile, Whereat,Temp);/*計算結(jié)果*/fclose(Temp);MakeEmpty(Whereat);putc('n',OutputFile);/* 在輸出文件中換行*/sample = getc(InputFile); /* While循環(huán)結(jié)束*/free(Whereat); fclose(InputFile);fclose(OutputFile);remove("Temp.txt"); /* 刪除Temp.txt*/return 1;int IsEmpty(Stack S)return(S->Next=NUL

19、L);int FIsEmpty(FStack S)return(S->Next=NULL);void Pop(Stack S)PtrToNode FirstCell;if (IsEmpty(S)perror("Empty Stack");elseFirstCell = S->Next;S->Next = S->Next->Next;free(FirstCell);void FPop(FStack S)Ptr_Fn FirstCell;if (FIsEmpty(S)perror("Empty Stack");elseFirst

20、Cell = S->Next;S->Next = S->Next->Next;free(FirstCell);void MakeEmpty(Stack S)if (S = NULL)perror("Must use Createstack first");elsewhile (!IsEmpty(S)Pop(S);void FMakeEmpty(FStack S)if (S = NULL)perror("Must use Createstack first");elsewhile (!IsEmpty(S)Pop(S);void Pu

21、sh(char X, Stack S)PtrToNode TmpCell;TmpCell = (PtrToNode)malloc(sizeof(struct Node);if (TmpCell = NULL)perror("Out of Space!");elseTmpCell->Element = X;TmpCell->Next = S->Next;S->Next = TmpCell;void FPush(float X, FStack S)Ptr_Fn TmpCell;TmpCell = (Ptr_Fn)malloc(sizeof(struct

22、FNode);if (TmpCell = NULL)perror("Out of Space!");elseTmpCell->Element = X;TmpCell->Next = S->Next;S->Next = TmpCell;char Top(Stack S)if (!IsEmpty(S)return S->Next->Element;perror("Empty Stack");exit(1);return 0;float FTop(FStack S)if (!FIsEmpty(S)return S->N

23、ext->Element;perror("Empty Stack");exit(1);return 0;void Reverse(Stack Rev)Stack Tempstack;Tempstack = malloc(sizeof(struct Node);Tempstack->Next = NULL;while (!IsEmpty(Rev)Push(Top(Rev),Tempstack); /*將元素壓棧到一個臨時堆棧*/Pop(Rev);Rev->Next = Tempstack->Next; /*指向新的堆棧*/void ConvertToP

24、ost(FILE *In, Stack Whereat, FILE *Temp)Stack OpHolder;char holder;char lastseen;int digitcounter = 0; /*操作數(shù)的計數(shù)器*/OpHolder = malloc(sizeof(struct Node); /*初始化*/OpHolder->Next = NULL;holder=getc(In);lastseen = '' /*用來防止輸入格式錯誤putc(' ',Temp); while (holder !='n') && (

25、holder != EOF)if (holder = ' ')digitcounter = 0;else if ( IsOperator(holder) = -1) PrintError = 1;else if (IsOperator(holder)=0)if (lastseen = holder) && (lastseen = '.') /*錯誤處理*/PrintError = 1;elselastseen = holder;if (digitcounter = 0)Push('A',Whereat); /*進(jìn)棧*/digitc

26、ounter+;/*計數(shù)器加一*/putc(' ',Temp);putc(holder,Temp);elsedigitcounter = 0;if (lastseen = holder) && (lastseen != '(') && (lastseen != ')') PrintError = 1;elselastseen = holder;if(IsEmpty(OpHolder)=1) /*當(dāng)OpHolder為空*/Push(holder,OpHolder);else if(OperatorValue(Top(

27、OpHolder) = 6) if(OperatorValue(holder)=5)Pop(OpHolder);elsePush(holder,OpHolder);else if(OperatorValue(holder) = 6) Push(holder,OpHolder);else if(OperatorValue(holder) = 5) while (IsEmpty(OpHolder) != 1) && (OperatorValue(Top(OpHolder) != 6) putc(' ',Temp);Push('B',Whereat);

28、putc(Top(OpHolder),Temp);Pop(OpHolder);if (IsEmpty(OpHolder) = 1) PrintError = 1;else Pop(OpHolder);else if(OperatorValue(holder) = OperatorValue(Top(OpHolder) && (OperatorValue(holder) = 3) /*冪運算情況*/Push(holder,OpHolder);else if(OperatorValue(holder) < OperatorValue(Top(OpHolder) &&a

29、mp; 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);Pu

30、sh(holder,OpHolder);else if(OperatorValue(Top(OpHolder) >= OperatorValue(holder)while(IsEmpty(OpHolder) != 1) && (OperatorValue(Top(OpHolder) >= OperatorValue(holder) && (OperatorValue(Top(OpHolder)!=6)putc(' ',Temp);putc(Top(OpHolder),Temp);Push('B',Whereat);Po

31、p(OpHolder);Push(holder,OpHolder);else if(OperatorValue(Top(OpHolder) < OperatorValue(holder) Push(holder,OpHolder);holder=getc(In); /* While循環(huán)結(jié)束*/while(IsEmpty(OpHolder)!=1) Push('B',Whereat);putc(' ',Temp);putc(Top(OpHolder),Temp);Pop(OpHolder);MakeEmpty(OpHolder); free(OpHolder

32、);int IsOperator(char ToCompare)if (ToCompare = '(' | ToCompare = ')'| ToCompare = '+' | ToCompare = '-' | ToCompare = '*'| ToCompare = '/' | ToCompare = ''| ToCompare = '%')return 1;else if (ToCompare = '1' | ToCompare = '2

33、'| ToCompare = '3' | ToCompare = '4' | ToCompare = '5'| ToCompare = '6' | ToCompare = '7'| ToCompare = '8' | ToCompare = '9'| ToCompare = '0'| ToCompare = '.') return 0; elsereturn -1;int OperatorValue(char ValueToGive)if (V

34、alueToGive = '(')return 6;if (ValueToGive = ')')return 5;if (ValueToGive = '')return 3; if (ValueToGive = '%')return 2;if (ValueToGive = '*') return 2;if (ValueToGive = '/')return 2;if (ValueToGive = '+')return 1;if (ValueToGive = '-')r

35、eturn 1;return 0;void Calculate(FILE *Change, Stack Whereat, FILE *Temp)FStack Operands;float looker;char Op;char spacefinder;float answer = 0;float NumA;float NumB;Operands = (Ptr_Fn)malloc(sizeof(struct FNode);Operands->Next= NULL;while (IsEmpty(Whereat) != 1) && PrintError != 1) if (To

36、p(Whereat) = 'A')fscanf(Temp," ",&spacefinder);fscanf(Temp,"%f",&looker); /*如果是A,則是操作數(shù)*/FPush(looker,Operands);Pop(Whereat);else if (Top(Whereat) = 'B')fscanf(Temp," ",&spacefinder); /*如果是B,則是運算符*/Op = getc(Temp);switch(Op) /* 判斷是什么運算符*/case(

37、''): /*冪運算*/NumB = FTop(Operands);FPop(Operands);if (FIsEmpty(Operands) /*錯誤處理*/PrintError = 1;elseNumA = FTop(Operands);FPop(Operands);if (NumA = 0 && NumB < 0)|(NumA<0) && (NumB - (int)NumB != 0)PrintError = 1;elseanswer = pow(NumA,NumB);FPush(answer,Operands);break;c

38、ase '%': /*取模運算*/NumB = FTop(Operands);FPop(Operands);if (FIsEmpty(Operands)/*錯誤處理*/PrintError = 1;elseNumA = FTop(Operands);FPop(Operands);if (NumA - (int)NumA != 0) | (NumB - (int)NumB != 0) | (NumB = 0)PrintError = 1;elseanswer = (int)NumA % (int)NumB; FPush(answer,Operands);break;case '*': NumB = FTop(Operands);FPop(Operands);if (FIsEmpty(Operands)PrintErro