北理工數(shù)據(jù)結(jié)構(gòu)試驗二

1、北理工數(shù)據(jù)結(jié)構(gòu)實驗二數(shù)據(jù)結(jié)構(gòu)與算法設計實驗報告實驗二學院:班級:學號:姓名:一、實驗目的1 .通過實驗實踐、鞏固棧的相關(guān)操作；2 .熟悉VC環(huán)境，加強編程、調(diào)試的練習；3 .用C語言實現(xiàn)棧的抽象數(shù)據(jù)類型，實現(xiàn)棧的 建立、進棧、出棧、取數(shù)據(jù)等基本操作；4 .用C語言實現(xiàn)判斷運算符優(yōu)先級、表達式求 值等基本操作；5 .理論知識與實際問題相結(jié)合，利用上述基本 操作實現(xiàn)簡單計算器。二、實驗內(nèi)容1、簡單計算器。請按照四則運算加、減、乘、除、哥（人）和括 號的優(yōu)先關(guān)系和慣例，編寫計算器程序。要求：從鍵盤輸入一個完整的表達式，以回車作為 表達式輸入結(jié)束的標志。輸入表達式中的數(shù)值均為大于等于零的整 數(shù)。中間的

2、計算過程如果出現(xiàn)小數(shù)也只取 整。例如，輸入：4+2*5= 輸出：14輸入：（4+2）*（2-10）= 輸出：-48三、程序設計1、概要設計 為實現(xiàn)上述程序功能，應用棧存儲運算符和操作 數(shù)，為此需要建立一個抽象數(shù)據(jù)類型：棧。(1)、棧的抽象數(shù)據(jù)類型定義為：ADT Stack數(shù)據(jù)對象： D=ai|aiElemSet,i=1,2,3 ,n,n >0數(shù)據(jù)關(guān)系：R1= <ai-1,ai>|aiGD,i=1,2,n基本操作：InitStack(&S)操作結(jié)果：創(chuàng)建一個空棧SoPush(&S, e)初始條件：棧S已存在操作結(jié)果：插入運算符e作為新的棧頂元素GetTop(&a

3、mp;S)初始條件：棧S已存在且非空操作結(jié)果：用e返回寄存運算符棧S的棧頂元素Pop(&S,&e)初始條件：棧S已存在且非空操作結(jié)果：刪除寄存運算符棧S的棧頂元Operate(a,theta,b)初始條件：a, b為整數(shù)，theta為運算符 操作結(jié)果：返回a與b運算的結(jié)果Precede(d,c)初始條件：d, c為運算符操作結(jié)果：若d優(yōu)先級大于c,返回'>' 若d優(yōu)先級小于c,返回 <'若d優(yōu)先級等于 c,返回='EvaluateExpression()初始條件：輸入合法的表達式操作結(jié)果：返回表達式的值A(chǔ)DT Stack主程序流程調(diào)用

4、EvaluateExpression() 函數(shù)計算表達 式的值，并將結(jié)果輸出在屏幕上。各函數(shù)模塊的調(diào)用關(guān)系先由主函數(shù)調(diào)用計算求值函數(shù)；再由求值模塊調(diào)用棧構(gòu)造函數(shù)，構(gòu)造兩個棧 分別用來保存操作數(shù)和運算符，然后根據(jù)情況多 次調(diào)用進棧、出棧、取棧頂元素、判斷運算符優(yōu) 先級、計算表達式的值等多個函數(shù)，計算并返回表達式的值；最后由主函數(shù)在屏幕上輸出表達式的結(jié)果 流程圖作I為運算輸出運結(jié)2、詳細設計<:操作符入(1)、宏定義# define STACK_INIT_SIZE 10 / 棧 存儲空間的初始分配量# define STACKINCREMENT 10 / 空 間的分配增量# define O

5、K1 /正確時返回值為真#define ERROR 0 /出錯時返回值為假(2)、抽象數(shù)據(jù)類型定義typedef char ElemType1;定義元素類型1為chartypedef int ElemType2;/ 定義元素類型2為inttypedef struct棧SqStack1存儲元素為charElemType1 *base; /?？臻g基址ElemType1 *top; /棧頂指針int stacksize; /當前分配的棧空間大小SqStack1;typedef struct/棧SqStack2存儲元素為intElemType2 *base; /?？臻g基址ElemType2 *top;

6、 /棧頂指針 int stacksize; /當前分配的棧空間大小SqStack2;(3)、操作算法程序?qū)崿F(xiàn)： int InitStack1( SqStack1 &S ) /構(gòu)造一個空棧SS.base =( ElemType1*)malloc(STACK_INIT_SIZE *sizeof(ElemType1); /為順序棧動態(tài)分配存儲空間if(! S. base)exit(OVERFLOW); / 分配失敗S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK; InitStackl int Push1( SqStackl &am

7、p;S, ElemTypel e ) / 將元素e插入棧中，使其成為新的 棧頂元素if ( S.top-S.base>=S.stacksize )/若棧滿則追加存儲空間 S.base = (ElemTypel * ) realloc( S.base,(S.stacksize+STACKINCREMENT) * sizeof(ElemTypel);if(! S. base )exit(OVERFLOW); / 存儲分配失敗S.top = S.base + S.stacksize;S.stacksize+=STACKINCREMENT; * S.top + = e; / 元素 e 插入 棧頂

8、，后修改棧頂指針return OK; / *S.top=e;S.top +; /Pushlchar GetTop1( SqStackl S) /取棧頂元素并返回其值ElemTypel e;if (S.top=S.base)return ERROR; /e = *(S.top-1);return e; /GetTopIint Pop1 ( SqStackl &S, ElemTypel&e ) 刪除棧頂元素，并用e返回其值if ( S.top=S.base)return ERROR; /?？誩 = * - S.top; /-S.top;e=*S.top;return OK; Pop

9、1int InitStack2( SqStack2 &S )S.base /構(gòu)造一個空棧SElemType2*)malloc(sizeof(ElemType2);STACKINITSIZE/為順序棧動態(tài)分配存儲空間ifS.base)exit(OVERFLOW); / 分配失敗 S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK; InitStack2int Push2( SqStack2 &S, ElemType2 e ) / 將元素e插入棧中，使其成為新的 棧頂元素if ( S.top-S.base>=S.sta

10、cksize )/若棧滿則追加存儲空間 S.base = (ElemType2 * ) realloc( S.base,(S.stacksize+STACKINCREMENT) * sizeof(ElemType2);if(! S. base )exit(OVERFLOW); / 存儲分配失敗S.top = S.base + S.stacksize;S.stacksize+=STACKINCREMENT; * S.top + = e; / 元素 e 插入 棧頂，后修改棧頂指針return OK; / *S.top=e;S.top +; /Push2int GetTop2( SqStack2 S

11、) /取棧頂元素并返回其值ElemType2 e;if ( S.top=S.base)return ERROR; /?？誩 = *(S.top-1);return e; /GetTop2int Pop2 ( SqStack2 &S, ElemType2 &e ) 刪除棧頂元素，并用e返回其值if ( S.top=S.base) return ERROR; /?？誩 = * - S.top; /-S.top;e=*S.top;return OK; /Pop2 int In (char c) /判斷c是否為運算符，是則返回1否則返回0if(c='+'|c='

12、-'|c='*'11c='/'|c='A'|c='('|c=')'11c='=')return 1;elsereturn 0; /Inchar Precede(char d,char c) /判斷運算符d與運算符c的優(yōu)先級 switch(c) case'+':switch(d)case'+':return '>'break; case'-':return '>'break; case'*

13、9;:return '>'break; case'/':return '>'break; case'"return '>'break; case'(':return '<'break; case')':return '>'break; case'=':return '<'break;case'-':switch(d) case'+':return &#

14、39;>'break; case'-':return '>'break; case'*':return '>'break; case'/':return '>'break; case'"return '>'break; case'(':return '<'break; case')':return '>'break; case'=':re

15、turn '<'break;case'*':switch(d) case'+':return '<'break; case'-':return '<'break; case'*':return '>'break; case'/':return '>'break; case'"return '>'break; case'(':return '&l

16、t;'break; case')':return '>'break; case'=':return '<'break;case'/':switch(d) case'+':return '<'break;case'-':return '<'break; case'*':return '>'break; case'/':return '>'break

17、;case'"return '>'break; case'(':return '<'break; case')':return '>'break; case'=':return '<'break;case'A':switch(d)case'+':return '<'break; case'-':return '<'break; case'*&#

18、39;:return '<'break; case'/':return '<'break;case'"return '>'break; case'(':return '<'break; case')':return '>'break; case'=':return '<'break;case'(':switch(d)case'+':return 

19、9;<'break; case'-':return '<'break; case'*':return '<'break; case'/':return '<'break; case'"return '<'break; case'(':return '<'break; case'=':return '<'break;case')':swit

20、ch(d)case'+':return '>'break; case'-':return '>'break; case'*':return '>'break; case'/':return '>'break;case'"return '>'break; case'(':return '='break; case')':return '>'

21、;break;case'=':switch(d)case'+':return '>'break;case'-':return '>'break;case'*':return '>'break;case'/':return '>'break;case'"return '>'break;case')':return '>'break;case'=&

22、#39;:return '='break; /Precedeint Operate(int a,char theta,int b) /運算函數(shù)switch(theta)case'+':return (a+b);case'-':return (a-b);case'*':return (a*b);case'/':return (a/b);case'"return (pow(a,b);/Operateint EvaluateExpression() /算術(shù)表達式求值的算符優(yōu)先算 法。設OPT序口 OPN

23、盼別為運算符棧和操作數(shù)棧， OP為運算符、界限符集合。char c,theta;int num,a,b;SqStackl OPTR;SqStack2 OPND;InitStackl(OPTR);InitStack2(OPND);Push1(OPTR,'=');c=getchar();while (c!='='|GetTop1(OPTR)!='=')num = 0;if (! In(c) In(c)判斷c是否為運算符while(!In(c)num*=10;num+=(c-48);c=getchar();Push2(OPND, num); / 不是運

24、算符則進棧 else switch (Precede(GetTop1(OPTR),c) /判定OPTR勺棧頂運算符1 入的運算符2間的優(yōu)先關(guān)系case/新輸入的算符c優(yōu)先級高，c進棧Push1(OPTR, c=getchar( ); break; case /脫括號并接收下一字符Pop1(OPTR, c=getchar( ); break;case '>': / 新輸入的算符c 級低，即棧頂算符優(yōu)先權(quán)高/出棧并將運算結(jié)果入棧Pop1( OPTR, theta);Pop2( OPND, b);與讀'<': c);'=' c);優(yōu)先OPN

25、DPop2( OPND, a);Push2( OPND, Operate(a, theta, b)； 進行二元運算a theta bbreak; /switch /while return GetTop2(OPND); EvaluateExpression (4)、主程序的代碼實現(xiàn)： int main()int x; /定義整形變量x用以接受表達式的值x=EvaluateExpression(); / 返回表達 式的值printf("%dn",x);/ 輸出表達式的值return 0;四、程序調(diào)試分析1 .引用標識符壞符合C語言語法，應使用C+;2 .存操作數(shù)和運算符的棧元

26、素類型不一樣，所以要定義兩種元素類型、兩種棧以及分別對應的 基本操作；3 .操作數(shù)進棧時要注意連續(xù)讀完所有非運算符 的字符并且把字符型轉(zhuǎn)換為整型；4 . pow()函數(shù)返回值為double ,直接取整會丟失 數(shù)據(jù)，組建時會有警告提示。五、用戶使用說明1 .本程序的運行環(huán)境為DOSI作系統(tǒng)，執(zhí)行文件 為：實驗二.exe ,雙擊打開文件。2 .進入程序后，輸入要計算的表達式，按 Enter 鍵結(jié)束。3 .屏幕輸出上述表達式的結(jié)果，按任意鍵退出程 序。六、程序運行結(jié)果測試一：I F4+2»5=二14PresE 遢ny key to cont inueH測試二： 工:濟科巨算溫球Debuq二

27、Qc'. | 目-48p青癖琮匿 any Ley 七口 cvntriinmaL“測試三：I E百田科司強揖王噲朗超程序D史bug'室裝二r _、L 5-15/2 +4tE*ireS3 any kcy to continue：七、程序清單#include <stdio.h>#include <stdlib.h>#include <math.h>typedef char ElemTypel;定義元素類型1為 chartypedef int ElemType2;定義元素類型2為int# define STACK_INIT_SIZE 10 / 棧存儲

28、 空間的初始分配量# define STACKINCREMENT 10 / 空間 的分配增量# define OK1/正確時返回值為真# define ERROR0/ 出錯時返回值為假typedef struct 棧SqStack1存儲元素為charElemType1ElemType1 int stacksize;小base; top;?？臻g基址棧頂指針當前分配的?？臻g大typedef struct 棧SqStack2存儲元素為ElemType2 *base;ElemType2 *top; int stacksize;小int?？臻g基址棧頂指針當前分配的?？臻g大SqStack1;SqStack

29、2;int InitStack1( SqStack1構(gòu)造一個空棧SS.base =&S )*)malloc(STACK(INITSIZEElemType1*sizeof(ElemType1);為順序棧動態(tài)分配存儲空間/if ( ! S. base) exit(OVERFLOW);分配失敗S.top = S.base;S.stacksize = STACK_INIT_SIZE; return OK; InitStacklint Push1( SqStackl &S, ElemTypel e )將元素e插入棧中，使其成為新的棧頂元素if ( S.top-S.base>=S.s

30、tacksize ) / 若棧滿則 追加存儲空間 S.base = (ElemType1 * ) realloc (S.base,(S.stacksize +STACKINCREMENT) * sizeof(ElemType1);if ( ! S. base ) exit(OVERFLOW);存儲分配失敗S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;* S.top + = e; /元素e插入棧頂，后修 改棧頂指針return OK;/ *S.top=e; S.top +; /Push1char GetTop1( SqSta

31、ckl S) 取棧頂元素并返回其值ElemTypel e;if ( S.top=S.base)return ERROR;/?？誩 = *(S.top-1);return e; /GetTop1int Pop1 ( SqStack1 &S, ElemType1 &e ) 刪除棧頂元素，并用e返回其值if ( S.top=S.base)return ERROR; / 棧空e = * - S.top;-S.top; e=*S.top;return OK; /Pop1int InitStack2( SqStack2 &S )構(gòu)造一個空棧SS.base =( ElemType2

32、sizeof(ElemType2);*)malloc(STACKINITSIZE為順序棧動態(tài)分配存儲空間if ( ! S. base) exit(OVERFLOW); /分配失敗S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK; / InitStack2 int Push2( SqStack2 &S, ElemType2 e ) 將元素e插入棧中，使其成為新的棧頂元 素if ( S.top-S.base>=S.stacksize ) / 若棧滿則 追加存儲空間 S.base = (ElemType2 * ) reallo

33、c (S.base,(S.stacksize +STACKINCREMENT) * sizeof(ElemType2);if ( ! S. base ) exit(OVERFLOW);存儲分配失敗S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;* S.top + = e; 元素e插入棧頂)后修 改棧頂指針return OK;/ *S.top=e; S.top +; /Push2int GetTop2( SqStack2 S) 取棧頂元素并返回其值ElemType2 e;if ( S.top=S.base)return ERR

34、OR;?？誩 = *(S.top-1);return e; /GetTop2int Pop2 ( SqStack2 &S, ElemType2 &e ) 刪除棧頂元素，并用e返回其值if ( S.top=S.base)return ERROR; / ?？誩 = * - S.top;-S.top; e=*S.top;return OK; Pop2int In (char c) /判斷c是否為運算符，是則返回1,否則返 回0。if(c='+'|c='-'|c='*'|c='/'|c='A'|c='

35、;('|c=')'|c='=')return 1;elsereturn 0;/Inchar Precede(char d,char c) 判斷運算符d與運算符c的優(yōu)先級switch(c)case'+':switch(d)case'+':return '>'break;case'-':return '>'break;case'*':return '>'break;case'/':return '>&

36、#39;break;case'A'：return '>'break;case'(':return '<'break;case')':return '>'break;case'=':return '<'break;case'-':switch(d)case'+':return '>'break;case'-':return '>'break;case

37、9;*':return '>'break; case'/':return '>'break;case'"return '>'break; case'(':return '<'break; case')':return '>'break; case'=':return '<'break;case'*':switch(d)case'+':retur

38、n '<'break; case'-':return '<'break; case'*':return '>'break; case'/':return '>'break;case'"return '>'break; case'(':return '<'break;case')':return '>'break;case'=':r

39、eturn '<'break;case'/':switch(d)case'+':return '<'break;case'-':return '<'break;case'*':return '>'break; case'/':return '>'break;case'"return '>'break; case'(':return '<&

40、#39;break; case')':return '>'break; case'=':return '<'break;case'A':switch(d)case'+':return '<'break; case'-':return '<'break; case'*':return '<'break; case'/':return '<'break;ca

41、se'"return '>'break; case'(':return '<'break;case')':return '>'break;case'=':return '<'break; case'(':switch(d)case'+':return '<'break; case'-':return '<'break; case'*':

42、return '<'break; case'/':return '<'break; case'"return '<'break; case'(':return '<'break; case'=':return '<'break; case')':switch(d)case'+':return '>'break; case'-':return '>'break; case'*':return '>'break; case'/':return '>'break; case'"return '>'break; case'(':return '='break; case')':return '>