实验五：数据结构之顺序栈实践顺序栈实现括号匹配检测

朱雀 2023-06-07 12:07 81阅读 0赞

实验结果如下：

![2019101420411485.png][]

实验代码如下：

完整源码：

Stack.h

1 #include <stdio.h>
      2 #include <malloc.h>
      3 #define OK 0                        //成功执行
      4 #define Err_Memory -1               //内存分配错误 
      5 #define Err_InvalidParam -2         //输入参数无效
      6 #define Err_Overflow -3             //溢出错误
      7 #define Err_IllegalPos -4           //非法位置
      8 #define Err_NoResult -5             //无法返回结果或返回结果为空
      9 #define Stack_Init_Size 100              //顺序表最大长度
     10 #define Stack_Increment 10         //顺序表存储空间分配增量
     11 
     12 typedef char ElemType;                          //定义顺序表的元素类型ElemType
     13 
     14 typedef struct {
     15     ElemType * stackdata;           //data指向存储数据元素的一维数组，初始大小为Max_Length
     16     int top;                        //顺序表的实际长度,其值小于等于ListLength
     17     int stacksize;                  //当前顺序表分配的空间大小，初始值为Max_Length
     18 } SeqStack;                         //顺序表结构定义
     19 
     20 typedef int Status;                 //定义返回状态
     21 
     22 Status InitStack(SeqStack *S);
     23 Status EmptyStack(SeqStack *S);
     24 Status ClearStack(SeqStack *S);
     25 void TraverseStack(SeqStack *S);
     26 Status LengthStack(SeqStack *S);
     27 Status GetTop(SeqStack *S, ElemType *e);
     28 Status Push(SeqStack *S, ElemType e);
     29 Status Pop(SeqStack *S, ElemType *e);

Stack.c

1 #include "Stack.h"
      2 
      3 
      4 Status InitStack(SeqStack *S)
      5 {
      6     if(!S)
      7         return Err_InvalidParam;
      8 
      9     S->stackdata = (ElemType *)malloc(Stack_Increment*sizeof(ElemType));
     10 
     11     if(!S->stackdata)
     12         return Err_Memory;
     13 
     14     S->top = 0;
     15     S->stacksize = Stack_Init_Size;
     16 
     17     return OK;
     18 }
     19 
     20 Status ClearStack(SeqStack *S)
     21 {
     22     if(!S)
     23         return Err_InvalidParam;
     24 
     25     S->top = 0;
     26 
     27     return 0;
     28 }
     29 
     30 Status EmptyStack(SeqStack *S)
     31 {
     32     if(!S)
     33         return Err_InvalidParam;
     34     return (S->top == 0);
     35 }
     36 
     37 Status LengthStack(SeqStack *S)
     38 {
     39     return S->top;
     40 }
     41 
     42 void TraverseStack(SeqStack *S)
     43 {
     44     int i;
     45 
     46     for(i = 0; i<S->top; i++)
     47       printf("%d\n", *S->stackdata);
     48 }
     49 
     50 Status GetTop(SeqStack *S, ElemType *e)
     51 {
     52     if(!S)
     53         return Err_InvalidParam;
     54 
     55     if(S->top == 0)
     56         return Err_NoResult;
     57 
     58     *e = S->stackdata[S->top-1];
     59 
     60     return 0;
     61 }
     62 
     63 Status Push(SeqStack *S, ElemType e)
     64 {
     65     ElemType *newstack;
     66 
     67     if(!S)
     68         return Err_InvalidParam;
     69 
     70     if(S->top == S->stacksize)
     71         newstack = (ElemType *)realloc(S->stackdata, (S->stacksize+Stack_Increment)*sizeof(ElemType));
     72 
     73     if(!newstack)
     74         return Err_Memory;
     75 
     76 //  S->top = S->stackdata + S->stacksize; //???????????
     77     S->stacksize += Stack_Increment;
     78     S->stackdata[S->top++] = e;
     79 
     80     return OK;
     81 }
     82 
     83 Status Pop(SeqStack *S, ElemType *e)
     84 {
     85 
     86     if(!S)
     87         return Err_InvalidParam;
     88 
     89     if(S->top == 0)
     90         return Err_NoResult;
     91 
     92     *e = S->stackdata[--S->top];
     93 
     94     return OK;
     95 }

括号匹配文件：Backets\_match.c

1 #include <stdio.h>
      2 #include "Stack.h"
      3 
      4 void brackets(char *expression)
      5 {
      6     SeqStack *S;
      7     char ch1, ch2;
      8     int pos = 1;
      9 
     10     S = (SeqStack *)malloc(sizeof(SeqStack));
     11     if(!S){
     12         printf("内存分配错误\n");
     13         return;
     14     }
     15     InitStack(S);
     16     ch1 = expression[pos-1];
     17     while(ch1 != '\0'){
     18         if(ch1 == '(' || ch1 == '[' || ch1 == '{'){
     19             Push(S, ch1);
     20         } else if(ch1 == ')' || ch1 == ']' || ch1 == '}'){
     21             if(EmptyStack(S)){
     22                 printf("表达式中第%d个位置的括号‘%c’不匹配！\n", pos, ch1);
     23                 return;
     24             } else {
     25                 Pop(S, &ch2);
     26                 if((ch1 == ')' && ch2 != '(') || (ch1 == ']' && ch2 != '[') || (ch1 == '}' && ch2 != '{')){
     27                     printf("表达式中第%d个位置的括号‘%c’不匹配！\n", pos, ch1);
     28                     return;
     29                 }
     30 
     31             }
     32         }
     33         ch1 = expression[pos++];
     34 
     35     }
     36     if(EmptyStack(S))
     37       printf("括号匹配\n");
     38     else
     39       printf("表达式中缺少右括号！\n");
     40 
     41 }
     42 int main()
     43 {
     44     char str[100];
     45 
     46     printf("请输入表达式（不超过100个字符）:\n");
     47     
     48     gets(str);
     49     brackets(str);
     50 
     51     return 0;
     52 }

编译命令：gcc Stack.c Brackets\_match.c

执行命令：./a.out

[2019101420411485.png]: /images/20230601/f9c3eba2f5614b5ea20ee22c1f4f66e8.png