实验3栈-实验报告讲解.doc

实 验 报 告 课 程 数据结构及算法 实验项目 3、栈的建立及应用 成 绩 专业班级 指导教师 岳静 姓 名 学号 实验日期 实验目的 掌握栈的特性及其顺序存储结构。 掌握顺序栈的初始化、入栈和出栈操作，并能灵活运用。 实验内容 任意输入一个数学表达式，判断括号（包括大括号、中括号和小括号）是否匹配。 解决思路 可将数学表达式作为字符串进行处理。依次读取字符串中每个字符，对非括号字符不作处理，若为左括号，则应等待与其匹配的右括号。在判断过程中，后读到的左括号比先读到的左括号更急于得到匹配，这一要求与栈先进后出的特点相符，因此可考虑用栈实现括号的匹配。 首先，建立一个栈结构，且初始化为空，即令栈顶指针top=0。然后由键盘上随机输入一个带括号的语句或带括号数学表达式，同时将它们 保存在一个字符型数组中，再对字符数组中的每个元素进行访问，若是遇到右括号，则将栈中的栈顶元素出栈。当字符数组所有元素都访问完之后，再根据栈顶指针top的值判断左右括号是否匹配，若top=base时，则左右括号匹配，否则，左右括号不匹配。 在进行出栈运算时，通常在栈顶指针top=base时，就不能进行出栈运算了，否则返回错误状态。为正确判断形如“x*(y+z))”类型的表达式，可将出栈操作后的状态值可考虑进来，也就是说，当字符数组所有元素都访问完之后，若top=base且状态值为正确则左右括号匹配，否则，左右括号不匹配。 实验代码 #include stdio.h #include string.h #include stdlib.h #include malloc.h typedef int Status; typedef char SElemType; #define stack_INIT_SIZE 100 #define stackINCREMENT 10 #define OK 1 #define ERROR 0 typedef struct { SElemType *base; //栈底指针 SElemType *top; //栈顶指针 int stacksize; //栈空间 }Sqstack; Status iniStack(Sqstack S) //初始化栈 {//构造一个空栈S S.base = (SElemType*)malloc(stack_INIT_SIZE * sizeof(SElemType)); if (!S.base)return(ERROR); S.top = S.base; S.stacksize = stack_INIT_SIZE; return OK; }//InitStack Status push(Sqstack S, SElemType x) { if (S.top - S.base = S.stacksize){ S.base = (SElemType *)realloc(S.base, (S.stacksize + stackINCREMENT)*sizeof(SElemType)); if (!S.base) return(ERROR); S.top = S.base + S.stacksize; S.stacksize += stackINCREMENT; } *S.top++ = x; return OK; } Status pop(Sqstack S, SElemType e) { if (S.top == S.base)return ERROR; e = *--S.top; return OK; } Status GetTop(Sqstack S, SElemType e) { if (S.top == S.base)return ERROR; e = *(S.top - 1); return OK; } Status StackEmpty(Sqstack S) { if (S.base == S.top) return OK; return ERROR; } Status Compare(Sqstack S) { int flag = OK; char ch,e; while ((ch=getchar())!= \n flag) { switch (ch) { case (: case [: case {:push(S,ch); break; case ):if (pop(S,e) == ERROR || e!=() flag = ERROR; break; case ]:if