数据结构实验五.doc

PAGE 1 数据结构实验报告——实验5 实验目的 复习栈的逻辑结构、存储结构及基本操作； 掌握顺序栈、链栈。 二、实验内容 请实现：对于一个可能包括括号{}、[]、（）的表达式，判定其中括号是否匹配。 三、算法描述 （采用自然语言描述） 从键盘输入一个字符串表达式，遇到’{‘ 、’[‘ 或者 ‘(‘ 入栈，遇到’}‘ 、’]‘ 或者 ‘)‘ 出栈，如果最后盏空，证明匹配，否则不匹配。 四、详细设计 （画出程序流程图） 开始 开始 输入表达式 输入表达式 是否是左括号 是否是左括号 N N Y Y 出栈 出栈 入栈 入栈 N表达式是否结束 N 表达式是否结束 Y Y 结束 结束 N五、程序代码 N （给出必要注释） #includestdio.h #includemalloc.h #includestring.h #define STACK_INIT_SIZE 10 #define STACK_GROW_SIZE 5 #define ELEMTYPE char #define OK 1 #define ERROR 0 typedef struct { ELEMTYPE *base; ELEMTYPE *top; int stacksize; }SpStack; int InitStack(SpStack *s) { s-base=((ELEMTYPE*)malloc(STACK_INIT_SIZE*sizeof(ELEMTYPE))); if (!s-base) return ERROR; s-top=s-base; s-stacksize=STACK_INIT_SIZE; return OK; } int StackEmpty(SpStack *s) { if (s-top==s-base) return OK; else return ERROR; } int Push(SpStack *s,ELEMTYPE e) { if (s-top-s-base=s-stacksize) { s-base=((ELEMTYPE*)realloc(s-base,(s-stacksize+STACK_GROW_SIZE)*sizeof(ELEMTYPE))); if (!s-base) return ERROR; s-stacksize+=STACK_GROW_SIZE; s-top=s-base+s-stacksize; } *s-top++=e; return OK; } int Pop(SpStack *s,ELEMTYPE *e) { if (StackEmpty(s)) return ERROR; *e=*(--s-top); return OK; } int Comp(ELEMTYPE a,ELEMTYPE b) { if ((a==(b!=))||(a==[b!=])||(a=={b!=})) return ERROR; else return OK; } int Count(SpStack *s) { ELEMTYPE e[STACK_INIT_SIZE*2]; ELEMTYPE e1; int i; InitStack(s); fgets(e,STACK_INIT_SIZE*2,stdin); if (\n==e[strlen(e)-1]) e[strlen(e)-1]=0; printf(%s\n,e); for (i=0;e[i]!=\0;i++) { switch (e[i]) { case (: case [: case {: Push(s,e[i]); break; case ): case ]: case }: if (StackEmpty(s)) {