括号匹配问题.doc

实验报告括号匹配问题、一、实验目的：1、熟练掌握数据结构基本知识；2、通过括号匹配的实验，了解栈的表示和栈的基本操作，掌握栈“后进先出”的特性并能够应用这一特性。二、实验工具：C-Free三、实验内容：设表达式中包含三种括号：圆括号、方括号和花括号，它们可互相嵌套，如( )或（ ( ( ) ) ）等均为正确格式，而（ ）、 ( ) 或( 等均不正确。在算法中可设置一个栈，每读入一个括号，若是左括号，则直接入栈，等待相匹配的同类右括号；若读入的是右括号，且与当前栈顶的左括号同类型，则二者匹配将栈顶的左括号出栈，否则属于不合法情况。另外，如果输入序列已读完，而栈中仍有等待匹配的左括号，或者读入了一个右括号，而栈中已无等待匹配的同类型的左括号，均属不合法情况。当输入序列和栈同时为空时，说明所有括号完全匹配。四、实验过程：#include #include #define STACKINCREAMENT 10 #define STACK_INIT_SIZE 100 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int status; typedef char SElemtype; typedef struct SElemtype *base; SElemtype *top; status stacksize; sqstack; status Init(sqstack *s) s-base = (SElemtype *)malloc(STACK_INIT_SIZE * sizeof(SElemtype); if(!s-base) exit(OVERFLOW); s-top = s-base; s-stacksize = STACK_INIT_SIZE ; return OK; status push(sqstack *s, SElemtype e) if(s-top - s-base = s-stacksize) s-base=(SElemtype*)realloc(s-base,(s-stacksize+STACKINCREAMENT)*sizeof(SElemtype) if(!s-base) exit(OVERFLOW); s-top = s-base + s-stacksize; s-stacksize += STACKINCREAMENT; *s-top+ = e; return OK; status pop(sqstack *s, SElemtype *e) if(s-top = s-base) return ERROR; *e=*-s-top; return OK; status stackempty(sqstack *s) if(s-top=s-base) return OK; return ERROR; status Parenthesis_match(sqstack *s,char *str) int i=0, flag=0; SElemtype e; while(stri != 0) switch(stri) case (: push(s,stri); break; case : push(s,stri); break; case ): pop(s,&e); if(e != () flag=1; break; case : pop(s,&e); if(e!=) flag=1; break; default: break; if(flag) break; i+; if(!flag & stackempty(s) printf(括号匹配成功!n); else printf(括号匹配失败!n); return OK; int main() char str100, enter; sqstack s; Init(&s); printf(请