括号匹配问题--栈

用户11991900

发布于 2026-01-15 11:03:46

1090

栈的应用

在编程的世界里，经常会遇到各种各样需要处理符号匹配的问题，其中括号匹配是一个经典的基础案例。今天，我们就来深入探讨一段用 C 语言实现括号匹配验证的代码，同时了解栈（Stack）这种数据结构在其中发挥的重要作用。

代码概览

首先，让我们来看一下这段代码的整体结构。代码定义了一个名为stack的结构体，用于表示栈的数据结构，其中包含了一个字符指针arr用于存储栈中的元素，一个整数top用于指示栈顶的位置，以及一个整数capacity表示栈的当前容量。

typedef struct stack
{
    char *arr;
    int top;
    int capacity;
}stack;

接下来，是一系列对栈进行操作的函数，包括初始化栈（stackInit）、向栈中压入元素（stackpush）、获取栈顶元素（stacktop）、弹出栈顶元素（stackpop）、销毁栈（stackdestroy）以及判断栈是否为空（stackempty）。这些函数构成了栈操作的基本接口，为后续的括号匹配验证提供了基础支持。

栈操作函数详解

1.初始化栈（stackInit）

void stackInit(stack* ps)
{
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}

这个函数的作用是初始化一个栈。它将栈的数组指针arr设为NULL，表示栈中还没有分配内存空间。同时，将栈顶指针top和栈的容量capacity都初始化为 0。

2.向栈中压入元素（stackpush）

void stackpush(stack* ps, char s)
{
    if(ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0? 4 : ps->capacity*2;
        char* tmp = realloc(ps->arr,sizeof(char)*newcapacity);
        if(tmp == NULL)
        {
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newcapacity;
    }
    ps->arr[ps->top++] = s;
}

stackpush函数用于将一个字符s压入栈中。在压入元素之前，首先检查栈是否已满。如果栈的当前容量capacity与栈顶指针top相等，说明栈已满，需要进行扩容操作。这里采用了一种动态扩容的策略，当栈为空时，新的容量设为 4；否则，将当前容量翻倍。通过realloc函数重新分配内存空间，如果分配失败，则调用exit(1)终止程序。成功分配内存后，更新栈的容量，并将元素 s存入栈顶位置，然后将栈顶指针top加 1。

3.获取栈顶元素（stacktop）

char stacktop(stack *ps)
{
    if(ps->top == 0)
    exit(1);
    return ps->arr[ps->top-1];
}

stacktop函数用于获取栈顶元素。在获取元素之前，先检查栈是否为空。如果栈为空（即top为 0），则调用exit(1)终止程序，因为空栈是无法获取栈顶元素的。否则，返回栈顶指针top减 1 位置的元素，即栈顶元素。

4.弹出栈顶元素（stackpop）

void stackpop(stack* ps)
{
    ps->top--;
}

stackpop函数的实现非常简洁，它只是将栈顶指针top减 1，从而实现弹出栈顶元素的操作。需要注意的是，这里并没有真正释放栈顶元素所占用的内存空间，只是逻辑上移除了栈顶元素。

5.销毁栈（stackdestroy）

void stackdestroy(stack*ps)
{
    free(ps->arr);
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}

stackdestroy函数用于销毁栈。它首先通过free函数释放栈数组所占用的内存空间，然后将栈的数组指针arr设为NULL，防止出现野指针。最后，将栈顶指针top和栈的容量capacity都重置为 0。

6.判断栈是否为空（stackempty）

bool stackempty(stack* ps)
{
    if(ps->top == 0)
    {
        return true;
    }
    return false;
}

stackempty函数用于判断栈是否为空。它只需检查栈顶指针top是否为 0，如果为 0，则返回true表示栈为空；否则返回false表示栈不为空。

7.括号匹配验证函数（isValid）

bool isValid(char* s) {
    stack st;
    stackInit(&st);
    char* pi = s;
    while(*pi != '\0')
    {
        if(*pi == '(' || *pi == '[' || *pi =='{')
            stackpush(&st,*pi);
        else
        {
            if(stackempty(&st))
            {
                stackdestroy(&st);
                return false;
            }
        char top = stacktop(&st);
        if((top == '('&&*pi != ')')||(top == '['&& *pi != ']')||(top=='{'&&*pi != '}'))
        {
            stackdestroy(&st);
            return false;    
        }
        stackpop(&st);
        }
        pi++;
    }
    bool ret = stackempty(&st) ? true : false;
    stackdestroy(&st);
    return ret;
}

isValid函数是整个代码的核心，用于判断给定字符串s中的括号是否有效匹配。它首先初始化一个栈st，然后通过一个指针pi遍历字符串s。当遍历到一个左括号（(、[或{）时，将其压入栈中。当遍历到一个右括号（)、]或}）时，首先检查栈是否为空。如果栈为空，说明没有匹配的左括号，直接销毁栈并返回false。否则，获取栈顶元素，判断栈顶元素与当前右括号是否匹配。如果不匹配，则销毁栈并返回false。如果匹配，则弹出栈顶元素，表示成功匹配一对括号。当字符串遍历结束后，检查栈是否为空。如果栈为空，说明所有括号都成功匹配，返回true；否则返回false。无论结果如何，最后都要销毁栈，释放所占用的内存资源。