1、四川大學數據結構與算法分析實驗報告實驗名稱 ：帶括號的算術表達式求值指導老師 ：_孫界平_學 院 ：_軟件學院_專 業 ：_軟件工程_姓 名 ：_馬 健_學 號 ：_班 級 ：_5 班_日 期 ：_2014年10月24日_目錄一實驗題目3二實驗目的和要求3三實驗環境3四算法描述3五源程序清單附錄六運行結果6七實驗運行情況分析7一、實驗題目:l 帶括號的算術表達式求值二、實驗目的和要求:ü 采用算符優先數算法,能正確求值表達式;ü 熟練掌握棧的應用;ü 熟練掌握計算機系統的基本操作方法,了解如何編輯、編譯、鏈接和運行一個C程序;ü 上機調試程序,掌握查錯、

2、排錯使程序能正確運行。三、實驗的環境:² 硬件環境:聯想 筆記本電腦² 軟件環境:操作系統:windows 7 旗艦版編譯軟件:Visual C+ 6.0四、算法描述:否開始判斷表達式是否正確從鍵盤讀入算術表達式存入單鏈表中是用棧計算顯示算數表達式退出程序是是否繼續計算？顯示錯誤信息否Ø 程序框圖判斷表達式是否正確Ø 文字解釋:1. 用戶從鍵盤讀入算術中綴表達式，以”=”結尾;2. 程序判斷用戶輸入表達式是否正確;3. 若表達式正確，則用棧計算算術表達式;4. 打印輸出計算過程和最終結果;5. 程序詢問用戶是否繼續計算;6. 若繼續，則執行第1步;若否定

3、，則退出程序7. 若表達式錯誤，則打印錯誤信息，提示用戶重新輸入8. 返回第1步;Ø 函數及結構說明:l 結構體:1) 存儲算數表達式的單鏈表:struct Expressionchar sign;struct Expression *next;2) 操作符和操作數棧:typedef structchar *top;char *bottom;int stack_size;Stack;l 構造函數:1) 棧相關操作函數: 初始化空棧 int StackCreate(Stack *s); 入棧操作int PUSH(Stack *s, char c); 出棧操作int POP(Stack

4、*s, char c); 獲取棧頂元素char GetTop(Stack *s);2) 計算相關操作函數:利用棧計算算術表達式int Calculate(struct Expression *exp);子式的值的計算int Count(char num1, char sign, char num2);判斷字符是否為運算符int IsOpOrNum(char c);判斷運算符優先級char JudgeLevel(char c1, char c2);判斷表達式正確性int IsExpresiion(struct Expression *exp);輸出計算結果void PrintResult(str

5、uct Expression *exp,int result);3) 算術表達式輸入函數:鍵盤讀入存于單鏈表struct Expression *GetExp();符號2l 構造操作符優先級表符號1比較+-*/()=(#)+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>=(#)<<<<<=五

6、、源程序清單Ø 見附錄六、運行結果Ø 測試表l 本次測試采用用戶從鍵盤輸入算數表達式，共進行16組測試序號測試功能測試內容輸入項預期輸出實際輸出結果1基本計算操作單括號運算2*(3+4)+5*3=2929通過2基本計算操作多括號運算3+(4+3)*6)/3=1717通過3基本計算操作不能除整運算6*(2+(3/2)=2118有誤差4基本計算操作不能除整運算(1+2+3)/4=1.51有誤差5式子正誤判斷括號不匹配1+(1+3*2=輸出錯誤信息輸出錯誤信息通過6式子正誤判斷計算符多余1+2*3+6=輸出錯誤信息輸出錯誤信息通過7式子正誤判斷含非計算符x+y*z+w=輸出錯誤信

7、息輸出錯誤信息通過8式子正誤判斷未輸入”=”1+2*377通過9容錯能力除數為02+3/0=輸出除數為0輸出除數為0通過10容錯能力自動去空格1+ 2 * ( 3 + 4)=1515通過11容錯能力“=”輸為”#”2*(3+2)#1010通過12拓展功能多位正數計算10*(2+13)=150輸出錯誤信息未通過13拓展功能負數計算4+3*(-4)+5=-3輸出錯誤信息未通過15拓展功能小數計算1+10*0.1/2=6輸出錯誤信息未通過16全體測試最終測試2 *(4 (3+3) )+3 #-1-1通過Ø 部分運行截圖l 基本計算操作不能整除運算(3)多括號運算(2)l 式子正誤判斷l 容

8、錯能力l 全體測試七、實驗運行情況分析Ø 優點:l 用戶輸入格式較為自由。增添了一些能想到的容錯系統，如用戶未輸入”=”，或是用戶將”=”錯輸成”#”，或是用戶在字符間輸入空格，程序都會智能識別出正確的算數表達式，計算正確答案。l 防錯報錯系統較為完善。多方面考慮輸入方面的錯誤，如括號不匹配、計算符少輸多輸、輸入非計算符等方面均考慮，并提示用戶錯誤信息，便于用戶檢查輸入狀況。l 存儲方式較為規范。采用單鏈表存儲用戶輸入的算術表達式，更加清晰簡單,頭結點存儲表達式中符號的個數，方便在必要的時候統計對照最終結果的正確性。Ø 缺點:l 只能實現數字之間的四則運算，不能實現其他算數

9、功能如平方，開方等。l 僅僅局限于個位數之間的運算，無法運算兩位數或兩位以上數字的運算。l 計算數字只能為0-9的整數，無法對負數或者小數進行計算。l 在除法中若遇到無法除盡的結果，只能保留其整數部分，造成最終結果跟預期結果存在誤差l 由于控制臺系統的限制，與用戶交互性較差，界面太過簡單單調。Ø 感受:通過本次“帶括號算數表達式的計算”實驗，我不光復習了之前學習的單鏈表的相關知識并加以采用，而且還鞏固了有關于棧的相關操作；在實現題目要求基本功能的基礎上，還增加拓展了一些內容。在為期兩周的實驗中，從剛開始的整理思路，到接下里的編寫代碼，到最后的填寫實驗報告，都是我自己一步步完成。唯獨可

10、惜的是，由于知識掌握不夠全面，導致只能實現最基本的功能，無法進行進一步的擴展和完善，致使用戶輸入一些運算式未得到預期的結構，這是比較遺憾的方面。附錄(源程序代碼)/*實驗一：帶括號的算數表達式求值*實現：棧*語言：C*作者：馬健*/#include <stdio.h>#include <stdlib.h>#include <conio.h>#define STACK_SIZE_FIRST 100 /棧的初始空間大小#define STACK_SIZE_INCREASE 20 /棧的增加空間大小/*-算術表達式單鏈表-*/struct Expression c

11、har sign;struct Expression *next;/*-操作符和操作數棧-*/typedef structchar *top;char *bottom;int stack_size; /棧的空間大小Stack;struct Expression *GetExp(); /鍵盤讀入表達式存入單鏈表/*-棧相關的操作函數-*/int StackCreate(Stack *s); /初始化一個空棧函數int PUSH(Stack *s, char c); /入棧函數int POP(Stack *s, char c); /出棧函數char GetTop(Stack *s); /取出棧頂元

12、素/*-計算相關操作函數-*/int Calculate(struct Expression *exp); /帶括號的算數表達式計算函數int Count(char num1, char sign, char num2); /兩個數的計算int IsOpOrNum(char c); /判斷一個字符是不是運算符char JudgeLevel(char c1, char c2); /判斷兩運算符優先級void PrintResult(struct Expression *exp,int result); /打印最終結果int IsExpresiion(struct Expression *exp)

13、; /判斷是否為正確的算術表達式void main()struct Expression *head;int Result = 0; /定義最終計算結果int temp = 0; /定義循環參數char select;while(temp = 0)head = GetExp(); /創建算術表達式單鏈表if(IsExpresiion(head) = 0 | head = NULL) /算術表達式錯誤，重新輸入printf("算術表達式錯誤，請認真檢查并重新輸入");getch();system("cls");elseResult = Calculate(

14、head);/計算算術表達式PrintResult(head,Result);/輸出最終計算結果printf("是否繼續計算? 是(y) 否(n)n");/是否繼續select = getch();if(select = 'n' | select = 'N')temp = 1;elsesystem("cls");/讀入算術表達式并存儲于鏈表struct Expression *GetExp() printf("t帶括號的算術表達式求值n");printf("請輸入需要計算的算數表達式:(以&#

15、39;='結尾)n");char c;int number = 0;struct Expression *head = NULL,*p1,*p2,*first = NULL;/定義指針變量head = (struct Expression *)malloc(sizeof(struct Expression);while(c = getchar() != 'n')if(c != ' ')/若出現空格,自動刪除p1 = (struct Expression *)malloc(sizeof(struct Expression);if(c = '

16、;=')c = '#'p1->sign = c;if(first = NULL)first = p1;elsep2->next = p1;p2 = p1;number+;if(p2->sign != '#')/若未輸入'=',則自動補齊p1 = (struct Expression *)malloc(sizeof(struct Expression);p1->sign = '#'p2->next = p1;p2 = p1;number+;head->next = first;head-&

17、gt;sign = number + '0'/頭結點存儲表達式中字符個數if(head->next != NULL)p2->next = NULL;return head;/創建空棧int StackCreate(Stack *s)s->bottom = (char *)malloc(STACK_SIZE_FIRST * sizeof(char);if (s->bottom = NULL)printf("棧初始化失敗!n");exit(0);elses->top = s->bottom;s->stack_size =

18、 STACK_SIZE_FIRST;return 1;/入棧int PUSH(Stack *s, char c)if(s->top - s->bottom >= STACK_SIZE_FIRST)s->bottom = (char *)realloc(s->bottom,(STACK_SIZE_FIRST+STACK_SIZE_INCREASE) * sizeof(char);if(s->bottom = NULL)printf("增加棧空間失敗!n");exit(0);s->stack_size = s->stack_siz

19、e + STACK_SIZE_INCREASE;*(s->top) = c;/賦值需要入棧的元素s->top +;/棧頂指針上移return 1;/出棧int POP(Stack *s, char c)if(s->top = s->bottom)printf("棧為空!出棧失敗!n");exit(0);elsec = *(s->top);s->top -;return 1;/獲取棧頂元素char GetTop(Stack *s)char c;if(s->top = s->bottom)printf("棧空，無法獲取棧

20、頂元素!n");elsec = * (s->top - 1);return c;/計算算術表達式int Calculate(struct Expression *exp)exp = exp->next;/取表達式開始char OpSign =' '/存儲出棧操作符char NumSign1=' ',NumSign2= ' '/存儲出棧數字符char result;/存儲部分運算結果char temp = ' '/接受出棧操作數Stack s_operator, s_number; StackCreate(&a

21、mp;s_operator);/創建操作符棧StackCreate(&s_number);/創建數字棧PUSH(&s_operator,'#');/先在操作棧底壓入'#'printf("n計算過程如下:n");while(exp->sign != '#' | GetTop(&s_operator) != '#')/操作數存入操作數棧if(IsOpOrNum(exp->sign) = 0)PUSH(&s_number,exp->sign);exp = exp-&g

22、t;next;/操作符存入操作符棧else if(IsOpOrNum(exp->sign) = 1)OpSign = GetTop(&s_operator);/獲取棧頂元素switch(JudgeLevel(OpSign,exp->sign)/比較棧頂元素和運算符的優先級case '<':PUSH(&s_operator,exp->sign); exp = exp->next;break;case '=':POP(&s_operator,OpSign); exp = exp->next; break;c

23、ase '>': POP(&s_operator,OpSign); NumSign1 = GetTop(&s_number); POP(&s_number,temp); NumSign2 = GetTop(&s_number); POP(&s_number,temp); result = Count(NumSign2,OpSign,NumSign1); PUSH(&s_number,result); break;default: break;result = GetTop(&s_number);/獲取最終計算結果re

24、turn result - '0'/判斷兩個運算符的優先級char JudgeLevel(char c1, char c2)switch(c1) case '+': switch(c2) case '*': case '/': case '(': return '<' break; default: return '>' break; break; case '-': switch(c2) case '*': case '/'

25、;: case '(': return '<' break; default: return '>' break; break; case '*': switch(c2) case '(': return '<' break; default: return '>' break; break; case '/': switch(c2) case '(': return '<' break; default:

26、 return '>' break; break; case '(': switch(c2) case ')': return '=' break; default: return '<' break; break; case ')': switch(c2) case '+': return '>'break; default: return '>' break; break; case '#': switch(

27、c2) case '#': return '=' break; default: return '<' break; break; default: return '<' break; /計算一個符號的運算int Count(char num1, char sign, char num2)int a=0,b=0;a = num1 - '0'/取數字字符的值b = num2 - '0'int result = 0;switch(sign)case '+':result =

28、a+b;break;case '-':result = a-b;break;case '*':result = a*b;break;case '/':result = a/b;break;default:break;printf("%d %c %d = %dn",a,sign,b,result); /輸出計算過程return result + '0'/判斷字符是運算符還是數字符int IsOpOrNum(char c)switch(c)case '+':case '-':case

29、 '*':case '/':case '(':case ')':case '#':return 1;/操作符break;case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':return 0;/操作數break;default:ret

30、urn -1;/其他break;/輸出最終結果void PrintResult(struct Expression *exp,int result)printf("n最終計算結果為:n");exp = exp->next;while(exp != NULL)if( exp->sign = '#')exp->sign = '='printf(" %c",exp->sign);exp = exp->next;printf(" %dn",result);/判斷用戶輸入的算術表達式

31、是否正確int IsExpresiion(struct Expression *exp)int parameter = 1; /定義判斷表達式正確與否參數int i=0,j=0; /左右括號數量if(exp->sign - '0' < 4) /判斷表達式字符個數是否正確parameter = 0;exp = exp->next;while(parameter = 1) && (exp != NULL)switch(IsOpOrNum(exp->sign)case 0: /如果是數字,后必須跟操作符,且不能為左括號exp = exp->next;if(IsOpOrNum(exp->sign) != 1 |