栈和队列的应用.docVIP

【实验题目】 栈和队列的应用 【实验内容】 括号的配对问题 【实验目的】 掌握栈和队列的概念及工作原理，运用其原理完成实验题目中的内容。 【实验要求】 通过程序设计，实现括号的配对问题。更好的掌握与理解课堂上老师所讲的概念与原理，通过栈和队列的方法实现目标 【设计原理】 在算法中设置一个栈，读入一个括号，若是有括号，则活着使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的栈中的所有未消解的期待的急迫性都降了一级。在算法的开始和结束时，栈都应该是空的。 【程序清单及注释说明】 typedef char SElemType; #includemalloc.h #includestdio.h #includemath.h #includeprocess.h // exit() #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 struct SqStack { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }; // 顺序栈 Status InitStack(SqStack S) { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); S.top=S.base; if(!S.base) return ERROR; S.stacksize=STACK_INIT_SIZE; return OK; } Status StackEmpty(SqStack S) { if(S.base==S.top) return TRUE; else return FALSE; } Status Push(SqStack S,SElemType e) { if(S.top-S.base=S.stacksize) { S.base=(SElemType *)realloc(S.base,(STACK_INIT_SIZE+S.stacksize)*sizeof(SElemType)); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize=S.stacksize+STACK_INIT_SIZE; } *S.top=e; S.top++; return OK; } Status Pop(SqStack S,SElemType e) { if(S.base==S.top) return ERROR; e=*--S.top; return OK; } void check() // 对于输入的任意一个字符串，检验括号是否配对 { SqStack s; SElemType ch[80],*p,e; if(InitStack(s)) // 初始化栈成功 { printf(请输入所需要匹配开闭括号的表达式：); scanf(%s,ch); p=ch; while(*p) // 没到串尾 switch(*p) { case (: case [:Push(s,*p);p++; break; // 左括号入栈，且p++ case ): case ]: if(!StackEmpty(s)) // 栈不空 { Pop(s,e); // 弹出栈顶元素 if(*p==)e!=(||*p==]e!=[) // 弹出的栈顶元素与*p不配对 { printf(\n括号没有成对出现\n); exit(ERROR); } else { p++; break; // 跳出switch语句 } } else // 栈空 { printf(\n缺少左括号\n); exit(ERROR); } default: p++; // 其它字符不处理，指针向后移 }