棧和隊列及其應用(實驗三)

實驗三棧和隊列及其應用實驗目的及要求掌握棧和隊列這兩種特殊的線性表，熟悉它們的特性，在實際問題背景下靈活運用它們；本實驗訓練的要點是“棧”的觀點及其典型用法；掌握問題求解的狀態(tài)表示及其遞歸算法，以及由遞歸程序到非遞歸程序的轉(zhuǎn)化方法。實驗內(nèi)容編程實現(xiàn)棧在兩種存儲結(jié)構(gòu)中的根本操作〔棧的初始化、判?？?、入棧、出棧等〕；應用棧的根本操作，實現(xiàn)數(shù)制轉(zhuǎn)換〔任意進制〕；編程實現(xiàn)隊列在兩種存儲結(jié)構(gòu)中的根本操作〔隊列的初始化、判隊列空、入隊列、出隊列〕；利用棧實現(xiàn)任一個表達式中的語法檢查〔括號的匹配〕。利用棧實現(xiàn)表達式的求值。實驗主要流程、根本操作或核心代碼、算法片段〔該局部如不夠填寫，請另加附頁〕編程實現(xiàn)棧在兩種存儲結(jié)構(gòu)中的根本操作〔棧的初始化、判棧空、入棧、出棧等〕；程序代碼局部：順序存儲頭文件：#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineINFEASTALE-1#defineOVERFLOW-2功能函數(shù)：typedefintStatus;typedefintSElemType;typedefstruct{ SElemType*base; SElemType*top;intstacklength;}Sqstack;StatusInit(Sqstack&S);StatusDestroy(Sqstack&S);StatusClear(Sqstack&S);StatusEmpty(SqstackS);intLength(SqstackS);StatusGetTop(SqstackS,SElemType&e);StatusPush(Sqstack&S,SElemTypee);StatusPop(Sqstack&S,SElemType&e);#include"stdio.h"#include"stdlib.h"#include"1.h"StatusInit(Sqstack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacklength=STACK_INIT_SIZE;returnOK;}StatusDestroy(Sqstack&S){S.base=NULL; returnOK;}StatusClear(Sqstack&S){S.base=S.top; returnOK;}StatusEmpty(SqstackS){if(S.base==S.top){returnTRUE;}elsereturnFALSE;}intLength(SqstackS){returnS.top-S.base;}StatusGetTop(SqstackS,SElemType&e){if(S.base==S.top)returnERROR;e=*(S.top-1);returnOK;}StatusPush(Sqstack&S,SElemTypee){if(S.top-S.base>=STACK_INIT_SIZE){S.base=(SElemType*)realloc(S.base,(S.stacklength+STACKINCREMENT)*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacklength; S.stacklength+=STACKINCREMENT;}*S.top++=e;returnOK;}StatusPop(Sqstack&S,SElemType&e){if(S.base==S.top)exit(ERROR);e=*--S.top;returnOK;}主函數(shù)：#include"stdio.h"#include"stdlib.h"#include"1.h"intmain(){printf("是否創(chuàng)立空棧？\n");printf("1、創(chuàng)立\n2、退出\n");inta;//選擇scanf("%d",&a);if(a==2)exit(ERROR);SqstackS;Init(S);intlength;printf("請確定元素個數(shù)\n");scanf("%d",&length);printf("請輸入具體元素〔空格隔開〕\n");intd;//用于循環(huán)for(d=0;d<length;d++){scanf("%d",S.top); S.top++;}intb;//選擇功能do{printf("請選擇以下功能：\n");printf("1、銷毀棧\n");printf("2、置空棧\n");printf("3、判空\n");printf("4、棧的長度\n");printf("5、取棧頂元素\n");printf("6、插入新的棧頂元素\n");printf("7、刪除棧頂元素\n");printf("0、結(jié)束程序\n");scanf("%d",&b); switch(b) { case1: { Destroy(S); printf("棧已銷毀"); } break; case2: { Clear(S); printf("棧已清空\n"); } break; case3: { inta;//承載返回值 a=Empty(S); if(a==1) { printf("此棧為空\n"); } elseprintf("此棧不為空\n"); } break; case4: { printf("此時棧的長度為：%d\n",Length(S)); } break; case5: { SElemTypee; GetTop(S,e); printf("此時的棧頂元素為：%d\n",e); } break; case6: { inte; printf("請輸入新的棧頂元素\n"); scanf("%d",&e); Push(S,e); SElemType*p; p=S.base; printf("此時棧中元素有：\n"); while(p!=S.top) { printf("%d",*p); p++; } printf("\n"); } break; case7: { SElemTypee; Pop(S,e); SElemType*p; p=S.base; printf("被刪除的棧頂元素為：%d\n",e); printf("此時棧中元素為：\n");while(p!=S.top) { printf("%d",*p); p++; } printf("\n"); } break; case0:printf("程序結(jié)束！\n");break; default:printf("輸入錯誤\n"); }}while(b!=0&&b!=1);if(b==1){printf("假設(shè)需進行其他功能，那么要重啟程序，新建空棧\n");}return0;}鏈式存儲頭文件：#defineOK1#defineERROR0#defineTRUE1#defineFALSE0typedefintStatus;typedefintSElemType;typedefstructLNode{SElemTypedata;structLNode*next;}LNode,*LinkList;StatusInit(LinkList&SL,intnum1);StatusPush(LinkList&SL,inte,int&num1);StatusPop(LinkList&SL,int&e,int&num1);StatusGet(LinkListSL);StatusClear(LinkList&SL,int&num1);voidEmply(LinkListSL);功能函數(shù)：#include"stdio.h"#include"1.h"#include"stdlib.h"StatusInit(LinkList&SL,intnum1){printf("請輸入相應個數(shù)的各個具體元素〔空格隔開〕\n");SL=(LinkList)malloc(sizeof(LNode));scanf("%d",&SL->data);SL->next=NULL;for(inti=0;i<num1-1;i++){LinkLists=NULL; s=(LinkList)malloc(sizeof(LNode));scanf("%d",&s->data);s->next=SL;SL=s;}returnOK;}StatusGet(LinkListSL){returnSL->data;}StatusClear(LinkList&SL,int&num1){if(SL==NULL)printf("該棧本就為空\n");returnERROR;while(!SL){LinkListp=SL; if(p->next!=NULL){SL=p->next;free(p); } else { free(SL); }}if(SL==NULL){ num1=0;printf("該棧已清空\n");}else{printf("清空功能沒有正常完成！\n");}returnOK;}voidEmply(LinkListSL){if(SL==NULL){printf("該棧為空\n");}else{printf("該棧不為空\n");}}StatusPush(LinkList&SL,inte,int&num1){LinkLists=NULL;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=SL;SL=s;num1++;returnOK;}StatusPop(LinkList&SL,int&e,int&num1){e=SL->data;LinkLists;s=SL;SL=SL->next;free(s);num1--;returnOK;}主函數(shù)：#include"stdio.h"#include"stdlib.h"#include"1.h"intmain(){printf("是否建立鏈棧？\n");printf("1、建立\n");printf("2、不建立并退出程序\n");inta;//選擇建立scanf("%d",&a);switch(a){case1: { LinkListSL=NULL; intnum;//用戶確定的元素個數(shù) printf("請確定元素個數(shù)\n"); scanf("%d",&num); Init(SL,num); printf("此時的鏈棧中元素為(從棧頂?shù)綏５?：\n"); LinkListb=SL; for(inti=0;i<num;i++) { printf("%d",b->data); b=b->next; } printf("\n"); printf("請選擇以下功能：\n");intx;//用于選擇功能 do { printf("1、入棧\n");printf("2、出棧\n"); printf("3、查看棧頂元素\n"); printf("4、清空棧\n"); printf("5、判空\n"); printf("6、查看棧的長度\n"); printf("0、結(jié)束程序\n"); scanf("%d",&x); switch(x) { case1: { printf("請輸入新的棧頂元素\n"); intdata;//用戶輸入的新的棧頂元素 scanf("%d",&data); Push(SL,data,num);printf("此時的鏈棧中元素為(從棧頂?shù)綏５?：\n"); LinkListb=SL; for(inti=0;i<num;i++) { printf("%d",b->data); b=b->next; } printf("\n"); } break;case2: { inte;//用于承載棧頂元素 Pop(SL,e,num); printf("出棧的元素為：%d\n",e);printf("此時棧中的元素有(從棧頂?shù)綏５?：\n"); LinkListb=SL; for(inti=0;i<num;i++) { printf("%d",b->data); b=b->next; } printf("\n"); } break; case3: { printf("此時的棧頂元素為：%d\n",Get(SL)); } break; case4: { Clear(SL,num); } break; case5: { Emply(SL); } break; case6: { printf("此時棧長為：%d\n",num); } break; case0:printf("程序結(jié)束！\n"); break; default:printf("程序輸入錯誤！\n"); } }while(x!=0); } break;case2: printf("程序結(jié)束！\n"); break;default:printf("輸入錯誤！\n");}return0;}運行結(jié)果：〔2〕 應用棧的根本操作，實現(xiàn)數(shù)制轉(zhuǎn)換〔任意進制〕；程序代碼局部：頭文件：#defineOK1#defineERROR0#define TRUE1#defineFAULSE0#defineOVERFL-1#defineFEASIBLE-2#defineINIT100#defineINCR10typedefintStatus;typedefintSElemType;typedefstruct{ SElemType*top; SElemType*base; intstacksize;}Stack;voidInit(Stack&S);voidPush(Stack&S,SElemType&e);StatusPop(Stack&S,SElemType&e);StatusEmpty(StackS);voidd_to_other(inta,intd);voidother_to_d(inta,intc);intother_to_d2(inta,intc);voidother_to_other(inta,intc,intd);voidxiaoshu_d_to_other(doublep,intd);voidd_to_other2(inta,intd);功能函數(shù)：#include"stdio.h"#include"stdlib.h"#include"1.h"http://創(chuàng)立棧voidInit(Stack&S){S.base=(SElemType*)malloc(INIT*sizeof(SElemType));if(!S.base)exit(OVERFL);S.top=S.base;S.stacksize=INIT;}//入棧voidPush(Stack&S,SElemType&e){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(INCR+INIT)*sizeof(SElemType));if(!S.base)exit(OVERFL); S.top=S.base+S.stacksize; S.stacksize+=INCR;}*S.top++=e;}StatusPop(Stack&S,SElemType&e){if(S.base==S.top)returnERROR;e=*--S.top;returnOK;}//判空StatusEmpty(StackS){if(S.base==S.top){returnOK;}elsereturnERROR;}//十進制整數(shù)轉(zhuǎn)換成其他進制voidd_to_other(inta,intd)//用戶輸入的十進制數(shù)的整數(shù)局部和目的進制{ StackS;Init(S); intm;while(a) { m=a%d;Push(S,m);a=a/d; } inte; printf("該數(shù)對應的%d進制為：\n",d); while(!Empty(S)) { Pop(S,e); if(e>9) { printf("%c",e-10+'A'); } else { printf("%d",e); } } printf("\n");}//其他進制數(shù)轉(zhuǎn)換為十進制voidother_to_d(inta,intc)//用戶輸入的其他進制數(shù)和該數(shù)的進制{intb;intn,d=0,e=0;//余數(shù)其他進制數(shù)各個位對應的十進制其他進制數(shù)的第幾位幾位轉(zhuǎn)換成十進制的和while(a){b=a%10; d++; if(b==1&&d>1) { n=1; for(inti=d;i>1;i--) { n=c*n; } e=e+n; } elseif(b==1&&d==1) { n=1; e=e+n; } elseif(b==0) { a=a/10; continue; } a=a/10;}printf("該數(shù)對應的十進制數(shù)為：\n");printf("%d\n",e);}//其他進制數(shù)轉(zhuǎn)換為十進制(只用于其他功能函數(shù)內(nèi))intother_to_d2(inta,intc)//用戶輸入的其他進制數(shù)和該數(shù)的進制{intb;intn,d=0,e=0;//余數(shù)其他進制數(shù)各個位對應的十進制其他進制數(shù)的第幾位幾位轉(zhuǎn)換成十進制的和while(a){b=a%10; d++; if(b==1&&d>1) { n=1; for(inti=d;i>1;i--) { n=c*n; } e=e+n; } elseif(b==1&&d==1) { n=1; e=e+n; } elseif(b==0) { a=a/10; continue; } a=a/10;}returne;}//其他進制轉(zhuǎn)換為其他進制voidother_to_other(inta,intc,intd)//用戶輸入的數(shù)原數(shù)進制目的進制{intg;//承載該數(shù)轉(zhuǎn)化后的十進制數(shù)g=other_to_d2(a,c);d_to_other(g,d);}//十進制整數(shù)轉(zhuǎn)換成其他進制(只用于含小數(shù)局部的十進制整數(shù))voidd_to_other2(inta,intd)//用戶輸入的十進制數(shù)的整數(shù)局部和目的進制{ StackS;Init(S); intm;while(a) { m=((int)a)%d;Push(S,m);a=a/d; } SElemTypee; printf("該數(shù)對應的%d進制為：\n",d); while(!Empty(S)) { Pop(S,e); if(e>9) { printf("%c",e-10+'A'); } else { printf("%d",e); } }}//小數(shù)局部：十進制轉(zhuǎn)換成其他進制voidxiaoshu_d_to_other(doublep,intd)//小數(shù)局部和目的進制{ inta[20];//用于存放已經(jīng)轉(zhuǎn)化了的位 inti=0;while(p) {a[i]=(int)floor(p*d); p=p*d-(double)a[i]; i++; if(i>=20) { printf("該小數(shù)可能不能轉(zhuǎn)化為有限的%d進制的數(shù)\n",d); exit(ERROR); } }StackQ;Init(Q); SElemTypee; while(i) { Push(Q,a[i-1]); i--; } while(!Empty(Q)) { Pop(Q,e); if(e>9) { printf("%c",e-10+'A'); } else { printf("%d",e); } } printf("\n");}主函數(shù)：#include"stdio.h"#include"1.h"#include"stdlib.h"intmain(){intk;do{printf("請選擇一下操作\n"); printf("1、數(shù)制轉(zhuǎn)換\n"); printf("2、結(jié)束程序\n"); scanf("%d",&k); if(k==1) {intc=0,d=0;//用戶選擇原數(shù)進制、目的數(shù)進制printf("請輸入是幾進制變?yōu)閹走M制(空格隔開)\n");scanf("%d%d",&c,&d);if(c==10) {printf("確定輸入的數(shù)據(jù)的性質(zhì)\n"); printf("1、整數(shù)\n"); printf("2、含有小數(shù)局部\n"); inth; scanf("%d",&h); switch(h) { case1: { printf("請輸入源十進制整數(shù)\n"); inta; scanf("%d",&a); d_to_other(a,d); break; } case2: { doublea=0,p=0;//用戶輸入一個數(shù)〔非負〕、該數(shù)小數(shù)局部、 inti=0;//整數(shù)局部 printf("請輸入十進制實數(shù)\n");scanf("%lf",&a); i=(int)a; p=a-i;d_to_other2(i,d); printf("."); xiaoshu_d_to_other(p,d); break; } default:printf("輸入錯誤\n"); } }if(d==10) { inta; printf("請輸入%d進制數(shù)：\n",c); scanf("%d",&a); other_to_d(a,c); }if(c!=10&&d!=10) {inta; printf("請輸入%d進制數(shù)：\n",c); scanf("%d",&a); other_to_other(a,c,d); } } else { printf("程序結(jié)束！\n"); }}while(k!=2);return0;}運行結(jié)果：〔3〕編程實現(xiàn)隊列在兩種存儲結(jié)構(gòu)中的根本操作〔隊列的初始化、判隊列空、入隊列、出隊列〕；程序代碼：順序存儲頭文件：#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineOVERFLOW-1#defineINFEASIBLE-2#defineMAX4typedefintStatus;typedefintQElemType;typedefstruct{QElemType*base; intfront; intrear;}SqQueue;StatusInit(SqQueue&Q);StatusENQueue(SqQueue&Q,QElemTypee);StatusOUTQueue(SqQueue&Q,QElemType&e);StatusClearQueue(SqQueue&Q);StatusEmpty(SqQueueQ);功能函數(shù)：#include"stdio.h"#include"stdlib.h"#include"1.h"StatusInit(SqQueue&Q){Q.base=(QElemType*)malloc(sizeof(QElemType)*MAX);if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;returnOK;}StatusENQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAX==Q.front){returnERROR;}Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAX;returnOK;}StatusOUTQueue(SqQueue&Q,QElemType&e){if(Q.rear==Q.front)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAX;returnOK;}StatusClearQueue(SqQueue&Q){while(Q.rear!=Q.front){Q.front=(Q.front+1)%MAX;}returnOK;}StatusEmpty(SqQueueQ){if(Q.front!=Q.rear)returnERROR;returnOK;}主函數(shù)：#include"stdio.h"#include"1.h"intmain(){printf("是否創(chuàng)立隊列？\n");printf("1、創(chuàng)立\n");printf("2、結(jié)束程序\n");inta;scanf("%d",&a);if(a==2){return0;}else{SqQueueQ; if(Init(Q)==OK) { printf("隊列初始化完畢，最大容量為%d\n",MAX-1); } else { printf("隊列初始化失敗，程序結(jié)束\n"); returnERROR; } intb; do { printf("選擇以下操作\n"); printf("1、入隊\n");printf("2、出隊\n"); printf("3、清空隊\n"); printf("4、判空隊\n"); printf("0、結(jié)束程序\n"); scanf("%d",&b); switch(b) { case1: { printf("請輸入要插入的元素個數(shù)\n"); intnum; scanf("%d",&num); printf("請輸入要插入的元素：\n"); QElemTypee; intresult; for(inti=0;i<num;i++) { scanf("%d",&e); result=ENQueue(Q,e); if(result==ERROR) { printf("隊列已滿，第%d個元素無法再存入\n",i+1); } } inta=Q.front,b=Q.rear;printf("此時，隊列中的元素分別為：\n"); while(a!=b) { printf("%d",Q.base[a]); a=(a+1)%MAX; } printf("\n"); printf("\n"); printf("\n"); printf("\n"); break; } case2: { QElemTypee; intresult; result=OUTQueue(Q,e); if(result==ERROR) { printf("此隊列為空，當前沒有元素\n"); } else { printf("此時頭元素為：%d\n",e); }inta=Q.front,b=Q.rear;printf("此時，隊列中的元素分別為：\n"); while(a!=b) { printf("%d",Q.base[a]); a=(a+1)%MAX; } printf("\n"); printf("\n"); printf("\n"); printf("\n"); break; } case3: { intresult; result=ClearQueue(Q); if(result==OK) { printf("隊列已清空\n"); } else { printf("隊列清空失敗\n"); } printf("\n"); printf("\n"); printf("\n"); break; } case4: { intresult; result=Empty(Q); if(result==OK) { printf("此隊列為空\n"); } else { printf("此隊列不為空\n"); } printf("\n"); printf("\n"); printf("\n"); break; } case0: printf("程序結(jié)束！\n"); break;default:printf("輸入錯誤!\n"); } }while(b!=0);}}鏈式存儲頭文件：#defineOK1#defineERROR0#defineOVERFLOW-1typedefintStatus;typedefintQElemType;typedefstructQNode{structQNode*next;QElemTypedata;}QNode,*Queue;typedefstruct{Queuefront;Queuerear;}LinkQueue;StatusInit(LinkQueue&Q);voidENQueue(LinkQueue&Q,QElemTypee);StatusDEQueue(LinkQueue&Q,QElemType&e);StatusClear(LinkQueue&Q);StatusEmpty(LinkQueueQ);功能函數(shù)：#include"stdio.h"#include"stdlib.h"#include"1.h"StatusInit(LinkQueue&Q){Q.front=Q.rear=(Queue)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnOK;}voidENQueue(LinkQueue&Q,QElemTypee){Queues;Queuep=Q.rear;s=(Queue)malloc(sizeof(QNode));if(!s){ printf("分配存儲空間失敗\n"); exit(OVERFLOW);}s->data=e;s->next=NULL;Q.rear->next=s;Q.rear=s;p->next=s;}StatusDEQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear){returnERROR;}e=Q.front->next->data;Queues=Q.front->next;Q.front->next=s->next;free(s);returnOK;}StatusClear(LinkQueue&Q){Queues;while(Q.front->next!=Q.rear){s=Q.front->next;Q.front->next=s->next; free(s);}s=Q.rear;free(s);Q.rear=Q.front;Q.front->next=NULL;returnOK;}StatusEmpty(LinkQueueQ){if(Q.front==Q.rear&&Q.front->next==NULL){returnOK;}else{returnERROR;}}主函數(shù)：#include"stdio.h"#include"stdlib.h"#include"1.h"intmain(){printf("是否建立隊列\(zhòng)n");printf("1、建立\n");printf("2、不建立并結(jié)束程序\n");inta;scanf("%d",&a);if(a==1){ intnum; LinkQueueQ; if(Init(Q)==1) { printf("隊列初始化成功\n"); } else { printf("隊列初始化失敗，程序結(jié)束\n"); exit(1); } printf("請選擇一下功能\n"); intb; do { printf("1、入隊列\(zhòng)n"); printf("2、出隊列\(zhòng)n"); printf("3、清空隊列\(zhòng)n"); printf("4、隊列判空\n"); printf("0、結(jié)束程序\n"); scanf("%d",&b); switch(b) { case1: { printf("請確定入隊元素個數(shù)\n"); scanf("%d",&num);printf("請輸入具體元素\n"); inte; for(inti=0;i<num;i++) {scanf("%d",&e); ENQueue(Q,e); }printf("此時的隊列中元素分別為：\n"); Queuep=Q.front->next; for(intj=0;j<num;j++) { printf("%d",p->data); p=p->next; } printf("\n");printf("\n"); break; } case2: { QElemTypee; intresult; result=DEQueue(Q,e); if(result==OK) { printf("隊列中頭元素為：%d\n",e); num--;printf("此時的隊列中元素分別為：\n"); Queuep=Q.front->next; for(intj=0;j<num;j++) { printf("%d",p->data); p=p->next; } printf("\n");printf("\n"); } else { printf("此時的隊列為空，沒有元素能取出\n"); returnERROR; } printf("\n");printf("\n"); break; } case3: { if(Clear(Q)==OK) { printf("隊列已清空\n"); } else { printf("隊列清空失敗\n"); } printf("\n");printf("\n"); break; } case4: { if(Empty(Q)==OK) { printf("該隊列為空\n"); } else { printf("該隊列不為空\n"); } printf("\n");printf("\n"); break; } case0: printf("程序結(jié)束\n"); break; default:printf("輸入錯誤\n"); } }while(b!=0);}elseif(a==2){printf("程序結(jié)束\n"); return0;}else{printf("輸入錯誤\n"); exit(1);}return0;}運行結(jié)果：〔4〕利用棧實現(xiàn)任一個表達式中的語法檢查〔括號的匹配〕。程序代碼：頭文件：#defineOK1#defineERROR0#defineOVERFLOW-1#definesize20typedefintStatus;typedefcharSElemType;typedefstruct{SElemType*base;SElemType*top;intStacksize;}SqStack;StatusInit(SqStack&s);StatusENStack(SqStack&s,SElemTypee);StatusDEStack(SqStack&s,SElemType&e);功能函數(shù)：#include"stdio.h"#include"stdlib.h"#include"1.h"StatusInit(SqStack&s){s.base=(SElemType*)malloc(sizeof(SElemType)*size);if(!s.base)exit(OVERFLOW);s.top=s.base;returnOK;}StatusENStack(SqStack&s,SElemTypee){if((s.top-s.base)>=size){SElemType*newbase; newbase=(SElemType*)realloc(s.base,sizeof(SElemType)*(s.Stacksize+size)); if(!newbase)exit(OVERFLOW); s.base=newbase; s.Stacksize+=size;}*s.top++=e;returnOK;}StatusDEStack(SqStack&s,SElemType&e){if(s.base==s.top){returnERROR;}e=*--s.top;returnOK;}主函數(shù)：#include"stdio.h"#include"stdlib.h"#include"1.h"intmain(){SqStacks;s.Stacksize=size;if(Init(s)==OK){printf("已經(jīng)成功初始化一個空棧\n");}else{printf("棧的初始化失敗\n"); exit(ERROR);}printf("請輸入要檢測的表達式〔各個符號間用空格隔開,以#表示輸入完成〕\n");SElemTypea[size];for(inti=0;i<size;i++){scanf("%c",&a[i]); if(a[i]=='#') { break; } if(a[i]=='('||a[i]=='['||a[i]=='{') { ENStack(s,a[i]); } if(a[i]==')'||a[i]==']'||a[i]=='}') { SElemTypee; DEStack(s,e); if(a[i]==')') { if(e!='(') { printf("該表達式括號匹配不正確\n"); returnERROR; } } if(a[i]==']') { if(e!='[') { printf("該表達式括號匹配不正確\n"); returnERROR; } } if(a[i]=='}') { if(e!='{') { printf("該表達式括號匹配不正確\n"); returnERROR; } } }}printf("該表達式括號匹配正確\n");returnOK;}運行結(jié)果：〔5〕利用棧實現(xiàn)表達式的求值。未完成頭文件：#defineOK1#defineERROR0#defineOVERFLOW-1#definesize20typedefintStatus;typedefcharSElemType;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInit(SqStack&S);StatusENStack(SqStack&S,SElemTypee);StatusDEd_Stack(SqStack&S,SElemType*&e);StatusDEs_Stack(SqStack&S,SElemType&e);SElemTypeGetStack(SqStackS,SElemType&e);SElemTypecmp(SElemTypee1,SElemTypee2);功能函數(shù)：#include"stdio.h"#include"stdlib.h"#include"1.h"http://棧的初始化StatusInit(SqStack&S){S.base=(SElemType*)malloc(sizeof(SElemType)*size);if(!S.base){ printf("存儲空間分配失敗\n"); exit(OVERFLOW);}S.top=S.base;S.stacksize=size;returnOK;}//入棧StatusENStack(SqStack&S,SElemTypee){if(S.top-S.base+1>=S.stacksize){SElemType*newbase; newbase=(SElemType*)realloc(S.base,sizeof(SElemType)*(S.stacksize+size)); if(!newbase) { printf("新增存儲空間失敗\n"); exit(OVERFLOW); } S.base=newbase; S.top=S.base+S.stacksize-1; S.stacksize+=size;}*S.top++=e;returnOK;}//數(shù)值出棧StatusDEd_Stack(SqStack&S,SElemType*&e){if(S.base==S.top){printf("此時棧為空\n"); returnERROR;}e=--S.top;returnOK;}//算符出棧StatusDEs_Stack(SqStack&S,SElemType&e){if(S.base==S.top){printf("此時棧為空\n"); returnERROR;}e=*--S.top;returnOK;}//查看棧頂元素SElemTypeGetStack(SqStackS,SElemType&e){