括号匹配问题--栈

栈的应用

在编程的世界里，经常会遇到各种各样需要处理符号匹配的问题，其中括号匹配是一个经典的基础案例。今天，我们就来深入探讨一段用 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。无论结果如何，最后都要销毁栈，释放所占用的内存资源。

栈的应用与总结

栈作为一种后进先出（LIFO, Last In First Out）的数据结构，在许多场景中都有着广泛的应用。在括号匹配验证这个问题中，栈的特性恰好能够满足我们的需求。通过将左括号压入栈中，当遇到右括号时从栈中弹出相应的左括号进行匹配，能够有效地判断括号是否正确配对。