数据结构栈应用实验报告：括号匹配

实验目的

1. 了解数据结构栈的基本概念及其应用。
2. 实现栈的基本操作，如入栈、出栈、查看栈顶元素等。
3. 通过实现栈的应用，加深对数据结构栈的理解。

实验内容

本次实验我们将实现栈的一个应用——括号匹配。

括号匹配是一种常见的编程问题，其基本思路是使用栈来检测输入的表达式中的括号是否匹配。我们可以使用栈来存储左括号，每当遇到右括号时弹出栈顶元素，并检查弹出的左括号是否与当前的右括号匹配。如果匹配，则继续扫描表达式；否则，输入的表达式中的括号不匹配，算法结束。

实验步骤

1. 定义栈的结构体，并实现栈的基本操作：入栈、出栈、查看栈顶元素等。
2. 编写括号匹配的函数，使用栈来实现括号的匹配。
3. 编写主函数，输入待匹配的表达式，调用括号匹配的函数进行匹配，输出匹配结果。

实验代码

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100

typedef struct stack
{
    int data[MAXSIZE];
    int top;
}Stack;

void initStack(Stack *s)
{
    s->top=-1;
}

void push(Stack *s,int x)
{
    if(s->top==MAXSIZE-1)
    {
        printf("Stack is full!\n");
        return;
    }
    s->top++;
    s->data[s->top]=x;
}

int pop(Stack *s)
{
    if(s->top==-1)
    {
        printf("Stack is empty!\n");
        return -1;
    }
    int x=s->data[s->top];
    s->top--;
    return x;
}

int getTop(Stack *s)
{
    if(s->top==-1)
    {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->data[s->top];
}

int isEmpty(Stack *s)
{
    return s->top==-1;
}

int match(char a,char b)
{
    if(a=='('&&b==')')
        return 1;
    if(a=='['&&b==']')
        return 1;
    if(a=='{'&&b=='}')
        return 1;
    return 0;
}

int isBracket(char a)
{
    return a=='('||a=='['||a=='{';
}

int isRightBracket(char a)
{
    return a==')'||a==']'||a=='}';
}

int checkBracket(char *str)
{
    Stack s;
    initStack(&s);
    int i=0;
    while(str[i]!='\0')
    {
        if(isBracket(str[i]))
            push(&s,str[i]);
        else if(isRightBracket(str[i]))
        {
            if(isEmpty(&s))
                return 0;
            int top=getTop(&s);
            if(match(top,str[i])==0)
                return 0;
            pop(&s);
        }
        i++;
    }
    return isEmpty(&s);
}

int main()
{
    char str[MAXSIZE];
    printf("Input a string:\n");
    scanf("%s",str);
    if(checkBracket(str))
        printf("Match!\n");
    else
        printf("Not match!\n");
    return 0;
}

实验结果

（请根据实际运行结果填写）

总结

通过本次实验，我更加深入地理解了数据结构栈的基本概念及其应用。我学会了如何使用C语言实现栈的基本操作，并成功地编写了括号匹配的程序。这不仅加深了我对栈的理解，也提高了我的C语言编程能力。