1、C語言與數(shù)據(jù)結構課程設計報告       學 號 2010013314  姓 名 馮國偉 課程設計題目 16、括號匹配問題問題描述：假設一個算術表達式中可包含三種括號：圓括號，方括號和花括號且這三種括號可按任意次序嵌套使用。試利用棧的運算，編寫判別給定表達式中所含括號是否正確配對出現(xiàn)的算法。基本要求：從鍵盤輸入表達式，判斷該表達式中各種括號是否匹配，輸入判斷結果。測試數(shù)據(jù)：（1）括號匹配的表達式： a+b*c-d/2 (20/5+(4-3)/2)（2）括號不匹配的表達式： (a+b)*c) 1+2)  

2、2011 年 12 月 目 錄1 需求分析 1.1 功能與數(shù)據(jù)需求 1.1.1 題目要求的功能 1.1.2 擴展功能 1.2 界面需求 1.3 開發(fā)環(huán)境與運行需求 2 概要設計 2.1主要數(shù)據(jù)結構2.2程序總體結構2.3各模塊函數(shù)說明3 詳細設計3.1算法分析與設計3.2主要程序段設計4 測試5 使用說明5.1應用程序功能的詳細說明5.2應用程序運行環(huán)境要求5.5輸入數(shù)據(jù)類型、格式和內(nèi)容限制6 總結提高6.1課程設計總結6.2開發(fā)中遇到的問題和解決方法6.3 對自己完成課設完成情況的評價6.4C語言與數(shù)據(jù)結構課程設計課程的意見與建議附錄：程序源代碼 typedef char SEle

3、mType;#include<string.h>#include<ctype.h>#include<malloc.h> /* malloc()等 */#include<limits.h> /* INT_MAX等 */#include<stdio.h> /* EOF(=Z或F6),NULL */#include<stdlib.h> /* atoi() */#include<io.h> /* eof() */#include<math.h> /* floor(),ceil(),abs() */#incl

4、ude<process.h> /* exit() */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/* #define OVERFLOW -2 因為在math.h中已定義OVERFLOW的值為3,故去掉此行 */typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結果狀態(tài)代碼，如OK等 */typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */#define STACK_INIT_SIZE 1

5、0 /* 存儲空間初始分配量 */#define STACK_INCREMENT 2 /* 存儲空間分配增量 */typedef struct SqStackSElemType *base; /* 在棧構造之前和銷毀之后，base的值為NULL */SElemType *top; /* 棧頂指針 */int stacksize; /* 當前已分配的存儲空間，以元素為單位 */SqStack; /* 順序棧 */void InitStack(SqStack *S) /* 構造一個空棧S */(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(

6、SElemType);if(!(*S).base)exit(OVERFLOW); /* 存儲分配失敗 */(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;void DestroyStack(SqStack *S) /* 銷毀棧S，S不再存在 */free(*S).base);(*S).base=NULL;(*S).top=NULL;(*S).stacksize=0;void ClearStack(SqStack *S) /* 把S置為空棧 */(*S).top=(*S).base;Status StackEmpty(SqStack S) /*

7、 若棧S為空棧，則返回TRUE，否則返回FALSE */if(S.top=S.base)return TRUE;elsereturn FALSE;int StackLength(SqStack S) /* 返回S的元素個數(shù)，即棧的長度 */return S.top-S.base;Status GetTop(SqStack S,SElemType *e) /* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR */if(S.top>S.base)*e=*(S.top-1);return OK;elsereturn ERROR;void Push(SqStack *S,SEl

8、emType e) /* 插入元素e為新的棧頂元素 */if(*S).top-(*S).base>=(*S).stacksize) /* 棧滿，追加存儲空間 */(*S).base=(SElemType *)realloc(*S).base,(*S).stacksize+STACK_INCREMENT)*sizeof(SElemType);if(!(*S).base)exit(OVERFLOW); /* 存儲分配失敗 */(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACK_INCREMENT;*(*S).top)+=e;Stat

9、us Pop(SqStack *S,SElemType *e) /* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */if(*S).top=(*S).base)return ERROR;*e=*-(*S).top;return OK;void StackTraverse(SqStack S,void(*visit)(SElemType) /* 從棧底到棧頂依次對棧中每個元素調(diào)用函數(shù)visit() */while(S.top>S.base)visit(*S.base+);printf("n");void check() /* 對于輸入的任

10、意一個字符串，檢驗括號是否配對 */SqStack s;SElemType ch80,*p,e;InitStack(&s); /* 初始化棧成功 */printf("請輸入表達式：n");gets(ch);p=ch; /* p指向字符串的首字符 */while(*p) /* 沒到串尾 */switch(*p)case '(':case '':case '':Push(&s,*p+); /* 左括號入棧，且p+ */break;case ')':case '':case '':if(!StackEmpty(s) /* 棧不空 */Pop(&s,&e); /* 彈出棧頂元素 */if(!(e='('&&*p=')'|e=''&&*p=''|e=''&&*p='') /* 出現(xiàn)3種匹配情況之外的情況 */printf("左括號不正確！n");exit(ERROR);else /* 棧空 */printf("