C语言实现括号匹配检查及栈的应用详解

目录

栈数据结构简介 

C语言实现栈 

栈的初始化 

栈的销毁 

栈的插入

栈的删除

栈的判空

获取栈顶数据 

利用栈实现括号匹配检查

总结 

---

在编程中，经常会遇到需要检查括号是否匹配的问题，比如在编译器中检查代码的语法正确性，或者在文本处理中确保括号的正确使用。本文将通过C语言实现一个括号匹配检查的程序，并详细介绍栈数据结构在其中的应用。
 

栈数据结构简介
 

---

栈是一种后进先出（LIFO, Last In First Out）的数据结构。它就像一个放盘子的栈，最后放上去的盘子总是最先被拿下来。在栈中，有几个基本操作：
 
- 初始化（Init）：创建一个空栈。
 
- 销毁（Destroy）：释放栈占用的内存。
 
- 插入（Push）：将元素添加到栈顶。
 
- 删除（Pop）：从栈顶移除元素。
 
- 判空（Empty）：检查栈是否为空。
 
- 获取元素个数（Size）：返回栈中元素的数量。
 
- 获取栈顶数据（Top）：返回栈顶的元素，但不删除它。
 

---

C语言实现栈
 

c#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>typedef char typestk;
typedef struct Stack
{typestk* a;int top;int capacity;
} ST;

 
这里定义了一个栈的结构体 Stack ，包含一个字符类型的指针 a 用于存储栈中的元素， top 表示栈顶的位置， capacity 表示栈的容量。
 

栈的初始化
 

c// 栈的初始化
void STInit(ST* ps)
{assert(ps);ps->a = (typestk*)malloc(sizeof(typestk) * 4);if (ps->a == NULL){perror("malloc");return;}ps->top = 0;ps->capacity = 4;
}

 
 STInit 函数用于初始化栈。首先通过 malloc 分配4个字符大小的内存空间给栈的数组 a ，如果分配失败，使用 perror 打印错误信息。然后将栈顶位置 top 设为0，栈容量 capacity 设为4。
 

栈的销毁
 

c// 栈的销毁
void STDestory(ST* ps)
{// 查空assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}

 
 STDestory 函数用于销毁栈。先使用 free 释放栈数组 a 占用的内存，然后将指针 a 设为 NULL ，并将栈顶位置 top 和栈容量 capacity 都设为0。
 

栈的插入

 
c// 栈的插入
void STPush(ST* ps, typestk x)
{assert(ps);if (ps->top == ps->capacity){typestk* tmp = (typestk*)realloc(ps->a, sizeof(typestk) * ps->capacity * 2);if (tmp == NULL){perror("realloc error");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}

 
 STPush 函数用于将元素插入栈顶。首先检查栈是否已满（即 top 等于 capacity ），如果已满，使用 realloc 将栈的容量扩大为原来的2倍。如果内存重新分配失败，打印错误信息并返回。然后将元素 x 插入到栈顶位置，并将栈顶位置 top 加1。
 

栈的删除

 
c// 栈的删除
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));    ps->top--;
}

 
 STPop 函数用于从栈顶删除元素。首先检查栈是否为空，如果为空则使用 assert 断言报错。然后将栈顶位置 top 减1，相当于删除了栈顶元素。
 

栈的判空

 
c// 栈的判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}STEmpty 函数用于检查栈是否为空。如果栈顶位置 top 为0，则返回 true ，否则返回 false 。栈的元素个数c// 栈的元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

 
 STSize 函数返回栈中元素的个数，即栈顶位置 top 的值。
 

获取栈顶数据
 

c// 获取栈顶数据
typestk STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}

 
 STTop 函数返回栈顶的元素，但不删除它。首先检查栈是否为空，如果为空则使用 assert 断言报错。然后返回栈顶位置 top - 1 处的元素。
 

利用栈实现括号匹配检查

 
cbool isValid(char* s)
{ST st;STInit(&st);while (*s){if (*s == '[' || *s == '(' || *s == '{'){STPush(&st, *s);}else{if (STEmpty(&st)){STDestory(&st);return false;}char top = STTop(&st);STPop(&st);if ((*s == ')' && top != '(') || (*s == ']' && top != '[') || (*s == '}' && top != '{')){STDestory(&st);return false;}}++s;}bool ret = STEmpty(&st);STDestory(&st);return ret;
}

 

 isValid 函数用于检查给定字符串中的括号是否匹配。
 
初始化一个栈 st 。
 
遍历字符串 s ：
 
- 如果当前字符是左括号（ [ 、 ( 、 { ），将其压入栈中。
 
- 如果当前字符是右括号（ ] 、 ) 、 } ）：
 
- 检查栈是否为空，如果为空，说明没有匹配的左括号，返回 false 。
 
- 否则，获取栈顶元素并弹出栈，检查栈顶元素是否与当前右括号匹配。如果不匹配，返回 false 。
 
遍历结束后，如果栈为空，说明所有括号都匹配，返回 true ；否则返回 false 。最后销毁栈。
 

总结
 

通过以上代码，我们实现了一个简单的栈数据结构，并利用栈解决了括号匹配检查的问题。栈作为一种基本的数据结构，在很多算法和应用中都有广泛的应用，如表达式求值、深度优先搜索等。掌握栈的基本操作和应用场景，对于提升编程能力和解决实际问题都非常有帮助。希望本文能帮助你更好地理解栈和括号匹配问题。