1、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)二學(xué)院：自動化學(xué)院班級：_學(xué)號：_姓名：_一、實(shí)驗(yàn)?zāi)康?1、熟悉VC環(huán)境，學(xué)習(xí)使用C語言實(shí)現(xiàn)棧的存儲結(jié)構(gòu)。2、通過編程、上機(jī)調(diào)試，進(jìn)一步理解棧的基本概念。3、鍛煉動手編程，獨(dú)立思考的能力。二、實(shí)驗(yàn)內(nèi)容 實(shí)現(xiàn)簡單計(jì)算器的功能,請按照四則運(yùn)算加、減、乘、除、冪（）和括號的優(yōu)先關(guān)系和慣例，編寫計(jì)算器程序。要求支持運(yùn)算符：+、-、*、/、%、（）和=：從鍵盤輸入一個(gè)完整的表達(dá)式，以回車作為表達(dá)式輸入結(jié)束的標(biāo)志；輸入表達(dá)式中的數(shù)值均為大于等于零的整數(shù)，如果中間計(jì)算過程中出現(xiàn)小數(shù)也只取整進(jìn)行計(jì)算。例如，輸入：4+2*5=輸出：14 輸入：(4+2)*(2-10)=輸出：-48

2、三、程序設(shè)計(jì) 1、概要設(shè)計(jì)為實(shí)現(xiàn)上述程序功能，應(yīng)使用兩個(gè)棧，分別寄存操作數(shù)與運(yùn)算符。為此，需要棧的抽象數(shù)據(jù)結(jié)構(gòu)。(1)、棧的抽象數(shù)據(jù)類型定義為：ADT Stack數(shù)據(jù)對象：D=數(shù)據(jù)關(guān)系：R1= 約定端為棧頂，端為棧底?；静僮鳎篒nitStack(&S)操作結(jié)果：創(chuàng)建一個(gè)空棧S。GetTop(S,&e)初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。Push(&S,e)初始條件：棧S已存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop(&S,&e)初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。In(m,a)操作結(jié)果：若

3、m是運(yùn)算符，返回TRUE。Precede(m, n)初始條件：m，n為運(yùn)算符。操作結(jié)果：若m優(yōu)先級大于n，返回>，反之亦然。Operation(a, theta,b)初始條件：a，b為整數(shù)，theta為運(yùn)算符。操作結(jié)果：返回a與b運(yùn)算的結(jié)果。EvaluateExpression(p)初始條件：輸入合法的表達(dá)式。操作結(jié)果：返回表達(dá)式的值。ADT Stack(2)、宏定義#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OVERFLOW -2#define OK 1#define ERROR 0#define TRUE 1

4、#define FALSE 0(3)、主程序流程首先定義char型數(shù)組，將輸入的表達(dá)式存入。隨后調(diào)用EvaluateExpression(expression)函數(shù)計(jì)算結(jié)果，最后輸出在屏幕上。(4)、模塊調(diào)用關(guān)系：由主函數(shù)模塊調(diào)用輸入模塊與求值模塊。求值模塊調(diào)用表達(dá)式轉(zhuǎn)化模塊與表達(dá)式求職模塊，計(jì)算并返回表達(dá)式的值。最后主程序調(diào)用輸出模塊輸出結(jié)果。(5)、流程圖開始輸入表達(dá)式char c=表達(dá)式首字符c!='='|GetTop1(OPTR)!='='!In(c,OP)c存入數(shù)組;c=*(+ex);In(c,OP)數(shù)組中的數(shù)壓入棧內(nèi);指針指向數(shù)組首元素case &#

5、39;<':符號進(jìn)棧 c=*(+ex);case '=':符號出棧c=*(+ex);case '>':操作數(shù)棧前2個(gè)數(shù)運(yùn)算return GetTop2(OPND)輸出result結(jié)束 2、詳細(xì)設(shè)計(jì)(1)、數(shù)據(jù)類型設(shè)計(jì)typedef structchar *base;char *top;int stacksize;SqStack1; /定義運(yùn)算符棧數(shù)據(jù)類型typedef structint *base;int *top;int stacksize;SqStack2; /定義操作數(shù)棧數(shù)據(jù)類型SqStack1 OPTR; /聲明運(yùn)算符棧SqStac

6、k2 OPND; /聲明操作數(shù)棧(2)、操作算法設(shè)計(jì)Status InitStack1(SqStack1 &S)/構(gòu)造運(yùn)算符棧S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);/申請空間if(!S.base)exit(OVERFLOW); /存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack1Status InitStack2(SqStack2 &S)/構(gòu)造操作數(shù)棧S.base=(int *)malloc(STACK_INIT_SIZE*siz

7、eof(int);/申請空間if(!S.base)exit(OVERFLOW); /存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack2char GetTop1(SqStack1 S)/取得運(yùn)算符棧的棧頂元素char e;if(S.top=S.base) return ERROR; /棧空e=*(S.top-1);return e;/GetTop1int GetTop2(SqStack2 S)/取得操作數(shù)棧的棧頂元素int e;if(S.top=S.base) return ERROR; /?？誩=*(S.to

8、p-1);return e;/GetTop2Status Push1(SqStack1 &S,char e)/插入元素e為運(yùn)算符棧的棧頂元素if(S.top-S.base>=S.stacksize)/棧滿，追加存儲空間S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S.base) exit(OVERFLOW);/存儲分配失敗S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/Push1

9、Status Push2(SqStack2 &S,int e)/插入元素e為操作數(shù)棧的棧頂元素if(S.top-S.base>=S.stacksize) /棧滿，追加存儲空間S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int);if(!S.base) exit(OVERFLOW); /存儲分配失敗S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/Push2Status Pop1(SqStack1 &a

10、mp;S,char &e)/刪除表達(dá)式棧的棧頂元素并用e返回if(S.top=S.base) return ERROR; /棧空e=*-S.top;return OK;/Pop1Status Pop2(SqStack2 &S,int &e)/刪除表達(dá)式棧的棧頂元素并用e返回if(S.top=S.base) return ERROR; /?？誩=*-S.top;return OK;/Pop2Status In(int m,char a)/判斷m若是運(yùn)算符，返回TRUE，否則返回FALSEfor(int n=0;an!='0'n+)if(m=an) retu

11、rn TRUE;return FALSE;/Inchar Precede(char m,char n)/判斷m與n的優(yōu)先級switch(m)case'+':case'-':if(n='+'|n='-'|n=')'|n='=')return '>'else return '<'break;case'*':case'/':case'':case'%':if(n='(')return

12、 '<'else return '>'break;case'(':if(n=')')return '='else if(n='=')return ERROR;else return '<'break;case')':if(n='(')return ERROR;else return '>'break;case'=':if(n='=')return '='else i

13、f(n=')')return ERROR;else return '<'break;default:return ERROR;break;/其他情況，表達(dá)式有誤/ Precedeint Operation(int a,char theta,int b)/運(yùn)算函數(shù)switch(theta)case'+':return a+b;break;case'-':return a-b;break;case'*':return a*b;break;case'/':return a/b;break;case&

14、#39;%':return a%b;break;case'':return pow(a,b);break;default:return ERROR;break;/Operationint EvaluateExpression(char p)/主要操作函數(shù)int a,b,t;char x,theta,temp10;char* num=temp;char* ex=p;/聲明指針I(yè)nitStack1(OPTR);Push1(OPTR,'=');InitStack2(OPND);char c=*p;while(c!='='|GetTop1(OPT

15、R)!='=')if(!In(c,OP)/不是運(yùn)算符進(jìn)數(shù)組*(num+)=c;c=*(+ex);if(In(c,OP)/是運(yùn)算符將數(shù)組壓入棧*num='0't=atoi(temp);/將temp數(shù)組轉(zhuǎn)化為整型數(shù)num=temp;/指針指回?cái)?shù)組頭元素Push2(OPND,t);elseswitch(Precede(GetTop1(OPTR),c)case '<':/棧頂元素優(yōu)先級低Push1(OPTR,c);c=*(+ex);break;case '=':/脫括號并接受下一字符Pop1(OPTR,x);c=*(+ex);bre

16、ak;case '>':/運(yùn)算并將結(jié)果入棧Pop1(OPTR,theta);Pop2(OPND,b);Pop2(OPND,a);Push2(OPND,Operation(a,theta,b);break;return GetTop2(OPND);返回操作數(shù)棧頂元素/ EvaluateExpression(3)、主函數(shù)設(shè)計(jì)int main()/主函數(shù)int result;char expression100; /聲明表達(dá)式數(shù)組printf("Please input the expression:");gets(expression); /輸入數(shù)組res

17、ult=EvaluateExpression(expression);printf("the result is :%dn",result);/輸出結(jié)果return 0;四、程序調(diào)試分析 1、開始時(shí)，使用getchar函數(shù)輸入，但其有較大的弊端，只能輸入0-9之間的整數(shù)，不能實(shí)現(xiàn)多位數(shù)及小數(shù)的計(jì)算。于是換為gets函數(shù)，將表達(dá)式作為整體存入數(shù)組中待處理。2、第一個(gè)問題解決后，出現(xiàn)了第二個(gè)問題：數(shù)據(jù)結(jié)構(gòu)混亂。由于gets函數(shù)得到的是char型，直接存入操作數(shù)棧后，以ASCII碼形式存入，使得編譯通過但運(yùn)行結(jié)果錯誤。后來分析原因后，引入暫存數(shù)組，利用atoi函數(shù)，將數(shù)組中的數(shù)轉(zhuǎn)

18、化為整型，解決了這一問題。3、在設(shè)計(jì)主要處理函數(shù)時(shí)，出現(xiàn)了多次編譯錯誤。后發(fā)現(xiàn)是由于指針指向混亂造成。這主要是自己的思路不清，導(dǎo)致程序混亂。后仔細(xì)繪制了流程圖，詳盡的分析了過程后，解決了該問題。五、用戶使用說明 1、本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：Josegh.exe。2、進(jìn)入程序后，在Please input the expression:后輸入待求表達(dá)式，以“=”結(jié)尾，并敲回車。 3、程序運(yùn)行后即在屏幕上輸出計(jì)算結(jié)果。六、程序運(yùn)行結(jié)果 1、 2、七、程序清單#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define

19、OVERFLOW -2#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#include"stdio.h"#include"stdlib.h"#include"math.h"typedef int Status;char OP='+','-','*','/','(',')','','%','=' /定義運(yùn)算符數(shù)組typedef st

20、ructchar *base;char *top;int stacksize;SqStack1; /定義運(yùn)算符棧數(shù)據(jù)類型typedef structint *base;int *top;int stacksize;SqStack2; /定義操作數(shù)棧數(shù)據(jù)類型SqStack1 OPTR; /聲明運(yùn)算符棧SqStack2 OPND; /聲明操作數(shù)棧Status InitStack1(SqStack1 &S)/構(gòu)造運(yùn)算符棧S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);/申請空間if(!S.base)exit(OVERFLOW); /存儲分

21、配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status InitStack2(SqStack2 &S)/構(gòu)造操作數(shù)棧S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int);/申請空間if(!S.base)exit(OVERFLOW); /存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;char GetTop1(SqStack1 S)/取得運(yùn)算符棧的棧頂元素char e;if(S.top=S.base) return

22、 ERROR; /棧空e=*(S.top-1);return e;int GetTop2(SqStack2 S)/取得操作數(shù)棧的棧頂元素int e;if(S.top=S.base) return ERROR; /?？誩=*(S.top-1);return e;Status Push1(SqStack1 &S,char e)/插入元素e為運(yùn)算符棧的棧頂元素if(S.top-S.base>=S.stacksize)/棧滿，追加存儲空間S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S

23、.base) exit(OVERFLOW);/存儲分配失敗S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Push2(SqStack2 &S,int e)/插入元素e為操作數(shù)棧的棧頂元素if(S.top-S.base>=S.stacksize) /棧滿，追加存儲空間S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int);if(!S.base) exit(OVERFLOW); /存儲分配失敗

24、S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop1(SqStack1 &S,char &e)/刪除表達(dá)式棧的棧頂元素并用e返回if(S.top=S.base) return ERROR; /?？誩=*-S.top;return OK;Status Pop2(SqStack2 &S,int &e)/刪除表達(dá)式棧的棧頂元素并用e返回if(S.top=S.base) return ERROR; /?？誩=*-S.top;return OK;Status

25、 In(int m,char a)/判斷m若是運(yùn)算符，返回TRUE，否則返回FALSEfor(int n=0;an!='0'n+)if(m=an) return TRUE;return FALSE;char Precede(char m,char n)/判斷m與n的優(yōu)先級switch(m)case'+':case'-':if(n='+'|n='-'|n=')'|n='=')return '>'else return '<'break;cas

26、e'*':case'/':case'':case'%':if(n='(')return '<'else return '>'break;case'(':if(n=')')return '='else if(n='=')return ERROR;else return '<'break;case')':if(n='(')return ERROR;else r

27、eturn '>'break;case'=':if(n='=')return '='else if(n=')')return ERROR;else return '<'break;default:return ERROR;break;/其他情況，表達(dá)式有誤int Operation(int a,char theta,int b)/運(yùn)算函數(shù)switch(theta)case'+':return a+b;break;case'-':return a-b;break;case'*':return a*b;break;case'/':return a/b;break;case'%':return a%b;break;case'':