帶括號算術(shù)表達式的計算實驗報告

1、四川大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法分析實驗報告實驗名稱 ：帶括號的算術(shù)表達式求值指導(dǎo)老師 ：_孫界平_學(xué) 院 ：_軟件學(xué)院_專 業(yè) ：_軟件工程_姓 名 ：_馬 健_學(xué) 號 ：_班 級 ：_5 班_日 期 ：_2014年10月24日_目錄一實驗題目3二實驗?zāi)康暮鸵?三實驗環(huán)境3四算法描述3五源程序清單附錄六運行結(jié)果6七實驗運行情況分析7一、實驗題目:l 帶括號的算術(shù)表達式求值二、實驗?zāi)康暮鸵?ü 采用算符優(yōu)先數(shù)算法,能正確求值表達式;ü 熟練掌握棧的應(yīng)用;ü 熟練掌握計算機系統(tǒng)的基本操作方法,了解如何編輯、編譯、鏈接和運行一個C程序;ü 上機調(diào)試程序,掌握查錯、

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

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

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

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

6、、源程序清單Ø 見附錄六、運行結(jié)果Ø 測試表l 本次測試采用用戶從鍵盤輸入算數(shù)表達式，共進行16組測試序號測試功能測試內(nèi)容輸入項預(yù)期輸出實際輸出結(jié)果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容錯能力除數(shù)為02+3/0=輸出除數(shù)為0輸出除數(shù)為0通過10容錯能力自動去空格1+ 2 * ( 3 + 4)=1515通過11容錯能力“=”輸為”#”2*(3+2)#1010通過12拓展功能多位正數(shù)計算10*(2+13)=150輸出錯誤信息未通過13拓展功能負(fù)數(shù)計算4+3*(-4)+5=-3輸出錯誤信息未通過15拓展功能小數(shù)計算1+10*0.1/2=6輸出錯誤信息未通過16全體測試最終測試2 *(4 (3+3) )+3 #-1-1通過Ø 部分運行截圖l 基本計算操作不能整除運算(3)多括號運算(2)l 式子正誤判斷l(xiāng) 容

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

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

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

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

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

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

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

15、39;='結(jié)尾)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 != ' ')/若出現(xiàn)空格,自動刪除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'/頭結(jié)點存儲表達式中字符個數(shù)if(head->next != NULL)p2->next = NULL;return head;/創(chuàng)建空棧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("增加?？臻g失敗!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;/計算算術(shù)表達式int Calculate(struct Expression *exp)exp = exp->next;/取表達式開始char OpSign =' '/存儲出棧操作符char NumSign1=' ',NumSign2= ' '/存儲出棧數(shù)字符char result;/存儲部分運算結(jié)果char temp = ' '/接受出棧操作數(shù)Stack s_operator, s_number; StackCreate(&a

21、mp;s_operator);/創(chuàng)建操作符棧StackCreate(&s_number);/創(chuàng)建數(shù)字棧PUSH(&s_operator,'#');/先在操作棧底壓入'#'printf("n計算過程如下:n");while(exp->sign != '#' | GetTop(&s_operator) != '#')/操作數(shù)存入操作數(shù)棧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)/比較棧頂元素和運算符的優(yōu)先級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);/獲取最終計算結(jié)果re

24、turn result - '0'/判斷兩個運算符的優(yōu)先級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'/取數(shù)字字符的值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'/判斷字符是運算符還是數(shù)字符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;/操作數(shù)break;default:ret

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

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